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[]

[moine_ponce]

Oui j'avais vu, j'avais rajouté de delete [] Sommets après. Il se trouve que ça change rien si je l'enlève.
Et puis il y a les listes d'adjacence à libérer d'une part, et le tableau des listes d'autre part. Non ?

[gbdivers]

C'est quand même très casse-gueule de tester différentes combinaison de new[] et delete[] en espérant que ça tombe en marche sans vraiment maîtriser ce que l'on fait.
C'est une raison de plus pour utiliser les fonctionnalités du C++ qui facilite la vie.

[bertry]

Salut,

Si tu tiens vraiment à utiliser une liste de ta fabrication, alors implémentes une classe liste complète avec son constructeur, son destructeur, et ses fonctions pour ajouter et enlever des nœuds... Tu débug tout ça...Et quand ça tourne rond, alors là tu l'utilise dans ton Dijkstra ( mais pas avant!!! ).

Parce que là, tu n'as même pas l'air de savoir comment utiliser correctement une liste, alors... en implémenter une toi même en même temps que ton algo !!!

C'est quand même très casse-gueule de tester différentes combinaison de new[] et delete[] en espérant que ça tombe en marche sans vraiment maîtriser ce que l'on fait.

C'est clair!!

Regardes là : Implémentation avec une structure chainée et là : Liste chainée...

[moine_ponce]

Oui oui ne t'inquiète pas je commence par le début
J'ai pas encore commencé le Dijkstra, pour l'instant uniquement ma classe avec constructeur et destructeur (qui me pose déjà des problèmes).

Je suis en train de regarder boost. J'aurai moins de choses à coder (et ce sera surement mieux fait ), mais c'est bigrement compliqué toutes ces variables là .

Ben après de la doc sur les listes j'en ai lu pas mal. C'est juste que pour le destructeur je me suis dit qu'il fallait peut être libérer le tableau en plus des listes comme je l'ai dit dans mon post précédent. Et comme je vous l'ai dit, mon problème ne vient pas de là.

Mis à part ce delete [] Sommets, qu'est ce que j'ai fait de travers ?

[gbdivers]

Mis à part ce delete [] Sommets, qu'est ce que j'ai fait de travers ?

Plusieurs erreurs peut être :

- pensez que tu ferais mieux que l'existant (ok, j'arrête d'insister, tu risques de saturer)

- donnez toutes les responsabilités à la class Graph : ajouter un élément dans liste et supprimer les éléments de liste. Ce sont des responsabilités qui doivent être prises en charge par ta classe liste (nom qui est mal choisit au fait puisque cette classe ne représente pas une liste mais un élément d'une liste)

- Sinon, je n'ai pas vu de problème sur les new/delete et new[]/delete[] (mais je les utilises jamais donc quelque chose aurait pu m'échapper)

[moine_ponce]

Ouais pour le destructeur de liste j'en avais fait un au départ. Mais évidemment ça marchais pas bien non plus .

Penser que je peux faire mieux que l'existant ?

A vrai dire je connais pas trop la STL, j'ai déjà vaguement utilisé les maps mais ça se limite à ça.

Bon il se trouve que Dijkstra est déjà implémenté dans boost, et il est évident que je ferai pas mieux qu'eux

Je suis donc en train de lire et tester pas mal de trucs avec boost. Mais mon problème c'est qu'à terme, le programme devra supprimer le graphe et en créer un nouveau à chaque itération. En fait ce qui m'inquiète, c'est la mémoire. D'où l'utilité d'avoir un pointeur sur une structure (en théorie XD) facile à désallouer, pour libérer la mémoire.

Enfin bref, dès que j'aurai apprivoisé boost, je ferai des tests pour voir comment ça se comporte lors de réaffectations en masse.

[bertry]

A vrai dire je connais pas trop la STL, j'ai déjà vaguement utilisé les maps mais ça se limite à ça.

Alors commence par bosser sur le STL avant de te mettre à BOOST!! Ne mets pas la charrue avant les bœufs.

[ealex]

Bonjour,

sans rien enlever aux remarques fait précédemment sur l'utilisation de la STL etc.

L'utilisation de new/delete et new[] / delete[] est presque correcte.

Ta structure de donnée est un tableau de liste.

Or dans ton 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
 
// Destructeur
Graphe::~Graphe(){
    for(int i=0; i<taille; i++){
        liste *l;
        l = &Sommets[i]; <- pointe sur l element courant du tableau
        liste *tmp;
        while(l!=NULL){
            tmp = l->suiv;
            delete l;
            l = tmp;
        }
    }
    delete [] Sommets;
}

Lors du parcours de la liste chainée pour la destruction, tu détruit le premier élément (qui ne fait pas partie de la liste mais du tableau).
-> donc double desallocation avec le delete[] Sommets.

Il faut donc commencer à détruire à partir du premier élément de la liste et donc remplacer :

Code :

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

l = &Sommets[i];

par :

Code :

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

l = Sommets[i].suiv;

Voila qui devrai résoudre le problème de desallocation.

Mais effectivement regarde l'utilisation des conteneurs de la STL qui te simplifie grandement les choses (l'allocation/desalocation de la mémoire, parcours,...), sinon autant faire du C.

Pour ce qui est de la réallocation du graph à moins que ton graph soit énorme cela ne devrai pas poser de problème.

[moine_ponce]

Merci de ta réponse ealex!
Ben du coup j'ai fait un truc en utilisant Boost Graph. Le problème c'est que l'agorithme de Dijkstra est incroyablement lent.
Dans un premier temps, j'avais regardé avec ce code :
http://www.nimbustier.net/publications/djikstra/
Et l'algorithme tourne en un truc de l'ordre de 10^-6 secondes, alors que le Dijkstra de la BGL tourne en 10^-3 (soit 100 fois plus lent !!).
Enfin l'intérêt, c'est surtout qu'il n'y a pas de fuite de mémoire. Le code dont j'ai mis le lien souffre de fuite de mémoire, donc je voulais utiliser le même genre de méthode mais en modifiant un peu les structures.
Je vais essayer la désallocation comme tu as dit
Merci !!

[moine_ponce]

Bon c'est bon il n'y a plus de problème !
Merci encore ealex. Effectivement, je n'avais pas réaliser que le premier élément de la liste n'est en fait pas un élément de la liste mais un élément du tableau qui pointe vers la liste (d'où le problème). Merci pour ta solution et ton explication !

Merci aussi aux autres, de m'avoir recommandé la STL.
Je ne sais pas encore laquelle des deux méthodes je vais utiliser, mais en tout cas mon problème est résolu.
Sachez tout de même que je ne m'amuse pas à réinventer la roue par pur plaisir ou masochisme
C'est juste que je ne connaissais pas Boost Graph. D'ailleurs pour une librairie qui s'appelle boost, je suis assez déçu de ses performances :/ (ce qui me fait hésiter à poursuivre cette implémentation).
En tout cas merci à tous pour votre aide !