Discussion :

[betsprite]

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]

ca depend de l'algo.

je préconise boost.graph

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

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

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

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