Représentation optimale d'un graphe en C++

**betsprite** · 26/02/2011, 09h53

Bonjour tout le monde,

Afin de pouvoir tester des algorithmes de théorie des graphes pour la recherche d'une coupe minimale (et à plus long terme la segmentation d'une image), j'ai besoin de construire tout d'abord un graphe.

Or d'après vous, quelle est la meilleur représentation possible d'un graphe en C++ ? Une simple matrice avec en (i,j) la valeur de l'arc (i,j) ? Ou a-t-on besoin d'autres données ? Doit-on en faire une classe ou une structure ?

Je vous remercie !

Edit : Pour répondre à l'une de mes questions déjà, j'ai besoin d'autres données que seulement la valeur de l'arc. Voulant utiliser des algorithmes de théorie des graphes sur les flots (Ford-Fulkerson et Push-Relabel), j'ai besoin de connaître aussi par exemple l'excès de flot en un noeud du graphe. Mais comment représenter l'ensemble de mon graphe d'après vous ?

**Joel F** · 26/02/2011, 13h11

ca depend de l'algo.

je préconise boost.graph

**betsprite** · 26/02/2011, 14h29

Merci Joel F pour ta réponse.

En fait, ca me dérange pas de recoder mes propres classes pour la création d'un graphe. Après, si je créé les classes graphe, arête et sommet, qu'est ce que m'apporterais boost en plus pour la création des graphes ?

Merci !

**JolyLoic** · 26/02/2011, 15h46

boost.graph apporte avant tout des algorithmes, adaptables à des classes de graphes existantes. Elle fournit aussi plusieurs classes de graphe, avec des choix différents en terme de compromis.

**betsprite** · 26/02/2011, 15h51

Merci JolyLoic pour l'explication.

Etant donné que je veux développer l'algorithme de Ford-Fulkerson moi-même, je ne vais donc pas utiliser Boost.

Par contre, connaitriez-vous la représentation optimale d'un graphe en C++?
Une classe pour le graphe, une autre pour les sommets, et une troisième pour les arêtes avec en attributs la capacité et le flot de l'arête ?

Merci !

**JolyLoic** · 26/02/2011, 18h56

Ce que j'ai essayé de dire, c'est qu'il n'y a pas de représentation de graphe optimale, ni en C++, ni dans aucun langage. Certaines représentations sont plus adaptées à certains algorithmes, d'autres à d'autres, et on doit souvent choisir la moins mauvaise en fonction des algorithmes que l'on pense utiliser, ainsi que d'autres contraintes (nombre de nœuds, topologie du graphe, compatibilité avec du code existant, dynamicité du graphe,flexibilité de modifications du code...).

