BronKerbosch Sans pivot : Probleme

Fermé
Magik - Modifié le 25 avril 2018 à 01:27
 Magik - 25 avril 2018 à 19:39
Bonjour,
Je dois trouver toutes les cliques maximales dans un graphe générer aléatoirement.
Je fais la matrice d'adjacence, puis je lance mon algo de BronKerbosch :

vector<int> intersect(vector<int> A, vector<int> B){
    vector<int> I;
    for(int i = 0; i<A.size(); i++){
        for(int j = 0; i<B.size(); i++){
            if(A[i]==B[j]) I.push_back(A[i]);
        }
    }
    return I;
}

vector<int> suppr(vector<int> A, int b){
    for(int i = 0; i<A.size(); i++){
        if(A[i]==b) A.erase(A.begin()+i);
    }
    return A;
}

vector<int> getV(int v){
    vector<int> V;
    for(int i = 0; i<n; i++){
        if(M_adj[v][i]==1) V.push_back(i);
    }
    return V;
}

void BronKerboschWithoutPivot(vector<int> R, vector<int> P, vector<int> X){
    if((P.size() == 0) && (X.size() == 0) && (R.size()>1)){
        printf("Clique maximale :");
        for (int i=0; i<R.size(); i++){ printf(" %d ", R[i]); }
        printf("\n");
        return;
    }

    vector<int> P1;
    for(int i = 0; i < P.size(); i++){ P1.push_back(P[i]);}

    for(int i = 0; i < P.size(); i++){
        int v = P[i];
        vector<int> V = getV(v);
        R.push_back(v);
        BronKerboschWithoutPivot(R,intersect(P1,V),intersect(X,V));
        R = suppr(R,v);
        P1 = suppr(P1,v);
        X.push_back(v);
    }
}

Cependant, cela me rend pas le résulat attendu et je ne trouve pas mon erreur.

Pouvez vous m'aider ?
Merci

A voir également:

1 réponse

J'ai trouvé mon erreur : j'avais fait un copié-collé d'un for() et j'ai oublié de modifié la variable dans toutes la conditions, resultat, je me retrouvé avec for(int j = 0; i<...; i++)
0