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

Version imprimable

26/02/2011, 09h53
betsprite

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

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 ?
26/02/2011, 13h11
Joel F

ca depend de l'algo.

je préconise boost.graph
26/02/2011, 14h29
betsprite

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 !
26/02/2011, 15h46
JolyLoic

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.
26/02/2011, 15h51
betsprite

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 !
26/02/2011, 18h56
JolyLoic

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 ?)...).

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:

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 :

Citation:

|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:

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 ;)

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

Code:

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:

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

Merci dragonjoker59 pour ta réponse :)

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

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:

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 !

28/02/2011, 15h37
dragonjoker59

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.
28/02/2011, 16h01
betsprite

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?

Citation:

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 !
28/02/2011, 16h42
dragonjoker59

Oui effectivement, j'ai peut etre dit une connerie...
28/02/2011, 16h56
betsprite

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 !
01/03/2011, 16h28
koala01
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:

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:

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 ;)
01/03/2011, 16h49
betsprite
Bonjour,

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

Citation:

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:

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 !
01/03/2011, 17h03
jblecanard

Salut, Koala t'as pourtant donné la réponse :)
01/03/2011, 17h12
betsprite

-_- au temps pour moi ... :P

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

Edit :

Citation:

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 ?
01/03/2011, 17h21
dragonjoker59

Certes, mais il n'y aura plus d'inclusions cycliques.
01/03/2011, 17h48
betsprite

D'accord mais ou est le gain de performance en mettant plutôt les include dans les fichiers cpp ?
02/03/2011, 09h01
dragonjoker59

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.
02/03/2011, 09h30
betsprite

D'accord dragonjoker59 mais ce que je veux dire par là, c'est que lors de la compilation, les directives de préprocesseur des .cpp seront aussi parcourues, donc je ne vois pas pourquoi le temps de compilation serait différent entre le fait de mettre les includes dans les .h ou dans les .cpp...
02/03/2011, 11h24
Klaim

Le vrai code (les unités de compilation) est dans les cpp.

Dans les headers (les h) tu as juste du code qui va être copié/collé dans tes cpp , via #include.

Donc, si tu as des N #include dans un .h, tous les cpp qui vont include ce fichier vont appliquer l'include. Si tu as K fichiers cpp, alors tu as T = N x K includes qui vont se passer à la compilation.

Une #include corresponds à un copier coller de fichier, soit:

1. ouvrir le fichier
2. lire le contenu
2.1. lire les commandes de preprocessing et les appliquer (potentiellement allant a 1. recursivement)
3. copier le code final (après preprocessing) dans le code du cpp

