Алгоритм Брона-Кербоша не работает должным образом

Я реализовал алгоритм 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


person Miguel Duran Diaz    schedule 22.07.2020    source источник
comment
void UndirectedGraph::clique(vector<string> R, vector<string> P, vector<string> X) -- Вы уверены, что это заявление верно? С++ - это не Java. C++ использует семантику значений, а не семантику ссылок. Все эти векторы передаются по значению, то есть они являются временными. Как только эта функция возвращается, вся та работа, которую вы делаете внутри этой функции, исчезает в клубе дыма.   -  person PaulMcKenzie    schedule 22.07.2020
comment
@PaulMcKenzie, если я правильно понял алгоритм, это не имеет значения, поскольку мне на самом деле не нужно хранить эти векторы. Мне нужно, чтобы они были временными, потому что они постоянно меняются при каждом вызове функции. Это нормально, что они исчезают.   -  person Miguel Duran Diaz    schedule 22.07.2020
comment
Честно говоря, то, что вы сказали, не имеет большого смысла, учитывая код. Если вы не можете показать нам, какая переменная на самом деле обновляется после вызова этой функции, весь этот код ничего не делает, кроме ненужных циклов. Это функция void, поэтому ничего не возвращается, все 3 параметра передаются по значению, а не по ссылке, а остальные переменные внутри функции являются локальными (может быть, я пропустил одну — пожалуйста, покажите, что это такое). Так где же происходит изменение?   -  person PaulMcKenzie    schedule 22.07.2020
comment
Кроме того, я стараюсь искать любых членов класса, которые могли быть обновлены. Но поскольку вы опубликовали только функцию члена класса, очень сложно выяснить, где это может произойти. Я вижу, что используются нелокальные имена (например, users), но они используются только для чтения — они не изменяются.   -  person PaulMcKenzie    schedule 22.07.2020
comment
@PaulMcKenzie Вы правы, на самом деле ничего не меняется. Мне просто нужно было сообщить, когда клика максимальна, что происходит, когда и P, и X пусты. Когда это происходит, я просто счастлив сообщить, что он печатает на консоли (согласно алгоритму, если условие выполнено, то, что R содержит, должно быть максимальной кликой). Так что, учитывая, что мне просто нужно увидеть клики, мне вообще не нужно ничего менять.   -  person Miguel Duran Diaz    schedule 22.07.2020
comment
Ну, вы должны иметь в коде операторы вывода. В опубликованном вами коде его нет, что указывает на то, что код не работает. Если бы эта функция clique также делала то же самое, я не удивлюсь, если бы хороший оптимизирующий компилятор просто стер последние две трети этой функции, следуя как если бы правило в C++.   -  person PaulMcKenzie    schedule 22.07.2020
comment
@PaulMcKenzie Добавлен полный код в виде внешнего URL-адреса в pastebin на случай, если кому-то интересно увидеть полное определение класса.   -  person Miguel Duran Diaz    schedule 22.07.2020