DIRECTED ACYCLIC GRAPH (DAG)

Program

Write a program to find the topological order of a diagraph G represented as adjacency lists.

#include <stdio.h>

#define N 11                // no of total vertices in the graph.

typedef enum {FALSE, TRUE} bool;
typedef struct node node;

struct node {
   int count;        // for arraynodes : in-degree.
                     // for listnodes : vertex no this vertex is connected to.
                     // if this node is out of graph : −1.
                     // if this has 0 indegree then it occurs in zerolist.
   node *next;
};

node graph[N];
node *zerolist;

void addToZerolist( int v ) {
    /*
     * adds v to zerolist as v has 0 predecessors.
     */
    node *ptr = (node *)malloc( sizeof(node) );
    ptr->count = v;
    ptr->next = zerolist;
    zerolist = ptr;
}

void buildGraph( int a[][2], int edges ) {
   /*
    * fills global graph with input given in a.
    * a[i][0] is src vertex and a[i][1] is dst vertex.
    */
   int i;

   // init graph.
   for( i=0; i<N; ++i ) {
       graph[i].count = 0;
       graph[i].next = NULL;
   }

   // now add the list entries.
   for( i=0; i<edges; ++i ) {
      // add new node to src list.
      node *ptr = (node *)malloc( sizeof(node) );
      ptr->count = a[i][1];
      ptr->next = graph[ a[i][0] ].next;
      graph[ a[i][0] ].next = ptr;
      // increase indegree of dst.
      graph[ a[i][1] ].count++;
   }

   // now create list of zero predecessors.
   zerolist = NULL;     // list of vertices having 0 predecessors.
   for( i=0; i<N; ++i )
      if( graph[i].count == 0 ) {
             addToZerolist(i);
      }
}

void printGraph() {
    int i;
    node *ptr;

    for( i=0; i<N; ++i ) {
        node *ptr;
        printf( "%d: pred=%d: ", i, graph[i].count );
        for( ptr=graph[i].next; ptr; ptr=ptr->next )
               printf( "%d ", ptr->count );
        printf( "\n" );
    }
    printf( "zerolist: " );
        for( ptr=zerolist; ptr; ptr=ptr->next )
            printf( "%d ", ptr->count );
        printf( "\n" );
    }

    int getZeroVertex() {
        /*
         * returns the vertex with zero predecessors.
         * if no such vertex then returns −1.
         */
        int v;
        node *ptr;

        if( zerolist == NULL )
            return −1;
        ptr = zerolist;
        v = ptr->count;
        zerolist = zerolist->next;
        free(ptr);

        return v;
   }

   void removeVertex( int v ) {
       /*
        * deletes vertex v and its outgoing edges from global graph.
        */
       node *ptr;
       graph[v].count = −1;
       // free the list graph[v].next.
       for( ptr=graph[v].next; ptr; ptr=ptr->next ) {
          if( graph[ ptr->count ].count > 0 ) // normal nodes.
                 graph[ ptr->count ].count-;
          if( graph[ ptr->count ].count == 0 )          // this is NOT else of above if.
                 addToZerolist( ptr->count );
       }
}

void topsort( int nvert ) {
    /*
     * finds recursively topological order of global graph.
     * nvert vertices of graph are needed to be ordered.
     */
    int v;

    if( nvert > 0 ) {
       v = getZeroVertex();
       if( v == −1 ) {       // no such vertex.
               fprintf( stderr, "graph contains a cycle.\n" );
               return;
       }
       printf( "%d.\n", v );
       removeVertex(v);
       topsort( nvert-1 );
   }
}

int main() {
    int a[][2] = {
                           {0,1},
                           {0,3},
                           {0,2},
                           {1,4},
                           {2,4},
                           {2,5},
                           {3,4},
                           {3,5}
                      };
    buildGraph( a, 8 );
    printGraph();
    topsort(N);
}

MINIMUM-COST SPANNING TREE

The following program can be used to find the minimum spanning tree of a graph.

#include <stdio.h>

#define MAXVERTICES 10
#define MAXEDGES 20
typedef enum {FALSE, TRUE} bool;

