strongly connected components

c program to find strongly connected components
Task - Implement the algorithm to compute Strongly Connected Components of a graph .
Display the finishing and discovery time of each vertex as well as the transpose of the graph G along with strongly connected component

 
header.c
int dfs(int **a,int *visited,int v,int *d,int *f,int time,int s);

main.c
#include<stdio.h>
#include<stdlib.h>
#include"header.h"

int main(){
int **a,**b,i,j,v,*visited,*visited2,*d,*f,time=0,max,pos,*trick;
struct timeval tim;
double time_start,time_end,time1;
FILE *fp;
fp=fopen("input.txt","r");

fscanf(fp,"%d",&v);

printf("the v is %d\n",v);
visited=(int *)calloc(v,sizeof(int));
visited2=(int *)calloc(v,sizeof(int));
trick=(int *)calloc(v,sizeof(int));

d=(int *)calloc(v,sizeof(int));
f=(int *)calloc(v,sizeof(int));

a=(int **)calloc(v,sizeof(int *));

for(i=0;i<v;i++){
a[i]=(int *)calloc(v,sizeof(int));
}

b=(int **)calloc(v,sizeof(int *));

for(i=0;i<v;i++){
b[i]=(int *)calloc(v,sizeof(int));
}

for(i=0;i<v;i++){

    for(j=0;j<v;j++){

        fscanf(fp,"%d",&a[i][j]);

    }
}
printf("the graph is :\n");
for(i=0;i<v;i++){

    for(j=0;j<v;j++){
    if(a[i][j]==1)
        printf("%d---->%d\n",i,j);

    }
}

for(i=0;i<v;i++){
if(visited[i]==0)
    dfs(a,visited,v,d,f,time,i);
}

printf("the transpose of the graph is :\n");
for(i=0;i<v;i++){

    for(j=0;j<v;j++){
        b[i][j]=a[j][i];
        if(b[i][j]==1)
        printf("%d---->%d\n",i,j);

    }
}

printf("vertex\tstart\tfinish\n",i,d[i],f[i]);
for(i=0;i<v;i++){
printf("%d\t%d\t%d\n",i,d[i],f[i]);
}

printf("\n");
printf("the components are :\n");

gettimeofday(&tim,NULL);
time_start=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);

for(i=0;i<v;i++){
    max=-1;
    for(j=0;j<v;j++){
        if(f[j]>max && visited2[j]==0){
            max=f[j];
            pos=j;
    }

}

if(max==-1)
    break;

if(visited2[pos]==0)
    dfs(b,visited2,v,d,f,time,pos);

for(j=0;j<v;j++){
    if(visited2[j]==1 && trick[j]==0){
        printf("%d ",j);
        trick[j]=1;
        }

}
printf("\n");
}

gettimeofday(&tim,NULL);
time_end=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);
time1=time_end-time_start;
printf("Execution time taken is %1f\n",time1);

return 0;
}



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

int dfs(int **a,int *visited,int v,int *d,int *f,int time,int s){
int i,j,u;

visited[s]=1;
d[s]=++time;


for(i=0;i<v;i++){

if(a[s][i]==1 && visited[i]==0){

time=dfs(a,visited,v,d,f,time,i);
    }

}

f[s]=++time;


return time;

}

int main(){
int **a,**b,i,j,v,*visited,*visited2,*d,*f,time=0,max,pos,*trick;
FILE *fp;

fp=fopen("input.txt","r");
printf("enter the number of vertices");
fscanf(fp,"%d",&v);

printf("the v is %d\n",v);
visited=(int *)calloc(v,sizeof(int));
visited2=(int *)calloc(v,sizeof(int));
trick=(int *)calloc(v,sizeof(int));

d=(int *)calloc(v,sizeof(int));
f=(int *)calloc(v,sizeof(int));

a=(int **)calloc(v,sizeof(int *));

for(i=0;i<v;i++){
a[i]=(int *)calloc(v,sizeof(int));
}

b=(int **)calloc(v,sizeof(int *));

for(i=0;i<v;i++){
b[i]=(int *)calloc(v,sizeof(int));
}

for(i=0;i<v;i++){

    for(j=0;j<v;j++){

        fscanf(fp,"%d",&a[i][j]);
        //b[j][i]=a[i][j];

    }
}

for(i=0;i<v;i++){

    for(j=0;j<v;j++){
        //b[i][j]=a[j][i];
        printf("%d ",a[i][j]);

    }printf("\n");
}

printf("\n\n");

for(i=0;i<v;i++){
if(visited[i]==0)
dfs(a,visited,v,d,f,time,i);
}

for(i=0;i<v;i++){

    for(j=0;j<v;j++){
        b[i][j]=a[j][i];
        printf("%d ",b[i][j]);

    }printf("\n");
}


for(i=0;i<v;i++){
printf("%d  %d %d \n",i,d[i],f[i]);
}

printf("\n\n\n");
printf("the components are :\n");
for(i=0;i<v;i++){

max=-1;
for(j=0;j<v;j++){
if(f[j]>max && visited2[j]==0){
max=f[j];
pos=j;
}

}

if(max==-1)
break;

if(visited2[pos]==0)
dfs(b,visited2,v,d,f,time,pos);

for(j=0;j<v;j++){
if(visited2[j]==1 && trick[j]==0){
printf("%d,",j);
trick[j]=1;

}

}
printf("\n");
}
return 0;
}



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

int dfs(int **a,int *visited,int v,int *d,int *f,int time,int s){
int i,j,u;

visited[s]=1;
d[s]=++time;

for(i=0;i<v;i++){

if(a[s][i]==1 && visited[i]==0){

time=dfs(a,visited,v,d,f,time,i);
    }

}

f[s]=++time;

return time;

}


input.txt   
5
0 4 3 0 0
7 0 9 0 0
0 0 0 2 0
0 0 0 0 8
0 0 6 0 0

   

Related Posts