Discussion :

[maxHesse]

Bonjour,

Je débute tout juste en POO en C++ et je suis confronté à un petit problème.
Je souhaite créer une classe Graphe et faire quelques opérations dessus.
Ma classe graphe a 2 attributs:
- une liste (vector) de Noeuds
- un liste (vector) d'Arêtes

Noeud et Arête sont des classes.

Ma classe Noeud n'a qu'un attribut (pour le moment) qui est son identifiant.
2 méthodes permettent de renvoyer son adresse et son identifiant (il y aura potentiellement d'autres attributs, j'insiste)

Ma classe Arête a 2 attributs:
- un poids (entier)
- un tableau de taille 2 de pointeurs sur Noeud
et une méthode d'affichage ==> (id Noeud1, id Noeud2, poids) qui me permet d'utiliser l'operateur <<

Le constructeur d'Arête prend 'en entrée' 2 noeuds et un poids.

Le constructeur de Graphe prend en entrée un nombre de noeuds et d'arêtes.
Je commence par 'construire' mon ensemble de noeuds, puis mon ensemble d'arêtes.
Ma classe possède également une méthode d'affichage (affichage des arêtes) qui me permet d'utiliser l'opérateur <<.

Le problème vient quand je cherche à afficher mon graphe.
En lieu et place d'avoir mes 'id noeuds', j'ai, par moments, une adresse qui s'affiche.
Par exemple, pour un graphe de 10 noeuds, et 4 arêtes, je peux voir ça:
(0,0,3)
(4489296,4692064,8)
(4489296,4692064,9)
(4489296,4692064,6)

Je présume qu'il s'agit d'adresse, mais je n'en suis pas sûr.

A première vue, voyez-vous une erreur possible?

je peux transmettre mon code.

J'ai fait un test en transformant, dans la classe Arete, le tableau de pointeurs sur Noeuds en tableau de Noeuds. Avec les modifications qu'il convient, l'affichage est bon.

Merci !

[Iradrille]

Hello,

Probablement ta méthode d'affichage qui est mauvaise.

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
struct Arrete {
   int poids;
   std::array<Noeud*, 2> noeuds;
 
   friend std::ostream& operator<<(std::ostream& os, const Arrete& arr) {
      // Tu as surement
      os << "(" << arr.noeuds[0] << ", " << << arr.noeuds[1] << ", " << arr.poids << ")" << std::endl;
 
      // Au lieu de
      os << "(" << arr.noeuds[0]->id << ", " << << arr.noeuds[1]->id << ", " << arr.poids << ")" << std::endl;
 
      // Ou si les Noeuds possèdent une méthode d'affichage
      os << "(" << *arr.noeuds[0] << ", " << << *arr.noeuds[1] << ", " << arr.poids << ")" << std::endl;
 
      return os;
   }
};

Si c'est le cas, le fait que ça affiche 0 est inquiétant, il y à des pointeurs nuls qui se baladent.

Cela peut aussi être les id qui ne sont pas initialisés.

Avec un bout de code ce sera plus simple de trouver le problème.

[Bousk]

Bonjour,

pour détecter un problème de code, il faut... présenter du code.
Ma boule de crystal est pas super performante mais ça ressemble beaucoup à des valeurs non initialisées plutôt.

[maxHesse]

Bonjour,

Merci pour ces premières réponses.
Je vous donne donc mon code pur y voir plus clair

Arete.h

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
class Arete
{
public:
    Arete( Noeud noeudDepart, Noeud noeudFin,int poids=1);
    void afficherArete(std::ostream& flux);
 
private:
    Noeud* m_noeudsExtremites[2];
    int m_poids;
};
 
std::ostream& operator<<(std::ostream& flux,  Arete areteAAfficher);

Arete.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
 
Arete::Arete(Noeud noeudDepart,Noeud noeudFin,int poids)
{
    m_poids=poids;
    m_noeudsExtremites[0]=noeudDepart.getAdresse();
    m_noeudsExtremites[1]=noeudFin.getAdresse();
}
 
