Bron-Kerbosch Algorithm not working as expected

285 views Asked by At

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

0

There are 0 answers