Bron-Kerbosch C реализация

Question

У меня возникли проблемы с реализацией C-версии алгоритма Брон-Кербоша:

1- Я абсолютно не понимаю, как работает алгоритм. Я пытался найти ссылки в интернете, но все они безрассудны из-за ужасных реализаций примера algol и без объяснения каких-либо функций с произвольным названием, которые появляются в псевдокоде (например, P (N))

2. В Интернете я нашел несколько реализаций C++, но авторам не удалось вставить классы, используемые в коде, поэтому у меня остались переменные со страшным именем, которые я понятия не имею, даже какого они типа (например, compsub, nod, minnod, fixp, newne, newce).

Единственный код, который мне удалось перевести, - это SegFaulting. Можете ли вы помочь мне понять алгоритм / скажите, что я сделал неправильно в своем коде?

Некоторая полезная информация:

graph-> matrix является матрицей связности.

List_clear возвращает размер списка.

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

Для этой реализации диагональные элементы матрицы должны быть истинными, скажем, graph->matrix[i][i] для всех i должно быть истинным. Это немного необычно, и я полагаю, что в этом случае вы не просто временно назначаете им значение true, и это должно работать.