Discussion :

[moine_ponce]

Bonjour à tous.

Je suis en train de programmer un algorithme de Dijkstra dont le graphe est représenté par listes d'adjacence, et c'est avec ces listes que j'ai un problème.

Le programme devra à terme appliquer l'algorithme de Dijkstra sur des graphes différents à l'intérieur d'une boucle. C'est à dire qu'à chaque itération, on efface le graphe de l'itération précédente et on en crée un nouveau.

Seulement voilà, je ne sais pas pourquoi mais de temps en temps, au bout d'un nombre totalement aléatoire d'itérations, le programme plante lors de la désallocation d'une des listes.

Graphe.h :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
struct liste{
    int id;
    double poids;
    liste *suiv;
};
 
class Graphe{
    public:
        Graphe();
        Graphe(int t);
        ~Graphe();
        int taille;
        liste *Sommets;
        void afficherSommets();
        int ajouterArc(int source, int id, double p);
        liste *creerSommet(int s, double p);
};

Graphe.cpp :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
// Constructeur par défaut
Graphe::Graphe(){
    taille=0;
    Sommets = NULL;
}
 
// Constructeur par valeurs
Graphe::Graphe(int t){
    taille = t;
    Sommets = new liste[taille];
    for(int i=0; i<taille; i++){
        // -1 = pas de sommet
        Sommets[i].id = -1;
        Sommets[i].poids = -1;
        Sommets[i].suiv = NULL;
    }
}
 
// Destructeur
Graphe::~Graphe(){
    for(int i=0; i<taille; i++){
        liste *l;
        l = &Sommets[i];
        liste *tmp;
        while(l!=NULL){
            tmp = l->suiv;
            delete l; // <- C'est ici que ça semble coincer
            l = tmp;
        }
    }
    delete [] Sommets;
}
 
// Affichage de la liste des sommets
void Graphe::afficherSommets(){
    liste *l;
    cout << "________________________________" << endl;
    cout << "Liste des Sommets : taille = " << taille << endl;
    for(int i=0; i<taille; i++){
        l = &Sommets[i];
        cout << "Sommet " << i << " : " << endl;
        while(l!=NULL){
            cout << "\t [" << l->id << "] " << l->poids << endl;
            l = l->suiv;
        }
    }
    cout << "________________________________" << endl;
}
 
// Création d'un sommet
liste *Graphe::creerSommet(int s, double p){
    liste *r = new liste;
    r->id = s;
    r->poids = p;
    r->suiv = NULL;
    return r;
}
 
// Ajout d'un arc
int Graphe::ajouterArc(int source, int id, double p){
    // liste des sommets adjacents au sommet source
    liste *tmp = &Sommets[source];
    // Si la liste ne contient aucun sommet
    if(tmp->id==-1){
        // On ajoute le premier sommet
        Sommets[source].id = id;
        Sommets[source].poids = p;
        Sommets[source].suiv = NULL;
        return 0;
    }
    // Sinon
    else{
        // Si le sommet existe déjà
        if(tmp->id==id)
            // Sortie (erreur)
            return -1;
        // On ajoute le sommet à la suite de la liste
        while (tmp->suiv!=NULL){
            // Si le sommet existe déjà
            if(tmp->id==id){
                // Sortie (erreur)
                return -1;
            }
            tmp = tmp->suiv;
        }
        // Ajout de l'arc
        tmp->suiv = creerSommet(id, p);
        return 0;
    }
}

Le main boucle en allouant et désallouant un Graphe*. Et au bout d'un moment, une erreur survient.
Je vous donne un exemple avec un graphe généré aléatoirement :

Le graphe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Liste des Sommets : taille = 232
Sommet 0 : 
	 [118] 641.102
	 [214] 96.2249
(...)
Sommet 78 :
(...)
	 [25] 863.765
	 [166] 554.827
Sommet 79 : 
	 [60] 658.406
	 [226] 992.187
	 [214] 975.89
	 [73] 921.842
(...)

