Bron Kerbosch algorithm in c++

Question

I've been practicing my C++ algorithm knowledge, and got stuck on the standard BK implementation. The algorithm outputs way too many cliques, and I doesn't seem to figure out why. I represented the graph as an adjacency list:

vector< list<int> > adjacency_list;

My BK function looks like:

void graph::BronKerbosch(vector<int> R, vector<int> P, vector<int> X){

  if (P.empty() && X.empty()){
    result_cliques.insert(R);
  }

  for (int node : P){

    vector<int> intersection = {}, intersectionX = {};

    //N(P)
    for (int nodeP : adjacency_list[node]){
      for (int node2 : P){
        if (nodeP == node2){
          intersection.push_back(nodeP);
        }   
      }

      //N(X)
      for (int node3 : X){
        if (nodeP == node3){
          intersectionX.push_back(nodeP);
        }
      }
    }

    R.push_back(node);
    BronKerbosch(R,intersection,intersectionX);
    P.erase(remove(P.begin(),P.end(),node),P.end());
    X.push_back(node);    

  }
}

I call this using:

void graph::run_BronKerbosch(){

  vector<int> R,P,X;

  for (int i=1; i < adjacency_list.size(); i++) {
    P.push_back(i);
  }

  BronKerbosch(R,P,X);

  cout << "................\nClassic: " << result_cliques.size() << endl;
  for (auto clique : result_cliques){
    cout << "(";
    for (int node : clique){
      cout << node <<" ";
    }    
    cout << ")\n";    
  } 

}

I am trying to implement the basic version of the algorithm, but I seem to be missing a detail here. Is the problem in:

for (int node : P){

Should I somehow use a copy of P for this first loop? (I've seen this in a related issue)

Thank you for any help.

How did you finally solve it? Where did you add this copy of P? — Miguel Duran Diaz, Jul 22 '20 at 17:20

Bathsheba · Accepted Answer · 2020-02-26T09:28:29.110

4

Yes you should take a copy, unless you reserve space in advance so you can guarantee there is no reallocation¹. (Note that the C++ foreach implementation boils down to a bunch of iterators under the hood.)

I'd recast to an old-fashioned for loop if I were you, iterating over the vector using an std::size_t (the super-pedants² would use a std::vector<int>::size_type) to index the vector element you're currently interested in. Terminate when the final element of P has been read.

References:

¹Iterator invalidation rules

²C++ for-loop - size_type vs. size_t

edited Feb 26 '20 at 09:28

answered May 03 '17 at 12:05

Bathsheba

231,907
34
361
483

Thanks for the insightful comment, if I understand correctly, something in the lines of: for(std::vector::size_type i = 0; i != v.size(); i++) { /* std::cout << someVector[i]; ... */ } should work? – sdgaw erzswer May 03 '17 at 12:51
That should be fine. `push_back` will not invalidate `i`. Even if `i` is on the last element. – Bathsheba May 03 '17 at 12:53
Works like a charm! Thanks. – sdgaw erzswer May 03 '17 at 12:56
@Bathsheba Why should he use a copy? I'm having a similar issue but can't understand why a copy is needed. – Miguel Duran Diaz Jul 22 '20 at 04:17

Bron Kerbosch algorithm in c++

1 Answers1

Linked