Bron-Kerbosch a powtarzające się kliki

Cześć, potrzebuje do pewnego zadania wyszukiwać maksymalne kliki w grafie za pomocą algorytmu Bron-Kerbosch. Na Wiki znalazłem opis algorytmu, zaimplementowałem według pseudokodu i o ile faktycznie wyszukuje maksymalne kliki to niektóre z nich wyświetla kilkukrotnie co nie powinno mieć miejsca więc przypuszczam że gdzieś mam błąd.

Proszę o zerknięcie w kod.

//  BronKerbosch1(P, R, X):
//     if P and X are both empty:
//         report R as a maximal clique
//     for each vertex v in P:
//         BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
//         P := P \ {v}
//         X := X ⋃ {v}

QVector<int> a{2, 5, 6};
QVector<int> b{1, 3, 5, 6, 7};
QVector<int> c{2, 4, 7};
QVector<int> d{3, 7, 8};
QVector<int> e{1, 2, 6};
QVector<int> f{1, 2, 5, 7};
QVector<int> g{2, 3, 4, 6};
QVector<int> h{4};

QMap<int, QVector<int>> graph{{1,a}, {2,b}, {3,c}, {4,d}, {5,e}, {6,f}, {7,g}, {8,h}};


QVector<int> P = QVector<int>::fromList(graph.keys());
QVector<int> R(0);
QVector<int> X(0);


QVector<int> intersection(QVector<int> x, QVector<int> y )
{
    QVector<int> result;
    std::sort(x.begin(), x.end());
    std::sort(y.begin(), y.end());
    std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result));

    return result;
}

QVector<int> append(QVector<int> x, int v )
{
    QVector<int> result(x);
    result.append(v);

    return result;
}

// main algorithm
void BronKerbosch(QVector<int> R, QVector<int> P, QVector<int> X)
{

    if( P.isEmpty() && X.isEmpty() ) {
        qDebug()<< "MAX CLIQUE: " << R;
        return;
    }

    for( int v : P ) {

        // N(v)
        QVector<int> N(graph.value(v));

        // BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        BronKerbosch(append(R, v), intersection(P, N), intersection(X, N));

        P.removeOne(v);
        X.append(v);
    }
}

Wywołanie

BronKerbosch(R, P, X);

I wyjście na konsoli

MAX CLIQUE:  QVector(1, 2, 5, 6)
MAX CLIQUE:  QVector(3, 2, 7)
MAX CLIQUE:  QVector(3, 7, 4)
MAX CLIQUE:  QVector(3, 7, 4)
MAX CLIQUE:  QVector(7, 2, 6)
MAX CLIQUE:  QVector(8, 4)
MAX CLIQUE:  QVector(8, 4)
MAX CLIQUE:  QVector(8, 4)
MAX CLIQUE:  QVector(8, 4)

Pytanie czemu klike {3, 7, 4} i {8, 4} wyświetla kilka razy?

uzywales debuggera?

Oczywiście, naprzemiennie z kartką i długopisem xd

WIdzę problem na wyjściu z konsoli

v =  7
N =  QVector(2, 3, 4, 6)
R =  QVector(3, 7)
P =  QVector(4)
X =  QVector(2)

v =  4
N =  QVector(3, 7, 8)
R =  QVector(3, 7, 4)
P =  QVector()
X =  QVector()
MAX CLIQUE:  QVector(3, 7, 4)


v =  7
N =  QVector(2, 3, 4, 6)
R =  QVector(3, 7)
P =  QVector(4)
X =  QVector(2)

v =  4
N =  QVector(3, 7, 8)
R =  QVector(3, 7, 4)
P =  QVector()
X =  QVector()
MAX CLIQUE:  QVector(3, 7, 4)

Czyli będąc w wierzchołku 3 algorytm wybiera 7, potem 4 i widząc że to klika ( brak kandydatów i wykluczonych ) wyświetla - to jest ok. Ale dalej cofa się z powrotem do wierzchołka numer 3 i ZNOWU WYBIERA WIERZCHOŁEK 7 a dalej 4 a on po powrocie powinien chyba dodać 7 do wykluczonych tak by nie wchodzić do niej ponownie.

Dziwne to dlatego że wydaje mi się że napisałem kod dokładnie według tego co było na wiki. Spróbuje poszukać dokładniejszego opisu algorytmu.

Ok, już mam.

Algorytm jest zaimplementowany prawidłowo, problem był w pętli for opartej na zakresie która dla klas kontenerowych Qt tworzy... kopie =-=
Zamieniłem to na foreach i działa prawidłowo.

@fasadin dzięki za zainteresowanie ;)