# Strongly connected components, component graph, semiconnected graph and new graph from SCCs

I have written a program in C to do the following:

Read a matrix (in file format, first line you have the size, then next are the entries). This is done by the "input" function.

1. Find the strongly connected components using the kosaraju algorithm (the one that uses the transpose). Done by the "SCCmatrix":

+) Step 1: DFS all of the possible vertices, push them onto a stack +) Step 2: Pop from the stack, DFS but this time do it on the transpose graph

2. Find a similar graph that has the same SCCs as the original one, with the same component graph and with the lowest number of edges possible. Here is how I do it (done by "minSCC") :

+) Find the component graph (this is easy since we have found all of the SCCs)

+) In each of the SCC, to make the edges as low as possible, you just connect all the vertices in a cycle

+) Use the component graph to connect the vertices in each of the SCC to each other (of course make sure that only one vertice from a SCC can connect to a vertex of another SCC)

3. The final one is done by "semiconnected". Here, the program finds out if the input graph is semiconnected (for all pairs of vertices u,v we have a road from u to v or a road from v to u, not necessarily means that the two are directly connected). It does that by using the component graph, which has a topological structure. It uses the first SCC used in step 2 of the Kosaraju algorithm and DFS from there, if all components are reached then it is semiconnected.

My reasonings are correct, right? Also, I would like you to review on my C code, since I find it rather cumbersome, and it seems to me that I have been going the wrong way in structural programming lately (and give me some tips as well please!). I know these are very easy problems but I'm not very good at graphs and algorithms in general.

 #include <stdio.h>
#include <conio.h>

#define MAX 100
//int time = 0;

int input(int *matrix, int *N);

int SCCmatrix(const int *matrix, int N, int *result, int *component,int *num);

int dfs(const int *matrix, int N, int current, int num, int transpose,
int *index, int *count, int *result, int *component);

int minSCC(int N, const int *result, int *result2, int *componentG, int *num);

int quicksort(int *fin, int *index, int first, int last);

int semiconnected(int *component, int num);

int dfsSC(int *component, int num, int current, int *count, int *marked);

int main()
{
int matrix[MAX][MAX],N,result[MAX],i,j, result2[MAX][MAX],
component[MAX][MAX],num,yes;

input( (int *) matrix, &N);

for (i=0; i<N; i++)
for (j=0; j<N; j++)
component[i][j]=0;
SCCmatrix( (const int *) matrix, N, result,(int *) component, &num);

for (i=0; i<N; i++)
result[i]--;
for (i=0; i<N; i++)
for (j=0; j<N; j++)
result2[i][j] = 0;

minSCC(N, (const int *) result, (int *) result2, (int*) component, &num);

yes=semiconnected( (int*) component, num);
getch();
return 0;
}

int input(int *matrix, int *N)
{
FILE *f;
int i,j;
f = fopen("LTHONG.TXT","r");
fscanf(f,"%d",N);
for (i=0; i< (*N) ; i++)
for (j=0; j< (*N) ; j++)
fscanf(f,"%d",matrix + i*MAX + j);
fclose(f);
return 0;
}

int SCCmatrix(const int *matrix, int N, int *result, int *component, int *num)
{
int i,transpose, index[MAX], count=0, j, yes[MAX],number=0;
int dau, cuoi;
for (i=0; i<N; i++)
{
result[i]=-1, index[i]= -1;
yes[MAX]=0;
}

transpose = 0;
for (i=0; i<N; i++)
if (result[i]==-1)
{
dfs(matrix, N, i, number, transpose, index, &count,result,
component);
}

//quicksort(fin,index, 0, N-1);
transpose = 1,number=1;

for (i= N-1; i>=0; i--)
if (result[ index[i] ]==0)
{
dfs(matrix, N, index[i], number++, transpose, index,
&count, result, component);
}
*num = number-1;
return 0;
}

