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