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

Rating 2.33 out of 5
[?]

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(nsizeof(int));
secondDFSrestarts=(int) malloc(nsizeof(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;
}

Anshuman

About Anshuman

Computer Engineer ... MBA .. Endurance Runner ... Physics Geek ... Genius
Bookmark the permalink.

11 Comments


  1. Believe me.. This code is really useful.. especially bcoz in spite of searching for a looonnngg time I could not find the code on the Internet


  2. please example input file and out put.


  3. please example input file and out put. i am try no generate exe file .


  4. Hi, it is really a good work. Typing the values for vertices and edges would be so crucial, if the network (graph) is so large. Hence, it would be helpful to the people, if the values can be supplied through a file.


  5. plz……………..give this program in a simple coding


  6. in given code there is a function calling of qsort().where is that function…below to that function some for loop is missing….


  7. the program is only taking inputs and NOT displaying any output


  8. This code is USELESS because its not inside Code HTML Tag. If we copy paste this into codeblocks, it will give /223 /224 /226 error codes. As the charecters like “” are encoded. Cannot copy from “viewsource” either because of stupid HTML tags.


    • Hahaha.. I agree.. It’s been long I coded this piece. The tags did have some issue. Not sure if it works now. Else do the hard way 🙁

Liked it? Share Your Thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.