int dfs(const int *matrix, int N, int current, int num, int transpose,
int *index, int *count, int *result, int *component)
{
int next,i,*tmp;
//(*time)++;
//start[current] = (*time);
result[current] = num;
for (next=0; next<N; next++)
{
if (transpose==0)
{
if (result[next]!=-1)
continue;
tmp = ( (int*) matrix ) + current*MAX + next;
}
else
{
if (result[next]!=0)
{
if (result[current]!=result[next])
{
tmp = ( (int*) matrix) + next*MAX + current;
if ((*tmp)==1)
(*(component+ (result[next]-1)*MAX +
(result[current]-1) ))=1;
}
continue;
}
tmp = ( (int*) matrix )  + next*MAX + current;

}
if ( (*tmp)==0 )
continue;
//result[next]= num;
dfs(matrix, N, next, num, transpose, index, count , result, component);
}
//(*time)++;
if (transpose==0)
{
//fin[current]= (*time);
index[*count] = current;
(*count)++;
}
return 0;
}

int minSCC(int N, const int *result, int *result2,int *componentG, int *num)
{
int first[MAX],i,current[MAX], component, now, next,j;
for (i=0; i<N; i++)
{
first[i]=-1, current[i]=-1;
}
for (i=0; i<N; i++)
{
component = result[i];
if (first[ component ] == -1)
{
first  [component]= i;
current[component]= i;
continue;
}
now = current[component];
next = i;
( *(result2 + now * MAX + next) ) = 1;
current[component] = next;
}
for (i=0; i<N; i++)
{
component = result[i];
if (current[component]!= -1)
{
now = current[component];
next = first[component];
( *(result2 + now *MAX + next)) = 1;
}
}
for (i=0; i< (*num); i++)
for (j=0; j< (*num); j++)
{
if ( (*(componentG + i*MAX + j))==1 )
{
(*(result2 + first[i]*MAX + first[j] ))=1;

}
}

return 0;

}

int quicksort(int *fin, int *index, int first, int last)
{
int mid,pivot,tmp,i,j;
if (first>=last)
return 0;
i=first,j=last;
mid = i + (j-i)/2 ;
pivot = fin[ index[mid] ];
do
{
while (fin[ index[i] ] > pivot)
i++;
while (fin[ index[j] ] < pivot)
j--;
if (i<=j)
{
if (i< j)
{
tmp = index[i];
index[i] = index[j];
index[j] = tmp;
}
i++,j--;
}
}
while (i<=j);
quicksort(fin,index,first,j);
quicksort(fin,index,i,last);
return 0;

}

int semiconnected(int *component, int num)
{
int i,count=0,marked[MAX];
for (i=0; i< num; i++)
marked[i]=0;
dfsSC(component, num, 0, &count, (int*)marked);
if (count!=num)
return 0;
else
return 1;
}

int dfsSC(int *component, int num, int current, int *count, int *marked)
{
int next;
marked[current]=1;
(*count)++;
for (next=0; next< num; next++)
{
if (marked[next]==1)
continue;
if ( (*(component + current*MAX + next))==0)
continue;
dfsSC(component, num, next, count, marked);
}
return 0;
}


Always use {s and }.

On bigger codes, omitting these can cause really big problems that are not very easy to notice at first.

It's just better practice to put them there.

You don't really seem to have a definitive indentation size.

For some things, you indent a single space, which is way too little.

For other things, you indent 4 spaces, which is perfect.

I recommend that you stick with 4 spaces for everything.

Since your program is not accepting any command-line arguments, it is good practice to put void in the parameter section of main.

All that method declaring at the top of your code is very nice-ly formatted.

However, I believe that it is in the wrong space.

You should move all these declarations to their own header file.

This is highly debatable.

You should use the pre-increment operator, rather than the post-increment operator.

For example, this

++i


over this

i++

• Header file? But I thought it was prototyping? And there was only several functions so would it be a good choice? And I will try to use the pre-increment operator from now on :) Apr 20, 2015 at 12:10
• Please give me more specific reviews :) , like: is my choice of parameters for each function appropriate or do i have to remove some of them? Are my codes in the functions dfs and SCCmatrix good? Do they need some modifications?? Please I need to know these stuff because I am spending too much time figuring how to code it right! Apr 20, 2015 at 12:14
• @DangManhTruong In my answer, I aimed to cover how you C code was, not the content of it. I'm a little hesitant to try and review the content because I'm not very handy with algorithms and maths. However, I will start to look more into it and I will update my answer with more information. Apr 20, 2015 at 16:57