C-Program For Finding The Strongly Connected Component of a Directed Graph (The Tarjan’s Algorithm)

Hi All. This is the program used to find the strongly connected components using DFS algorithm also called Tarjan’s Algorithm. One of my friend had a problem in the code so though of typing it.


// Strongly connected components using DFS technique
// Anshuman Pandey 11/08

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

#define WHITE 0
#define GRAY 1
#define BLACK 2

int n;  // number of nodes
int e;  // number of edges
struct edge {
int tail,head,type;
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *firstEdge;  // Table indicating first in range of edges with a common tail

int *vertexStatus,*secondDFSrestarts;

int tailThenHead(const void* xin, const void* yin)
// Used in calls to qsort() and bsearch() for read_input_file()
{
int result;
edgeType *x,*y;

x=(edgeType*) xin;
y=(edgeType*) yin;
result=x->tail – y->tail;
if (result!=0)
return result;
else
return x->head – y->head;
}

void read_input_file()
{
int a,b,i,j;
edgeType work;
edgeType *ptr;
printf(“Enter number of vertices,edges”);
scanf(“%d %d”,&n,&e);
edgeTab=(edgeType*) malloc(e*sizeof(edgeType));
if (!edgeTab)
{
printf(“edgeTab malloc failed %dn”,__LINE__);
exit(0);
}

// read edges
for (i=0; i<e; i++)
{
printf(“If a—>b then enter a,b: “);
scanf(“%d %d”,&a,&b);
if (a<0 || a>=n || b<0 || b>=n)
{
printf(“Invalid input %d %d at %dn”,a,b,__LINE__);
exit(0);
}
edgeTab[i].tail=a;
edgeTab[i].head=b;
}

// sort edges
qsort(edgeTab,e,sizeof(edgeType),tailThenHead);

// Coalesce duplicates into a single edge
j=0;
for (i=1; i<e; i++)
if (edgeTab[j].tail==edgeTab[i].tail
&& edgeTab[j].head==edgeTab[i].head)
;
else
{
j++;
edgeTab[j].tail=edgeTab[i].tail;
edgeTab[j].head=edgeTab[i].head;
}
e=j+1;

// For each vertex as a tail, determine first in range of edgeTab entries
firstEdge=(int*) malloc((n+1)*sizeof(int));
if (!firstEdge)
{
printf(“malloc failed %dn”,__LINE__);
exit(0);
}
j=0;
for (i=0; i<n; i++)
{
firstEdge[i]=j;
for ( ;
j<e && edgeTab[j].tail==i;
j++)
;
}
firstEdge[n]=e;
}

int finishIndex;

void DFSvisit(int u)
{
int i,v;

vertexStatus[u]=GRAY;

for (i=firstEdge[u];i<firstEdge[u+1];i++)
{
v=edgeTab[i].head;
if (vertexStatus[v]==WHITE)
DFSvisit(v);
}
vertexStatus[u]=BLACK;
secondDFSrestarts[--finishIndex]=u;
}

void reverseEdges()
{
int a,b,i,j;
edgeType work;
edgeType *ptr;

for (i=0; i<e; i++)
{
a=edgeTab[i].tail;
b=edgeTab[i].head;
edgeTab[i].tail=b;
edgeTab[i].head=a;
}

// sort edges
qsort(edgeTab,e,sizeof(edgeType),tailThenHead);

// For each vertex as a tail, determine first in range of edgeTab entries
if (!firstEdge)
{
printf(“malloc failed %dn”,__LINE__);
exit(0);
}
j=0;
for (i=0; i<n; i++)
{
firstEdge[i]=j;
for ( ;
j<e && edgeTab[j].tail==i;
j++)
;
}
firstEdge[n]=e;
}

void DFSvisit2(int u)
{
int i,v;

printf(“%dn”,u); // Indicate that u is in SCC for this restart
vertexStatus[u]=GRAY;

for (i=firstEdge[u];i<firstEdge[u+1];i++)
{
v=edgeTab[i].head;
if (vertexStatus[v]==WHITE)
DFSvisit2(v);
}
vertexStatus[u]=BLACK;
}

int main()
{
int u,i,j,k,nextDFS;
int SCCcount=0;

read_input_file();

vertexStatus=(int*) malloc(n*sizeof(int));
secondDFSrestarts=(int*) malloc(n*sizeof(int));
if (!vertexStatus || !secondDFSrestarts)
{
printf(“malloc failedn”);
exit(0);
}
// DFS code
for (u=0;u<n;u++)
vertexStatus[u]=WHITE;
finishIndex=n;
for (u=0;u<n;u++)
if (vertexStatus[u]==WHITE)
DFSvisit(u);

reverseEdges();

// DFS code
for (u=0;u<n;u++)
vertexStatus[u]=WHITE;
for (i=0;i<n;i++)
if (vertexStatus[secondDFSrestarts[i]]==WHITE)
{
SCCcount++;
printf(“Strongly Connected Component %dn”,SCCcount);
DFSvisit2(secondDFSrestarts[i]);
}

free(edgeTab);
free(firstEdge);
free(vertexStatus);
free(secondDFSrestarts);
return 0;
}