Hors optimizations faites par les compilateurs, tu vas donc avoir T fois ces operations.
Notemment, 1. est très couteux, 2. est contextuel et peut donc donner différents résultats selon les définitions en cours (#define).

Et en plus, seulement une fois tous les includes resolus, là on peut compiler l'ensemble.

Donc c'est couteux en temps. Dans l'idéal, limite les #include dans le .h à ce qui est absolument nécessaire, lorsque tu dois avoir la DEFINITION des types utilisés dans le header. Si tu n'as besoin que de leurs noms, leurs DECLARATION, alors fait des "forward declare", dis juste que leurs noms existes - typiquement si tu ne manipules que des pointeurs et des références vers ces types dans le header.

En fait il faut comprendre tout le processus de compilation pour que cela paraisse évident.
10/03/2011, 02h35
MABROUKI

matrice d'incidence,matrice d'adjacence,graphe

bonjour
veux-tu reinventer la roue a propos de la representation d'un graphe.il n'y a pas sur le plan des recherches mathematiques theoriques d'autres representation efficiente que matrice d'incidence noeud/noeud ou(exclusif) matrice d'adjacence arcs/noeuds .
Elles contiennent si je puis dire la "quintessence,la moelle " pour decrire d'une maniere complete un graphe et meme un peu plus .
Entre autres suivant que l'on a choisi l'une de ces 2 representations on peut deduire ,à partir d'une liste des aretes ou arcs les informations suivantes :
1/graphe non oriente
- liste des noeuds voisins d'un noeud
- liste des arcs voisins d'un noeud
2/graphe oriente (arete oriente)
- liste des noeuds voisins incidents et sortants d'un noeud
- liste des arcs voisins incidents et sortants d'un noeud
De plus ces "structures" d'informations complementaires sont -indispensables- dans la quasi majorites des algo de graphes classiques (plus court chemin et ses variantes, coupe ,postier chinois, sac à dos .... ).
Maintenant il ne faut pas confondre l'implementation de ces representations dans un language bien specifique (c++,fortran,java ou cobol ...) et les 2 representations citees ci-dessus.
Je connais des implementations de graphe en fortran(ou il n'y a que des tableaux),en c++ avec des dictionnaires etc....
Implementation
---------------
Un premier point est remarquable dans l'implementation :
-la representation par une matrice d'incidence n'a pas la faveur des auteurs de code à cause qu'elle peut etre "sparse" (comporter des elements vide -graphe peu dense en nombre d'aretes) et gaspiller la memoire.
-aussi la matrice d'adjacence a-t-elle la faveur dans toutes les implementations quelque soit les languages utilises.
Un deuxieme point qui parait anodin mais de la plus haute importance en realite est que l'information "noeud" est deja contenu dans l'information "arete" mais l'inverse n'est pas vrai (un graphe ou tous les noeuds seraient "pendants ou dead nodes " ne repond pas à la definition d'un graphe).Ceci pour soulager ton martyr à propos de la redondance qui n'existe pas si ty reflechis un peu plus en profondeur.

Un troisieme point doit attirer l'attention est que les donnees d'un graphe sont disponibles ou peuvent etre toujours mises sous la forme d'une liste d'aretes jointes à d'autres informations.
Armes de ces remarques on peut concevoir :
-un dictionnaire graphe (un dictionnaire ou table de hashage à cle unique) contenant la liste des membres de la classe Arcs (cle=serait "startnode+endnode",numero d'arc=indice).
L'utilite du dictionnaire vient à propos pour eviter les erreurs dans les donnees ainsi que son indice qui servira heureusement à numeroter les arcs.
-toujours un 2eme dictionnaire(ou est deporte la fameuse adjacence arc-noeud) s'avere approprie pour la classe "Node" (cle="startnod",numero noeud =indice).Les membres de cette classe sont crees au fur et à mesure de l'insertion des aretes.
L'utilite du dictionnaire est qu'il permet de n'inserer que les noeuds des nouveaux arcs mais qui ne figurent pas encore dans le dictionnaire noeud (pas de "dead nodes ou bouts morts" suite à une duplication erronee).
Les autres structures complementaires citees en 1/ et 2/ sont egalement à implementer dans les classes de base.Ces structures sont construites egalement au fur à mesure de l'insertion des aretes et noeuds
La encore ne craignons pas d'abuser des dictionnaires pour les noeuds voisins et les arcs voisins d'un noeuds.
Entre autre utilite de la structure dictionnaire est qu'elle permet d'eviter le fameux test de connexite d'un graphe.
-Il faudrait implementer le tri evidement qui est utile dans la fonction de base des classes.
Classe Graphe
-------------
Autre question bien à propos c'est d'implementer la classe Graphe car il s'agit d'une question pratique bien à propos:
-distinguer un graphe oriente d'un graphe non-oriente
-appartenance d'un sous-graphe à un graphe (foret).
-un algo doit posseder en donnee d'entree une instance graphe (avec tous ses baguages cite ci-dessus) et se limiter à implementer uniquement ses propres structures et sa logique.
Algos structures et methodes communes
---------------------------------------
-table de marquage pour exploration ou tables de recherche avec des structures identiques (liste de noeuds ou arcs predecesseurs dans une exploration)peuvent etre communes à plusieurs algos ainsi que leur methodes (à mettre en pool =>methodes helper d'algo).

Algos structures specifiques
------------------------------
-les autres structures et mthodes specifiques à chaque algo sont à circoncire à l'algo en question.

Pour l'anecdote quand j'ai vu les structures utilisees dans la BCL et dans les fameux graphes de codeplex cela m'a rappele 2 anciens programmes en fortran (annee 70) qui utilisait une structure graphe et comment le probleme de "redondance" avait ete resolu remarquablement à l'epoque par une routine dont le seul role est de verifier au cours de la lecture de chaque arc pour la paire "starnode" et "endnode" que le "nom" de chaque node ne figure dans une table des noms de noeuds et auquel cas elle devait l'ajouter et renvoyer un numero de noeud .
Ce numero etait necessaire pour construitre les autres tables (noeuds voisins,arcs voisins) car les "noms" servait juste de mnemoniques pour l'impression et la comprehension humaine des choses par les utilisateurs en fait )
En esperant que mes humbles remarques auront contribues à eclaircir un peu mieux les choses....
bon code....grapheur...mais il ne faut lacher le morceau et avoir bonne prise...
10/03/2011, 08h06
Dr Dédé

Citation:

Envoyé par betsprite

D'accord dragonjoker59 mais ce que je veux dire par là, c'est que lors de la compilation, les directives de préprocesseur des .cpp seront aussi parcourues, donc je ne vois pas pourquoi le temps de compilation serait différent entre le fait de mettre les includes dans les .h ou dans les .cpp...

La raison est simple. Un fichier .cpp définit une unité de traduction et est donc compilé une seule fois. Un fichier .h est compilé une fois par unité de traduction qui l'inclut, donc un nombre arbitraire de fois.

Donc, ajouter un include dans un cpp entraîne potentiellement une et une seule compilation supplémentaire de ce fichier d'en-tête; ajouter un include dans un .h entraîne un nombre arbitraires de compilations supplémentaires.