Я реализовал алгоритм BK (https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm) ‹- Без сводной версии на C++, но работает не так, как ожидалось. Код:
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);
}
}
Ожидаемый выход кликов: A B C
A E
C B D F
E D
Фактические выходные клики: A B C
A E
C B D F
C D F ‹- Этого не должно быть
E D
Связанный с этим вопрос здесь: алгоритм Брона Кербоша в С++, где решение заключается в использовании копия P (что я и делаю, хотя не совсем понимаю, зачем это нужно). График, который я тестировал, был таким:
Примечание: users определяется как: map<string, vector<string>>
, поэтому users[v] на самом деле является вектором, содержащим всех соседей v.
Полная реализация класса: https://pastebin.com/dRXrC0Rf
Код для воспроизведения вывода после объявления класса: https://pastebin.com/vV6ppunF
void UndirectedGraph::clique(vector<string> R, vector<string> P, vector<string> X)
-- Вы уверены, что это заявление верно? С++ - это не Java. C++ использует семантику значений, а не семантику ссылок. Все эти векторы передаются по значению, то есть они являются временными. Как только эта функция возвращается, вся та работа, которую вы делаете внутри этой функции, исчезает в клубе дыма. - person PaulMcKenzie   schedule 22.07.2020void
, поэтому ничего не возвращается, все 3 параметра передаются по значению, а не по ссылке, а остальные переменные внутри функции являются локальными (может быть, я пропустил одну — пожалуйста, покажите, что это такое). Так где же происходит изменение? - person PaulMcKenzie   schedule 22.07.2020users
), но они используются только для чтения — они не изменяются. - person PaulMcKenzie   schedule 22.07.2020clique
также делала то же самое, я не удивлюсь, если бы хороший оптимизирующий компилятор просто стер последние две трети этой функции, следуя как если бы правило в C++. - person PaulMcKenzie   schedule 22.07.2020