J'ai affiché les valeurs des éléments de la liste lors de la désallocation (dans le destructeur de Graphe ( sous la forme ( id | poids | suiv->id ) )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
(...)
	(25 | 863.765 | 166)
	(166 | 554.827 | NULL)
[79]---------------------------------
	(60 | 658.406 | 226)

Et le programme plante lors de la désallocation du premier élément du sommet n°79.

D'une manière générale, le programme plante toujours lors de la désallocation du premier élément d'une des listes (mais pas nécessairement la première liste, c'est complètement aléatoire).
Les itérations allocation/désallocation peuvent se succéder plusieurs fois avant de planter.

A la limite, je préfèrerai que ça plante tout le temps, mais le fait que ce soit de manière totalement aléatoire que rend complètement chèvre !!!
J'espère que vous pourrez m'aider.
Merci d'avance.

[bertry]

Salut,

Si tu utilisais les <list> de la STL ça te simplifierai la vie...

[Lucien63]

Tu créés tes sommets sous forme de tableaux de listes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Sommets = new liste[taille];

et d'autre Sommets avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

liste *r = new liste;

Dans la methode creerSommet

Le problème c'est qu'il ne ce delete pas de la même façon.

[moine_ponce]

Merci de ta réponse Lucien.
Mon raisonnement était le suivant : Sommets est un tableau dynamique qui contient les listes d'adjacence pour chaque sommets.
Chaque élément de chaque liste contient un pointeur vers l'élément suivant, et la méthode creerSommet() n'est appelée que pour attribuer le sommet suiv (de type liste*).

Bref, je me trompe surement en m'y prenant comme ça.

Comment puis-je résoudre ce problème ?

Renvoyer une liste au lieu d'une liste* dans creerSommet(), et affecter le pointeur suiv par l'instruction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

*(tmp->suiv) = creerSommet(id, p);

?

Créer le nouveau sommet en faisant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

liste *r = new liste[1];

?

Edit: Effectivement, le problème semble venir de là car le programme ne plante plus si je n'ajoute pas de sommet par la méthode creerSommets
Edit3:Au temps pour moi, ça plante aussi de la même manière si l'on ajoute pas de sommet. Le problème ne doit pas venir de là

Edit2: Aucune de ces 2 solutions ne marchent. J'ai essayé aussi une variante de la première en faisant tmp->suiv = &creerSommet(id, p).
La première possibilité fait planter à l'allocation. (mais pas forcément dès le premier appel de ajouterArc d'ailleurs).
La deuxième fait exactement la même chose qu'avant. Quelle est la différence entre new et new[taille] ?
Une idée ?

[moine_ponce]

Salut,

Si tu utilisais les <list> de la STL ça te simplifierai la vie...

Le reste du programme utilisera Qt. J'ai entendu dire que c'était pas très bon de mélanger les frameworks. C'est le cas ?

[gbdivers]

Bonjour

La STL n'est pas un framework mais une extension du langage C++. Il n'y a pas de problème de compatibilité. De plus, Qt founit des conteneurs équivalent à ceux de la STL (QVector, QList, etc.) et compatible avec les algorithmes de la STL.

Et pour les graphs, tu pourrais aussi utiliser Boost Graph.

Donc ne pas hésiter à utiliser ce qui existe et qui fonctionne.

[moine_ponce]

Ah ok merci !
Je vais jeter un coup d'oeil alors

[Lucien63]

Bon si on met ton constructeur suivie du destructeur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    taille = t;
    Sommets = new liste[taille];
    for(int i=0; i<taille; i++)
       {
 
        Sommets[i].id = -1;
        Sommets[i].poids = -1;
        Sommets[i].suiv = NULL; 
       }
 
    // ensuite :
 
    for(int i=0; i<taille; i++){
        liste *l;
        l = &Sommets[i];
        liste *tmp;
        while(l!=NULL){
            tmp = l->suiv;
            delete l; // <- C'est ici que ça semble coincer
            l = tmp;
        }
    }
    delete [] Sommets;

on voit bien qu'il y a des delete de trop.
tu as taille delete et un delete[]
pour un seul new[]