void Arete::afficherArete(std::ostream& flux)
{
   flux << "(" << m_noeudsExtremites[0] -> getIdentifiant() << ","  << m_noeudsExtremites[1] -> getIdentifiant() << "," << m_poids << ")" << endl;
}
 
ostream& operator<<(std::ostream& flux,  Arete areteAAfficher)
{
    areteAAfficher.afficherArete(flux);
    return flux;
}

Noeud.h

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
class Noeud
{
public:
    Noeud(int id=1);
    int getIdentifiant();
    Noeud* getAdresse();
 
private:
    int m_idNoeud;
 
};

Noeud.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
 
Noeud::Noeud(int id)
{
    m_idNoeud=id;
}
 
Noeud* Noeud::getAdresse()
{
    return this;
}
 
int Noeud::getIdentifiant()
{
    int id=m_idNoeud;
    return m_idNoeud;
}

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
 
class Graphe
{
public:
    Graphe(int nbNoeuds=2, int nbAretes=1);
    void afficherGraphe(std::ostream& flux);
 
private:
    void nodesGeneration(int nbNoeuds);
    void edgesGeneration(int nbAretes);
    std::vector <Noeud> m_ensNoeuds;
    std::vector <Arete> m_ensArete;
};
 
bool presenceAreteDansListe(int noeudsInseres[][2], int taille, int noeudDepart, int noeudFin);
std::ostream& operator<< (std::ostream& flux, Graphe grapheAAfficher);

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
 
Graphe::Graphe(int nbNoeuds, int nbAretes)
{
    // we create the set of nodes
    nodesGeneration(nbNoeuds);
 
    // we create a set of Edges
    edgesGeneration(nbAretes);
}
 
void Graphe::nodesGeneration(int nbNoeuds)
{
    for (int i(0); i<nbNoeuds; i++)
    {
        m_ensNoeuds.push_back(Noeud(i));
    }
}
 
void Graphe::edgesGeneration(int nbAretes)
{
    // Definitions
    int nbAretesRestantes(nbAretes);
    int noeudsCandidats[2];
    int noeudsInseres[nbAretes][2];
    int poids(0);
    bool presenceArete(true);
 
    // Initialization
    srand(time(0));
 
    // Treatment
    do
    {
        do
        {
            noeudsCandidats[0]=rand()%m_ensNoeuds.size();
            noeudsCandidats[1]=rand()%m_ensNoeuds.size();
            presenceArete=presenceAreteDansListe(noeudsInseres,nbAretes-nbAretesRestantes,noeudsCandidats[0], noeudsCandidats[1]);
        }
        while(presenceArete);
 
        poids=rand()%10 +1;     // random number between 1 and 10
        m_ensArete.push_back(Arete(m_ensNoeuds[noeudsCandidats[0]], m_ensNoeuds[noeudsCandidats[1]],poids));
        noeudsInseres[nbAretes-nbAretesRestantes][0]=noeudsCandidats[0];
        noeudsInseres[nbAretes-nbAretesRestantes][1]=noeudsCandidats[1];
        nbAretesRestantes-=1;
    }
    while (nbAretesRestantes>0);
}
 
void Graphe::afficherGraphe(std::ostream& flux)
{
    for (int i(0); i<m_ensArete.size(); i++)
    {
        flux << m_ensArete[i];
    }
}
 
bool presenceAreteDansListe(int noeudsInseres[][2], int taille, int noeudDepart, int noeudFin)
{
    bool resultat(false);
    for (int i(0); i<taille; i++)
    {
        if((noeudsInseres[i][0]==noeudDepart && noeudsInseres[i][1]==noeudFin) ||
           (noeudsInseres[i][1]==noeudDepart && noeudsInseres[i][0]==noeudFin))
        {
            resultat=true;
            break;
        }
    }
 
    return resultat;
}
 
ostream& operator<< (ostream& flux, Graphe grapheAAfficher)
{
    grapheAAfficher.afficherGraphe(flux);
    flux;
}

Voilà, j'espère qu'avec ça vous pourrez m'aider

[maxHesse]

En fait, je crois que j'ai trouvé.