int getNVert(int edges[][3], int nedges) {
   /*
    * returns no of vertices = maxvertex + 1;
    */
   int nvert = −1;
   int j;

   for( j=0; j<nedges; ++j ) {
      if( edges[j][0] > nvert )
             nvert = edges[j][0];

      if( edges[j][1] > nvert )
             nvert = edges[j][1];
   }
   return ++nvert;         // no of vertices = maxvertex + 1;
}

bool isPresent(int edges[][3], int nedges, int v) {
   /*
    * checks whether v has been included in the spanning tree.
    * thus we see whether there is an edge incident on v which has
    * a negative cost. negative cost signifies that the edge has been
    * included in the spanning tree.
    */

   int j;
   for(j=0; j<nedges; ++j)
      if(edges[j][2] < 0 && (edges[j][0] == v || edges[j][1] == v))
               return TRUE;

   return FALSE;
}

void spanning(int edges[][3], int nedges) {
   /*
    * finds a spanning tree of the graph having edges.
    * uses kruskal's method.
    * assumes all costs to be positive.
    */
   int i, j;
   int tv1, tv2, tcost;
   int nspanedges = 0;
   int nvert = getNVert(edges, nedges);

   // sort edges on cost.
   for(i=0; i<nedges−1; ++i)
      for(j=i; j<nedges; ++j)
             if(edges[i][2] > edges[j][2]) {
                    tv1 = edges[i][0]; tv2 = edges[i][1]; tcost = edges[i][2];
                    edges[i][0] = edges[j][0]; edges[i][1] = edges[j][1]; edges[i][2] = edges[j][2];
                    edges[j][0] = tv1; edges[j][1] = tv2; edges[j][2] = tcost;
                  }
    for(j=0; j<nedges-1; ++j) {
        // consider edge j connecting vertices v1 and v2.
        int v1 = edges[j][0];
        int v2 = edges[j][1];

         // check whether it forms a cycle in the up until now formed spanning tree.
         // checking can be done easily by checking whether both v1 and v2 are in
        // the current spanning tree!
        if(isPresent(edges, nedges, v1) && isPresent(edges, nedges, v2)) // cycle.
                 printf("rejecting: %d %d %d...\n", edges[j][0], edges[j][1], edges[j][2]);
   else {
           edges[j][2] = -edges[j][2];
           printf("%d %d %d.\n", edges[j][0], edges[j][1], -edges[j][2]);
           if(++nspanedges == nvert-1)
                   return;
         }
   }
   printf("No spanning tree exists for the graph.\n");
}

main() {
    int edges[][3] = {
                                 {0,1,16},
                                 {0,4,19},
                                 {0,5,21},
                                 {1,2,5},
                                 {1,3,6},
                                 {1,5,11},
                                 {2,3,10},
                                 {3,4,18},
                                 {3,5,14},
                                 {4,5,33}
                           };
 int nedges = sizeof(edges)/3/sizeof(int);
 spanning(edges, nedges);

 return 0;
}

CONNECTED COMPONENT OF A GRAPH

Write a function dfs(v) to traverse a graph in a depth-first manner starting from vertex v. Use this function to find connected components in the graph. Modify dfs() to produce a list of newly visited vertices. The graph is represented as adjacency lists.

#include <stdio.h>

#define MAXVERTICES 20
#define MAXEDGES 20

typedef enum {FALSE, TRUE, TRISTATE} bool;
typedef struct node node;

struct node {
   int dst;
   node *next;
};

void printGraph( node *graph[], int nvert ) {
   /*
    * prints the graph.
    */
   int i, j;
   for( i=0; i<nvert; ++i ) {
       node *ptr;
       for( ptr=graph[i]; ptr; ptr=ptr->next )
           printf( "[%d] ", ptr->dst );
       printf( "\n" );
   }
}

void insertEdge( node **ptr, int dst ) {
    /*
     * insert a new node at the start.
     */
    node *newnode = (node *)malloc( sizeof(node) );
    newnode->dst = dst;
    newnode->next = *ptr;
    *ptr = newnode;
}

void buildGraph( node *graph[], int edges[2][MAXEDGES], int nedges ) {
    /*
     * fills graph as adjacency list from array edges.
     */
    int i;
    for( i=0; i<nedges; ++i ) {
        insertEdge( graph+edges[0][i], edges[1][i] );
        insertEdge( graph+edges[1][i], edges[0][i] ); // undirected graph.
    }
}

