Thread: Random Graph datastructure

  1. #1
    Registered User
    Join Date
    Jun 2013
    Posts
    2

    Random Graph datastructure

    Hi,

    I have written a code to generate random graphs and test floyd warshalls algorithm. but the output of the adjacency matrix is wearied. Could you please help me in correcting it? Below is the code.

    Code:
    /*C PROGRAM TO IMPLEMENT ALL PAIR SHORTEST PATH USING FLOYDS ALGORITHM
     
    INPUT: N VALUE FOR NUMBER OF VERTICES
     
    OUTPUT: ADJACENCY MATRIX
    SHORTEST DISTANCE MATRIX
    */
     
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define INF 99999
    #define MAX_NODE 50
    #define MAX_EDGE 50
    
    void AdjacencyMatrix(int a[][MAX_NODE],int n, int e){ //To generate adjacency matrix for given nodes
        int i,j;
        srand ( time(NULL) );
        for(i = 0;i < n; i++)
        {
            for(j = 0;j <= e; j++)
            {
                a[i][j] = 0;
            }
        }
    
        for(i = 1; i < n; i++)
        {
            for(j=0;j<i;j++)
            {
                a[i][j] = 99;
                a[j][i] = rand()%10;
            }
        }
    }
    
    int min(int a,int b){
        if(a < b)
            return a;
        else
            return b;
    }
     
    void floyds(int a[][],int n,int e){
        int i,j,k;
        for(k = 0;k < n ; k++)
        {
            for(i = 0;i < n; i++)
            {
                for(j = 0;j < e ; j++)
                {
                    a[i][j] = min (a[i][j], a[i][k] + a[k][j] );
                }
            }
        }
    }
     
    int main()
    {
        int a[MAX_NODE][MAX_EDGE],n,i,j,e;
        /*
        FILE *fp = fopen("floyds.dot","w"); 
    
        fprintf(fp,"digraph A {\n"); 
         */
        /*printf("Enter the vertices of the digraph\n"); 
        /* scanf("%d",&n); */
        srand ( time(NULL) );
        n = rand()%MAX_NODE;
        printf("vertices of the digraph is: %d \n", n);
    
        srand ( time(NULL) );
        e = rand()%MAX_EDGE;
        if(n == e) {
            n = n+1;
        }
        printf("Edges of the digraph is: %d \n", e);
    
        AdjacencyMatrix(a,n,e);
        printf("\t\tAdjacency Matrix of the graph\n"); /* PRINT ADJACENCY MATRIX */
        for(i = 0;i < n; i++)
        {
            for(j = 0;j < e; j++)
            {
                printf("%d->%d = %d\t", i, j, a[i][j]);  /* printf("%d\t", a[i][j]); */
            }
            printf("\n");
        }
        floyds(a,n,e);
    
        printf("\n Shortest distance matrix\n"); /*PRINT SHORTEST DISTANCE MATRIX*/
        for(i = 0;i < n; i++)
        {
            for(j = 0;j < e; j++)
            {
                if (a[i][j] == 99)
                    printf("%7s", "99");
                else
                    printf ("%7d", a[i][j]);
            }
            printf("\n");
        }
        return 0;
    }

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I'm sorry to hear that your output is fatigued.
    But I notice that you're using srand incorrectly.
    It should be called only once, not every time you use rand.
    Put it as the first executable statement in main.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Datastructure lab
    By El_Maco in forum C++ Programming
    Replies: 14
    Last Post: 10-10-2004, 07:35 AM
  2. Replies: 2
    Last Post: 12-25-2003, 01:31 AM
  3. Replies: 2
    Last Post: 12-16-2002, 09:27 PM
  4. Replies: 1
    Last Post: 12-14-2002, 01:51 AM
  5. Link lists as datastructure
    By stseitli in forum C Programming
    Replies: 13
    Last Post: 07-09-2002, 07:34 AM