add alternative approach from 2013-01
[synclust.git] / src / sources / connexity.c
1 #include "sources/connexity.h"
2 #include <cgds/Stack.h>
3 #include <stdlib.h>
4 #include "sources/utils/boolean.h"
5
6 int* getConnectedComponents_core(int** NIix, int* lengthNIix, int n)
7 {
8 int* cc = (int*)calloc(n,sizeof(int));
9 Stack* toBeExplored = stack_new(int);
10 int curInd = 0, nextInd;
11 bool* alreadyExpanded = (bool*)calloc(n,sizeof(bool));
12
13 // while the entire graph hasn't been visited
14 while (S_TRUE)
15 {
16 int label = curInd+1;
17 cc[curInd] = label;
18 stack_push(toBeExplored, curInd);
19
20 // while new elements are discovered in current component,
21 // mark them as expanded and stack their neighbors
22 while (!stack_empty(toBeExplored))
23 {
24 stack_top(toBeExplored, nextInd);
25 stack_pop(toBeExplored);
26 cc[nextInd] = label;
27
28 for (int j=0; j<lengthNIix[nextInd]; j++)
29 {
30 if (!alreadyExpanded[NIix[nextInd][j]])
31 stack_push(toBeExplored, NIix[nextInd][j]);
32 }
33 alreadyExpanded[nextInd] = S_TRUE;
34 }
35
36 // curInd is set to the next unexplored index (if possible)
37 for (int i=0; i<n; i++)
38 {
39 if (cc[i] == 0)
40 {
41 curInd = i;
42 break;
43 }
44 }
45 if (cc[curInd] != 0)
46 break;
47 }
48
49 free(alreadyExpanded);
50 stack_destroy(toBeExplored);
51
52 return cc;
53 }