graph-theorypseudocodenon-recursive

Iterative version of the Bron–Kerbosch algorithm with pivoting


I need much a correct pseudocode of Bron–Kerbosch algorithm (it enumerates all maximal cliques in an undirected unweighted graph). I need iterative (non-recursive) solution with a stack. And the version of the algorithm should be "with pivot" rather than "basic". (Both basic and pivot versions are considered in the Wikipedia article linked.)

I've found an iterative counterpart of the "basic" version, and it worked fine when I implemented it. But I need likewise the version "with pivot". To my shame, I find it always difficult for me to turn a recursive syntax into an iterative one. So can you help, please?

Update. Below is a pseudocode (iterative, with pivoting) I've picked, after an extensive search, from one article.

Iterative_BK_pivot(P, Q)
Stack := null
Stack.push({ }, P, { }, Q); /*i.e., initial R, P, X, Q (P is the collection of vertices; Q = ?)
while Stack is not empty do
     R, P, X,Q := Stack.pop();
     if P and X are both empty then
           report R as a maximal clique
     if Q is not empty then
          v := some vertex in Q
          Stack.push(R, P \ {v}, X ⋃ {v}, Q \ {v})
          choose a pivot vertex u of P (or of P ⋃ X) /*Say, the vertex with the largest degree of neighbours
          Stack.push(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v), P \ N(u))

When I tried to implement it, it did not work. Either the pseudocode is incorrect, or my undertanding of it, or my code. After plenty of iterations, I am getting empty P in the line "choose a pivot vertex u" and so cannot pick u. Plus to this, I am not sure how initial set Q should be defined at the beginning (one any vertex or all the vertices?).

I would really appreciate help. Thank you.


Solution

  • My trial and error - after the comment left by @JanneKarila here - produced me the following pseudocode. When implemented, it works correctly (i.e., always the same list of maximal cliques as the "basic" version). When the graph is dense, the "pivot" version is considerably faster.

    Iterative_BK_pivot(P)
     Stack := null
     Stack.push({}, P, {}, {})
     while Stack is not empty do
         R, P, X, Q := Stack.pop()   //poped Q is a single vertex, the stored q
         if P and X are both empty then
            report R as a maximal clique
         else
            Choose* pivot vertex q from P ⋃ X  //the new q to store if P \ N(q) isn't empty
            if P \ N(q) is not empty then
               v := some vertex in P \ N(q) 
               Stack.push(R, P \ {v}, X ⋃ {v}, q)
               Stack.push(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v), q)
    
    * Choose pivot vertex q from P ⋃ X - either the vertex with maximal
    degree (i.e. number of neighbours) or a randomly chosen.