Bron-Kerbosch C implementation

Question

I'm having some problems implementing a C version of the Bron-Kerbosch algorithm:

1- I have absolutely no understanding of how the algorithm works. I tried to find references on the internet but all of them are crappy with terrible algol example implementations and no explanation whatsoever of some arbitrarily named functions that appear on the pseudo-code (such as P(N) )

2- I found some C++ implementations on the internet but the authors failed to put in the classes used in the code so i'm left with terribly named variables that i have no idea even what type they are (such as compsub, nod, minnod, fixp, newne, newce).

The one code i was able to translate is SegFaulting. Can you please help me understand the algorithm/tell me what i did wrong in my code?

Some useful info:

graph->matrix is the connectivity matrix.

List_clear returns the size of the list.

int serial (Graph* graph) { 
  int i; 
  int* all = (int *) malloc (graph->size * sizeof (int) ); 
  List compsub;

  List_init (&compsub);

  for (i = 0; i < graph->size; i++)  
all[i] = i; 
  bkv2 (graph, &compsub, all, 0, graph->size);
  free (all); 
  return List_clear (&compsub);
} 

// recursive function version 2 of Bron-Kerbosch  algorithm 
void bkv2 (Graph* graph, List* compsub, int* oldSet, int ne, int ce ) {  
  int* newSet = (int *) malloc (ce * sizeof (int) ); 
  int nod, fixp; 
  int newne, newce, i, j, count, pos, p, s, sel, minnod; 

  minnod = ce; 
  nod = 0; 
  // Determine each counter value and look for minimum 
  for ( i = 0 ; i < ce && minnod != 0; i++) { 
p = oldSet[i]; 
count = 0; 

// Count disconnections 
for (j = ne; j < ce && count < minnod; j++) 
  if ( !(graph->matrix[p][oldSet[j]]) ) { 
    count++; 
    // Save position of potential candidate 
    pos = j; 
  } 
// Test new minimum 
if (count < minnod) {
  fixp = p; 
  minnod = count; 
  if (i < ne)
    s = pos; 
  else { 
    s = i; 
    // pre-increment 
    nod = 1; 
  } 
} 
  } 
  // If fixed point initially chosen from candidates then 
  // number of diconnections will be preincreased by one 
  // Backtrackcycle 
  for (nod = minnod + nod; nod >= 1; nod--) { 
// Interchange 
p = oldSet[s]; 
oldSet[s] = oldSet[ne];   sel = oldSet[ne] = p; 
// Fill new set "not" 
newne = 0; 
for ( i = 0 ; i < ne ; i++) 
  if (graph->matrix[sel][oldSet[i]] ) 
    newSet[newne++] = oldSet[i]; 

// Fill new set "cand" 
newce = newne; 
for (i = ne+1; i<ce; i++) 
  if (graph->matrix[sel][oldSet[i]] ) 
    newSet[newce++] = oldSet[i]; 

// Add to compsub 
List_add (compsub, sel); 
if (newce == 0) { 
  // found a max clique 
  List_print(compsub); 

} else if (newne < newce) 
  bkv2 ( graph, compsub, newSet, newne, newce ); 

// Remove from compsub 
List_remove(compsub); 

// Add to "not" 
ne++; 
if (nod > 1) 
  // Select a candidate disconnected to the fixed point 
  for ( s = ne ; graph->matrix[fixp][oldSet[s]] ; s++) 
    ; 
// nothing but finding s  

  } /* Backtrackcycle */ 
  free (newSet); 
} 

Answer 1

For this implementation, the diagonal elements of the matrix has to be true, say, graph->matrix[i][i] for all i should be true. It is a bit unusual and I guess your input is not, in that case, just temporarily assign them to true and it should work.