void dfs( int v, int *visited, node *graph[] ) {
    /*
     * recursively traverse graph from v using visited.
     * and mark all the vertices that come in dfs path to TRISTATE.
     */
    node *ptr;

    visited[v] = TRISTATE;
    //printf( "%d \n", v );
    for( ptr=graph[v]; ptr; ptr=ptr->next )
       if( visited[ ptr->dst ] == FALSE )
           dfs( ptr->dst, visited, graph );
}
void printSetTristate( int *visited, int nvert ) {
    /*
     * prints all vertices of visited which are TRISTATE.
     * and set them to TRUE.
     */
    int i;

    for( i=0; i<nvert; ++i )
       if( visited[i] == TRISTATE ) {
           printf( "%d ", i );
           visited[i] = TRUE;
       }
    printf( "\n\n" );
}

void compINC(node *graph[], int nvert) {
    /*
     * prints all connected components of graph represented using INC lists.
     */
    int *visited;
    int i;

    visited = (int *)malloc( nvert*sizeof(int) );
    for( i=0; i<nvert; ++i )
        visited[i] = FALSE;

    for( i=0; i<nvert; ++i )
        if( visited[i] == FALSE ) {
            dfs( i, visited, graph );
            // print all vertices which are TRISTATE.
            // and mark them to TRUE.
            printSetTristate( visited, nvert );
       }
   free( visited );
}

int main() {
    int edges[][MAXEDGES] = { {0,2,4,5,5,4},
                              {1,1,3,4,6,6}
                           };
    int nvert = 7; // no of vertices.
    int nedges = 6; // no of edges in the graph.
    node **graph = (node **)calloc( nvert, sizeof(node *) );

    buildGraph( graph, edges, nedges );
    printGraph( graph, nvert );
    compINC( graph, nvert );

    return 0;
}

BREADTH-FIRST TRAVERSAL

#include <stdio.h>
#include <stdlib.h>
#define MAX 10
struct node
   {
     int data;
     struct node *link;
   };
void buildadjm(int adj[][MAX], int n)
   {
     int i,j;
     printf("enter adjacency matrix \n",i,j);
     for(i=0;i<n;i++)
         for(j=0;j<n;j++)
                 scanf("%d",&adj[i][j]);
   }

/* A function to insert a new node in queue*/
struct node *addqueue(struct node *p,int val)
{
   struct node *temp;
   if(p == NULL)
   {
      p = (struct node *) malloc(sizeof(struct node)); /* insert the new node first node*/
      if(p == NULL)
         {
              printf("Cannot allocate\n");
              exit(0);
         }
     p->data = val;
     p->link=NULL;
  }
 else
 {
 temp= p;
while(temp->link != NULL)
{
 temp = temp->link;
}
   temp->link = (struct node*)malloc(sizeof(struct node));
   temp = temp->link;
   if(temp == NULL)
        {
              printf("Cannot allocate\n");
              exit(0);
        }
   temp->data = val;
   temp->link = NULL;
}
return(p);
}
struct node *deleteq(struct node *p,int *val)
{  struct node *temp;
   if(p == NULL)
   {
        printf("queue is empty\n");
               return(NULL);
   }
    *val = p->data;
    temp = p;
    p = p->link;
    free(temp);
    return(p);
  }

void bfs(int adj[][MAX], int x,int visited[], int n, struct node **p)
{
    int y,j,k;
    *p = addqueue(*p,x);
    do{

            *p = deleteq(*p,&y);
            if(visited[y] == 0)
                 {
                      printf("\nnode visited = %d\t",y);
              visited[y] = 1;
                  for(j=0;j<n;j++)
              if((adj[y][j] ==1) && (visited[j] == 0))
                      *p = addqueue(*p,j);
               }

      }while((*p) != NULL);
}
void main()
   {
     int adj[MAX][MAX];

     int n;
     struct node *start=NULL;
     int i, visited[MAX];
     printf("enter the number of nodes in graph maximum = %d\n",MAX);
     scanf("%d",&n);
     buildadjm(adj,n);
     for(i=0; i<n; i++)
        visited[i] =0;
     for(i=0; i<n; i++)
       if(visited[i] ==0)
            bfs(adj,i,visited,n,&start);
    }

