#include <stdio.h>
#include <stdlib.h>

int **read_matrix_f(FILE *f, int *n)
{
    int i,j,m;
    int **a;
    fscanf(f,"%d",&m);

    a=(int **)malloc(m*sizeof(int*));
    for(i=0;i<m;i++)
    {
        a[i]=(int *)malloc(m*sizeof(int));
    }

    for(i=0;i<m;i++)
    {
        for(j=0;j<m;j++)
        {
           fscanf(f,"%d",&a[i][j]);
        }
    }

    *n=m;
    return a;
}

void print_matrix(int **a, int n)
{
    int i,j;

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%3d",a[i][j]);
        }
        putchar('\n');
    }

}

int **create_zero_matrix(int n)
{
    int **a;
    int i,j;

    a=(int **)malloc(n*sizeof(int*));
    for(i=0;i<n;i++)
    {
        a[i]=(int *)malloc(n*sizeof(int));
    }


    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
           a[i][j]=0;
        }
    }

    return a;
}

int **create_identity_matrix(int n)
{
    int **a;
    int i,j;

    a=(int **)malloc(n*sizeof(int*));
    for(i=0;i<n;i++)
    {
        a[i]=(int *)malloc(n*sizeof(int));
    }


    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
           if(i==j) a[i][j]=1;
           else a[i][j]=0;
        }
    }

    return a;
}

int** matrix_add(int **a,int **b,int n)
{
    int **c;
    int i,j;

    c=(int **)malloc(n*sizeof(int*));
    for(i=0;i<n;i++)
    {
        c[i]=(int *)malloc(n*sizeof(int));
    }


    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            c[i][j]=a[i][j]+b[i][j];
        }
    }
    return c;
}

int** matrix_mult(int **a,int **b,int n)
{
    int **c;
    int i,j,k;

    c=(int **)malloc(n*sizeof(int*));
    for(i=0;i<n;i++)
    {
        c[i]=(int *)malloc(n*sizeof(int));
    }


    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            c[i][j]=0;
        }
    }

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            for(k=0;k<n;k++)
            {
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }

    return c;
}

int raz_podgraf(int **a,int n,int **b,int m)
{
    if(n!=m) return 0;

    int i,j;

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j]==0 && b[i][j]==1) return 0;
        }
    }
    return 1;
}

int stepen_cvora(int **a,int n, int k)
{
    int j,count;
    count=0;
    for(j=0;j<n;j++)
    {
        count+=a[k][j];
    }

    return count;
}

int IJ_Walk_length_k(int **a, int n, int i, int j, int k)
{
    int **m,ii;

    m=create_identity_matrix(n);

    for(ii=0;ii<k;ii++)
    {
        m=matrix_mult(m,a,n);
    }
    return m[i][j];
}

int IsFull(int **a,int n)
{
    int i,j;

    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
           if (!a[i][j]) return 0;

    return 1;
}

int **MakeDistanceMatrix(int **a,int n)
{
    int **d=create_zero_matrix(n);
    int **m=create_identity_matrix(n);

    int i,j,k;

    for(k=1;k<n;k++)
    {
        m=matrix_mult(m,a,n);

        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(!d[i][j]&& m[i][j]) d[i][j]=d[j][i]=k;
            }
        }
        if(IsFull(d,n)) return d;
    }
    return d;
}

int Diameter(int **a,int n)
{
    int **d=MakeDistanceMatrix(a,n);

    int max=0;
    int i,j;

    for(i=0;i<n;i++)
       for(j=i+1;j<n;j++)
          if(d[i][j]>max) max=d[i][j];

    return max;
}

int IsGraphConnected (int **a,int n)
{
    int **b=create_zero_matrix(n);
    int **m=create_identity_matrix(n);
    int i,j,k;

    for(k=1;k<n;k++)
    {
        m=matrix_mult(m,a,n);

        for(i=0;i<n;i++)
           for(j=i+1;j<n;j++)
              if(!b[i][j] && m[i][j])
              {
                  b[i][j]=b[j][i]=1;
              }
        if(IsFull(b,n)) return 1;
    }
    return 0;
}

int IsBridge(int **a,int n,int i, int j)
{
    if(!IsGraphConnected(a,n))
    {
        printf("Ne moze se ispitati da li je neka grana most jer je graf nepovezan!\n");
        return -1;
    }
    a[i][j]=0;
    a[j][i]=0;
    if(IsGraphConnected(a,n)) return 0;
    else return 1;
}

int IsArtV(int **a,int n,int k)
{
    if(!IsGraphConnected(a,n))
    {
        printf("Ne moze se ispitati da li je neka grana most jer je graf nepovezan!\n");
        return -1;
    }

    int m=n-1,i,j,ii,jj;
    int **b=create_zero_matrix(m);

    for(i=0;i<m;i++)
       for(j=0;j<m;j++)
       {
           if(i<k) ii=i;
           else ii=i+1;
           if(j<k) jj=j;
           else jj=j+1;
           b[i][j]=a[ii][jj];
       }

    if(IsGraphConnected(b,m)) return 0;
    else return 1;
}

int main(void)
{
    int **mat,**dist;
    int n,i;
    FILE *f;

    f=fopen("test2.txt","r");
    mat=read_matrix_f(f,&n);
    fclose(f);
    print_matrix(mat,n);
    putchar('\n');

    for(i=1;i<11;i++) printf("Broj setnji duzine %d od 2 do 6 je %d\n",i,IJ_Walk_length_k(mat,n,1,5,i));
    putchar('\n');

    dist=MakeDistanceMatrix(mat,n);
    print_matrix(dist,n);
    putchar('\n');

    printf("Dijametar matrice je %d\n\n",Diameter(mat,n));

    if(IsGraphConnected(mat,n)) printf("Graf je povezan!\n\n");
    else printf("Graf nije povezan!\n\n");

 /*   i=IsBridge(mat,n,0,2);
    if(i==1) printf("Ovo je most!\n\n");
    else if(i==0) printf("Nije most!\n\n");
 */

    for(i=0;i<n;i++)
    {
        int k;
        k=IsArtV(mat,n,i);
        if(k==1) printf("%d jeste artikulacioni cvor!\n\n",i);
        else if (k==0) printf("%d nije artikulacioni cvor!\n\n",i);
    }

    getchar();
    return 0;
}