Au moment où j'ajoutais mes arêtes, je ne passais que par valeur les noeuds extrémités et pas par référence.

Voilà qui est fait et qui fonctionne bien!

Merci

[koala01]

Salut,

Il faut quand même faire attention à un truc avec la méthode que tu utilises (utiliser un std:::vector<Node> pour maintenir les noeuds en vie, maintenir l'adresse des noeuds dans les arrêtes) : tu ne peux plus envisager de rajouter un noeud dans ton graphe une fois que tu as décidé de commencer à créer tes arrêtes.

En effet, les mécanismes d'ajout d'éléments dans un std::vector font que tous les éléments sont régulièrement copiés et / ou déplacés en mémoires, parce que le vecteur doit augmenter le nombre d'éléments qu'il peut contenir.

Ce n'est pas forcément un problème si tu t'assures que tu ne devras plus rajouter de noeuds une fois que tu commences à en prendre les adresses, mais cela va placer une restriction forte quant à la manière dont tu vas utiliser ta classe graphe. Le code suivant pourrait alors poser problème:

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
int main(){
    Graphe g;
    /* Tu as sans doute oublié quelques fonctions dans la classe Graphe, dont celles
     * permettant d'ajouter un noeud ou une arrête :D
     */
    g.addNode(/* .... */);
    g.addNode(/* .... */);
    g.addNode(/* .... */);
    g.addEdge(/* .... */);
    g.addEdge(/* .... */);
    g.addEdge(/* .... */);
    /* jusqu'à présent, tout allait bien, mais */
    g.addNode(/* .... */); //OUPSSS
    /* on peut craindre le redimensionnement du vecteur de noeuds, toutes les arrêtes
     * seraient alors composées d'adresses invalides
     */
    return 0;
}

Attention, je ne veux pas dire qu'il soit anormal de subir cette restriction! Il peut être tout à fait cohérent de ne pas pouvoir agir de la sorte. Je voulais juste attirer ton attention dessus .

Si cette restriction pose un problème, il est toujours possible de s'y prendre autrement pour la supprimer

[maxHesse]

Merci pour cette précision. Je n'avais pas envisagé en effet un possible 'déménagement' de mes noeuds.

Je dois reconnaître que j'ai un peu du mal à concevoir mon graphe.
J'ai en tête qu'il faut que j'optimise la navigation d'un noeud à un autre.

Du coup, je pensais d'abord faire porter aux 2 noeuds reliés par une arête l'adresse de l'arête. Mais je pense qu'il y aura 2 problèmes. Celui précédemment évoqué (si j'utilise des std::vector) et celui de la suppression d'un noeud. Dites-moi si je me trompe, mais si je supprime un noeud, je supprime également l'arête vers laquelle il pointe, non? Si oui, que devient mon pointeur de mon autre noeud? Danger non? Idem si je supprime une arête, que deviennent mes 2 pointeurs dans mes noeuds? Mais de toute façon, si mon noeud connaît son arête, je n'avais pas informé l'arête de ses noeuds.

Je me suis ensuite dit que j'allais raisonner autrement, en faisant porter l'information par l'arête, possédant un pointeur vers chaque noeud extrémité. Mais même problème, inversé. Que se passe-t-il si je supprime un noeud? je perds un pointeur dans mon arête? (est-ce que je pourrais imaginer appeler une méthode de mon arête quand je détruit mon noeud?) Si je détruis mon arête, je détruis nécessairement mes noeuds pointés,non?

Du coup, si je reste assez claire, est-ce que vous voyez un moyen d'avoir un graphe dans lequel je peux naviguer efficacement et dans lequel je peux supprimer des éléments sans affecter les autres?


Sinon, sur le point du message précédent, est-ce que je peux gérer autrement que par des std::vector?

[r0d]

Sinon, sur le point du message précédent, est-ce que je peux gérer autrement que par des std::vector?

Tu peux jeter un coup d’œil à ce diagramme. Un peu vieux, donc incomplet aujourd'hui, mais ça peut aider à choisir.

Sinon, as-tu regardé du côté de boost::graph?