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.
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
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)
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;
}
