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 }