Même la phrase "Une classe pour le graphe, une autre pour les sommets, et une troisième pour les arêtes avec en attributs la capacité et le flot de l'arête ?" est extrêmement imprécise. Par exemple, dans ces classes, qui connait qui (lien direct entre sommets ? Un sommet connaît-il les arrêtes suivantes, précédentes, les deux ?...) ? Comment est géré cette connaissance (vector, list, map... d'objet, de pointeurs (intelligents ?)...).

**betsprite** · 28/02/2011, 14h38

Merci JolyLoic je comprends parfaitement ce que tu veux dire.

disons que le terme optimale fait référence ici à mon problème, autrement dit, à la création d'un graphe qui va être utilisé pour calculer via l'algorithme de Ford-Fulkerson une maximisation du flot et donc une coupe minimale.

Maintenant, voulant partir sur une base solide, j'aimerais avoir un avis et des conseils sur l'architecture globale de l'application. C'est vrai que j'ai cependant été trop vague.

L'algorithme de FF se décompose en deux étapes :
- Une méthode de marquage des sommets pour trouver des chemins augmentant (chemin par lequel on peut augmenter le flot).
- Une méthode d'augmentation du flot

Au départ, mon idée était de représenter mon application sous la forme suivante :

- Une classe node (sommet en français) représenté par deux listes d'objets Edge (ou arête) : une pour les arêtes entrantes et une pour les arêtes sortantes du sommet.
- Une classe Edge (arête en français) représentée par un sommet (Node) de départ et un sommet (Node) d'arrivé.
- Un graphe représenté par une liste de sommets et une liste d'arêtes.

(J'ai malgré tout l'impression dans cette représentation de faire une redondance car mes arêtes ont deux sommets et chaque sommet est représenté par notamment un ensemble d'arêtes. Qu'en pensez-vous ?)

Cependant, j'ai un problème lorsque j'essaie déjà d'implémenter cette structure de base. Le fait que ma classe Sommet ait besoin de ma classe Arête et que ma classe Arête ait besoin de ma classe Sommet pose en effet un problème malgré l'empêchement de la boucle infinie avec dans les .h :

Code :

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

1
2
3
4
#ifndef EDGE_H_INCLUDED
#define EDGE_H_INCLUDED
 
#endif // EDGE_H_INCLUDED

Pour être plus claire, j'ai commencé par la classe Edge (arête) pour laquelle j'ai include "node.h". Jusque là tout va bien.
Ensuite, je fais la classe Node, et lors de l'include "Edge.h", j'ai les erreurs suivantes :

|error: expected ')' before '*' token|
13 |error: ISO C++ forbids declaration of 'Node' with no type|
13 |error: expected ';' before '*' token|
14 |error: ISO C++ forbids declaration of 'Node' with no type|
14 |error: expected ';' before '*' token|
17 |error: 'Node' has not been declared|
18 |error: 'Node' has not been declared|
22 |error: ISO C++ forbids declaration of 'Node' with no type|
22 |error: expected ';' before '*' token|
23 |error: ISO C++ forbids declaration of 'Node' with no type|
23 |error: expected ';' before '*' token|
||=== Build finished: 11 errors, 0 warnings ===|

Avec ma classe concernée :

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
1. #ifndef EDGE_H_INCLUDED
2. #define EDGE_H_INCLUDED
3.
4. #include "Node.h"
5.
6. class Edge
7. {
8. public :
9.        Edge();
10.        Edge(Node*, Node*, double);
11.       ~Edge();
12.
13.        Node* getStartingNode();
14.        Node* getEndingNode();
15.        double getCapacity();
16.
17.        void setStartingNode(Node*);
18.        void setEndingNode(Node*);
19.        void setCapacity(double);
20.
21. private :
22.       Node *startingNode;
23.        Node *endingNode;
24.        double capacity;
 
protected :
};
 
#endif // EDGE_H_INCLUDED

Auriez-vous une idée ?

Merci

**dragonjoker59** · 28/02/2011, 15h05

Pour ton problème d'objets qui se connaissent mutuellement, il te faudra utiliser la pré-déclaration de classe et les pointeurs :

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
 
// Fichier Node.h
#ifndef ___NODE___
#define ___NODE___
class Edge;
typedef std::shared_ptr<Edge> EdgePtr;
typedef std::list<EdgePtr> EdgePtrList;
 
class Node
{
private:
   EdgePtrList m_listIn;
   EdgePtrList m_listOut;
// ...
};
#endif

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
 
// Fichier Edge.h
#ifndef ___EDGE___
#define ___EDGE___
class Node;
typedef std::shared_ptr<Node> NodePtr;
 
class Edge
{
private:
   NodePtr m_start;
   NodePtr m_end;
// ...
};
#endif

**betsprite** · 28/02/2011, 15h28

Merci dragonjoker59 pour ta réponse

Cependant, j'ai du mal à comprendre pourquoi il ne suffirait pas de faire :

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
#ifndef EDGE_H_INCLUDED
#define EDGE_H_INCLUDED
 
#include "Node.h"
 
class Edge
{
public :
 
private :
Node *startingNode;
Node *endingNode;
};
 
#endif // EDGE_H_INCLUDED

Et qu'il faut donc faire à la place :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Fichier Edge.h
#ifndef ___EDGE___
#define ___EDGE___
class Node;
typedef std::shared_ptr<Node> NodePtr;
 
class Edge
{
private:
   NodePtr m_start;
   NodePtr m_end;
// ...
};
#endif

Pourquoi la première solution n'est pas suffisante et qu'apporte en plus la deuxième qui fonctionne ?
Aussi doit-on ajouter malgré tout le include "Node.h" dans la deuxième solution ? (tu ne l'as peut être pas mis dans l'exemple par oubli je ne sais pas ^^)

Merci encore !

**dragonjoker59** · 28/02/2011, 15h37

Les 2 versions sont presqu'équivalentes. En fait, inclure Node.h ralentira un poil la compilation, ce autant de fois que ton fichier Edge.h sera inclus. Ensuite j'ai utilisé des shared_ptr, par habitude, et parce que ça permet d'éviter certaines erreurs des pointeurs nus.
Fondamentalement, les 2 codes feront la même chose.

**betsprite** · 28/02/2011, 16h01

Merci dragonjoker59!

Mais, si ce n'est qu'une question d'optimisation entre les deux options, pourquoi mon programme ne compile pas correctement avec la première option?

Envoyé par dragonjoker59

En fait, inclure Node.h ralentira un poil la compilation, ce autant de fois que ton fichier Edge.h sera inclus

Mais le fichier .h n'est lu qu'une seule fois justement avec le "#ifndef EDGE_H_INCLUDED" non?

Sinon, une toute autre question :

Que pensez-vous pour la conception de remplacer la représentation d'un noeud par une liste de noeuds de provenance, et une liste de noeuds de destination ? (au lieu d'une liste d'arêtes rentrantes et d'une liste d'arêtes sortantes ?)

Merci !

**dragonjoker59** · 28/02/2011, 16h42

Oui effectivement, j'ai peut etre dit une connerie...

**betsprite** · 28/02/2011, 16h56

Ok dragonjoker59 :p Il faudrait l'avis d'une autre personne pour qu'il puisse confirmer ou pas

Cependant, que penses-tu de la représentation que je propose par rapport à l'ancienne ?

Merci !

**koala01** · 01/03/2011, 16h28

Salut,

Non, dragonjoker59, tu n'as pas dit de connerie...

Le problème de compilation est, bel et bien, du au problème à ce point courent que la FAQ y consacre une entrée d'inclusion cyclique...

Pour arriver à comprendre le problème, il faut déjà comprendre (ne serait-ce qu'en très gros) les différentes étapes de la compilation.

La toute première étape est le passage par le préprocesseur, qui va gérer toutes les lignes qui commencent par un # (et les symboles éventuellement définis grace à ces lignes).

Il ne s'agit, ni plus ni moins, que de macro ayant un résultat prévisible et reproductible.

Ainsi, l'instruction #include va avoir pour effet de... copier le contenu du fichier dont le nom est donné à l'endroit où l'instruction se trouve.

Si on regarde node.h en premier, nous nous rendons donc compte que, une fois cette macro appliquée, nous obtenons quelque chose proche de

Code :

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

1
2
3
4
5
6
#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED
contenu de edge.h
 
la classe node
#endif // NODE_H_INCLUDED

Mais, pour notre malheur, nous nous rendons compte que le contenu de edge.h est, pour sa part, proche de

Code :

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

1
2
3
4
5
6
7
#ifndef EDGE_H_INCLUDED
#define EDGE_H_INCLUDED
contenu de node.h
 
la classe edge
 
#endif // EDGE_H_INCLUDED

Et voilà le serprent qui se mord la queue, car node.h va essayer d'inclure edge.h, qui va essayer d'inclure node.h, qui va essayer d'inclure... (et on peut continuer longtemps comme cela )

Après un certain moment, le préprocesseur va cesser ce jeu d'inclusions cycliques, mais, le résultat, c'est que l'une des classes (edge en l'occurence... cette fois ci...) utilise une classe que le compilateur ne connait absolument pas (il ne sait même pas qu'elle existe): node.

Or, le compilateur est "bête et méchant": si il rencontre un symbole non défini, il t'insulte avant de sortir sur une erreur

**betsprite** · 01/03/2011, 16h49

Bonjour,

Merci beaucoup koala01 pour cette réponse très claire !

Envoyé par koala01

Et voilà le serprent qui se mord la queue, car node.h va essayer d'inclure edge.h, qui va essayer d'inclure node.h, qui va essayer d'inclure... (et on peut continuer longtemps comme cela )

Justement, je croyais qu'il suffisait d'avoir la structure :

Code :

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

1
2
3
4
5
6
7
#ifndef ...
#define ...
 
// Contenu
 
 
#endif

pour qu'il n'y ait pas ce problème de boucle infinie... (alors qu'en fait ca sert juste à ne pas relire le fichier s'il est appelé par plusieurs classes c'est ça ?)

Dans ce cas, comment remédier à ce problème ? Si oui, est-il souhaitable d'utiliser une méthode existante pour y remédier ou cette boucle infinie d'inclusion ne traduirait-elle pas une faiblesse dans la conception de l'application ?

Merci beaucoup !

**jblecanard** · 01/03/2011, 17h03

Salut, Koala t'as pourtant donné la réponse

**betsprite** · 01/03/2011, 17h12

-_- au temps pour moi ...

Merci jblecanard, je suis un peu étourdi sur ce coup ^^ ! Je vais étudier ca !

Edit :

De manière générale les déclarations anticipées sont à utiliser autant que possible, à savoir dès qu'on déclare dans une classe un pointeur ou une référence sur une autre classe. En effet, cela permet aussi de limiter les dépendances entre les fichiers et de réduire considérablement le temps de compilation.

Il ne faut plus faire de #include "xxxx.h" dans les fichiers h alors ? Pourtant si on remet une inclusion dans le .cpp, le compilateur va quand même devoir aller chercher le fichier au début de la lecture du cpp non ?

**dragonjoker59** · 01/03/2011, 17h21

Certes, mais il n'y aura plus d'inclusions cycliques.

**betsprite** · 01/03/2011, 17h48

D'accord mais ou est le gain de performance en mettant plutôt les include dans les fichiers cpp ?

**dragonjoker59** · 02/03/2011, 09h01

Le gain de performance se situera uniquement au moment de la compilation.
En fait il s'agit d'une bonne habitude à prendre pour éviter des temps de compil faramineux sur les gros projets.

Représentation optimale d'un graphe en C++

C++

Discussions similaires

Partager

Partager