0

I implemented the BK algorithm (https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm) <- Without pivoting version in C++ but is not working as expected. The code is:

void UndirectedGraph::clique(vector<string> R, vector<string> P, vector<string> X) {
    // Revisa si están vacíos, lo que implicaría que hay un clique
    if (P.empty() && X.empty()){
        cout << "Clique found!" << endl;
        for (const auto& it: R)
            cout << it << " " << endl;
    }
    // Crea una copia de P para evitar problemas en el iterador
    vector<string> pCopy(P);
    for (const auto& v: pCopy){
        vector<string> unionSet;
        vector<string> intersectionSetPNv;
        vector<string> intersectionSetXNv;
        vector<string> neighborsP;
        vector<string> vVector = {v};
        // Obtiene los vecinos de P
        for (const auto& neighbors: users[v]) neighborsP.push_back(neighbors);
        // Obtiene la unión de R y U
        set_union(R.begin(), R.end(), vVector.begin(), vVector.end(), back_inserter(unionSet));
        // Obtiene intersección P y N(v)
        set_intersection(P.begin(), P.end(), neighborsP.begin(), neighborsP.end(), back_inserter(intersectionSetPNv));
        set_intersection(X.begin(), X.end(), neighborsP.begin(), neighborsP.end(), back_inserter(intersectionSetXNv));
        clique(unionSet, intersectionSetPNv, intersectionSetXNv);
        vector<string> PminusV;
        vector<string> XunionV;
        // Obtiene P - {v} y N u {v}
        set_difference(P.begin(), P.end(), vVector.begin(), vVector.end(), inserter(PminusV, PminusV.begin()));
        set_union(X.begin(), X.end(), vVector.begin(), vVector.end(), back_inserter(XunionV));

        P = vector<string> (PminusV);
        X = vector<string> (XunionV);
    }
}

Expected output cliques: A B C

A E

C B D F

E D

Actual output cliques: A B C

A E

C B D F

C D F <- This shouldn't be there

E D

A related question is here: Bron Kerbosch algorithm in c++ where the solution is to use a copy of P (which I am doing, although I don't completely understand why it is needed). The graph I tested it with was this:

enter image description here

Note: users is defined as a: map<string, vector<string>>, so users[v] is actually a vector containing all the neighbors of v.

Complete class implementation: https://pastebin.com/dRXrC0Rf

Code to reproduce the output once the class has been declared: https://pastebin.com/vV6ppunF

Miguel Duran Diaz
  • 302
  • 1
  • 3
  • 12
  • `void UndirectedGraph::clique(vector R, vector P, vector X)` -- Are you sure this declaration is correct? C++ is not Java. C++ uses value semantics, not reference semantics,. All of these vectors are passed by-value, meaning they are temporary. As soon as that function returns, all of that work you are doing inside that function disappears into a puff of smoke. – PaulMcKenzie Jul 22 '20 at 16:09
  • @PaulMcKenzie if I understood the algorithm correctly, it should not matter as I don't actually need to store those vectors. I do need to be them temporary because they are constantly changing with each call to the function. It's fine for them to "dissapear". – Miguel Duran Diaz Jul 22 '20 at 16:15
  • Honestly, what you stated doesn't make a lot of sense given the code. Unless you can show us which variable actually is updated *after* that function is called, all of that code does nothing except waste cycles. It is a `void` function, so nothing is returned, all 3 parameters are passed by value, not by reference, and those other variables within the function are local (maybe I missed one -- please show what it is). So where is the change occurring? – PaulMcKenzie Jul 22 '20 at 16:17
  • In addition, I am straining to look for any class members that may have been updated. But since you only posted a class member function, trying to flesh out where this could happen is very difficult. I see non-locals used (such as `users`), but they are only used for read-only purposes -- they are not changed. – PaulMcKenzie Jul 22 '20 at 16:26
  • @PaulMcKenzie You are right, nothing is actually changing. I just needed to report when a clique is maximal, which occurs when both P and X are empty. When that happens, I'm just happy reporting it printing to the console (according to the algorithm, if the condition is met, what R holds must be a maximal clique). So considering I just need to "see" the cliques, I don't actually need to change anything at all. – Miguel Duran Diaz Jul 22 '20 at 16:26
  • Well you should have in the code the output statements. There is none in the code you posted, thus gives the indication that the code is a big no-op. If that `clique` function also did similar, I wouldn't be surprised if a good optimizing compiler would just wipe away the last two-thirds of that function, following the [as-if](https://en.cppreference.com/w/cpp/language/as_if) rule in C++. – PaulMcKenzie Jul 22 '20 at 16:27
  • @PaulMcKenzie Added the complete code as an external URL to pastebin in case anyone is interested in seeing the complete class definition. – Miguel Duran Diaz Jul 22 '20 at 16:30

0 Answers0