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:
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