DEPTH-FIRST TRAVERSAL

Program

#include <stdio.h>
#define max 10

/* a function to build adjacency matrix of a graph */
void buildadjm(int adj[][max], int n)
   {
     int i,j;
     for(i=0;i<n;i++)
         for(j=0;j<n;j++)
          {
     printf("enter 1 if there is an edge from %d to %d, otherwise enter
0 \n",
   i,j);

            scanf("%d",&adj[i][j]);
            }
      }

/* a function to visit the nodes in a depth-first order */
void dfs(int x,int visited[],int adj[][max],int n)
{
   int j;
   visited[x] = 1;
   printf("The node visited id %d\n",x);
   for(j=0;j<n;j++)
      if(adj[x][j] ==1 && visited[j] ==0)
           dfs(j,visited,adj,n);
}
void main()
   {
      int adj[max][max],node,n;
      int i, visited[max];
      printf("enter the number of nodes in graph maximum = %d\n",max);
      scanf("%d",&n);
      buildadjm(adj,n);
      for(i=0; i<n; i++)
        visited[i] =0;
      for(i=0; i<n; i++)
       if(visited[i] ==0)
            dfs(i,visited,adj,n);
      }

Explanation

1. Initially, all the elements of an array named visited are set to 0 to indicate that all the vertices are unvisited.
2. The traversal starts with the first vertex (that is, vertex 0), and marks it visited by setting visited[0] to 1. It then considers one of the unvisited vertices adjacent to it and marks it visited, then repeats the process by considering one of its unvisited adjacent vertices.
3. Therefore, if the following adjacency matrix that represents the graph of Figure 22.9 is given as input, the order in which the nodes are visited is given here:
   • Input: 1. The number of nodes in a graph
     2. Information about edges, in the form of values to be stored in adjacency matrix 1 if there is an edge from node i to node j, 0 otherwise
   • Output: Depth-first ordering of the nodes of the graph starting from the initial vertex, which is vertex 0, in our case

COMPUTING INDEGREE AND OUTDEGREE OF A NODE OF A GRAPH USING ADJACENCY MATRIX REPRESENTATION

#include <stdio.h>
#define MAX 10
/* a function to build an adjacency matrix of the graph*/
void buildadjm(int adj[][MAX], int n)
   {
     int i,j;
     for(i=0;i<n;i++)
         for(j=0;j<n;j++)
         {
         printf("Enter 1 if there is an edge from %d to %d, otherwise enter 0 \n",
i,j);

         scanf("%d",&adj[i][j]);
         }
   }

/* a function to compute outdegree of a node*/
int outdegree(int adj[][MAX],int x,int n)
    {
       int i, count =0;
       for(i=0;i<n;i++)
           if( adj[x][i] ==1) count++;
      return(count);
    }
   /* a function to compute indegree of a node*/
   int indegree(int adj[][MAX],int x,int n)
       {
          int i, count =0;
          for(i=0;i<n;i++)
              if( adj[i][x] ==1) count++;
         return(count);
       }
  void main()
     {
       int adj[MAX][MAX],node,n,i;
       printf("Enter the number of nodes in graph maximum = %d\n",MAX);
        scanf("%d",&n);
       buildadjm(adj,n);
       for(i=0;i<n;i++)
       {
          printf("The indegree of the node %d is %d\n",i,indegree(adj,i,n));
        printf("The outdegree of the node %d is %d\n",
i,outdegree(adj,i,n));
   }
}

Explanation

1. This program uses the adjacency matrix representation of a directed graph to compute the indegree and outdegree of each node of the graph.
2. It first builds an adjacency matrix of the graph by calling a buildadjm function, then goes in a loop to compute the indegree and outdegree of each node by calling the indegree and outdegree functions, respectively.
3. The indegree function counts the number of 1's in a column of an adjacency matrix using the node number whose indegree is to be computed as a column index.
4. The outdegree function counts the number of 1's in a row of an adjacency matrix by using the node number whose outdegree is to be computed as a row index.
   • Input: 1. The number of nodes in a graph
     2. Information about edges, in the form of values, to be stored in adjacency matrix 1, if there is an edge from node i to node j; 0 otherwise.
   • Output: The indegree and outdegree of each node.