Comment adapter un graphique personnalisé au modèle de bibliothèque de graphiques boost?

Question

Je suis rouillé sur les modèles C++ et j'utilise la bibliothèque de graphe boost (une combinaison fatale). J'ai cherché sur le web et je ne trouve pas d'instructions directes sur la façon de prendre une structure de graphe personnalisée et d'en adapter suffisamment à BGL (bibliothèque de graphe boost) que je peux utiliser pour booster les algorithmes de déplacement de graphe. Quelqu'un de suffisamment familier avec la bibliothèque pour m'aider?

EDIT: Donc, le principal problème que j'ai eu est de savoir où trouver une source où le total requis pour mapper un graphique arbitraire à un graphe BGL. Je suis vraiment nouveau dans les templates, donc c'est difficile pour moi de lire les spécifications/exemples de BGL. Peut-être que je devrais chercher une source générale sur les modèles?

Answer 1

L'approche, si je comprends bien, est de spécialiser la structure boost::graph_traits pour votre type de graphique. Cela configure BGL avec diverses propriétés importantes, il doit savoir sur votre graphique. Vous allez ensuite spécialiser les fonctions de gabarit globales pour le type spécialisé graph_traits de votre graphique afin de mettre en œuvre toutes les interfaces de graphique d'accélération qui pourraient s'appliquer à votre type de graphique spécifique.

Un exemple est là dans la documentation BGL:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/leda_conversion.html

Il existe des liens pour plusieurs des différentes interfaces là-bas, qui indiquent les fonctions de modèle global dont vous aurez besoin de se spécialiser pour votre graphique si vous voulez soutenir cette interface. La liste complète des interfaces est ici:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/graph_concepts.html

Answer 2

Ma suggestion serait d'abandonner l'utilisation de BGL entièrement à moins que vous avez déjà une quantité importante de code écrit sur le dessus de celui-ci. Je l'ai testé récemment pour une utilisation future sur un grand projet d'analyse graphique, et je l'ai trouvé presque inutilisable en raison d'une API trop complexe et mal conçue.

Il n'y a pas de tâches simples dans BGL, seulement des tâches complexes, et je combattais constamment le compilateur en raison de la hiérarchie des modèles excessivement complexe que possède BGL. Peu ou pas de documentation utile (du moins pas là où c'est vraiment nécessaire) et pas assez d'exemples ne font qu'aggraver les choses. Ce n'est pas un moyen d'écrire du code.

Je vous recommande de passer à LEMON. Il est stable, écrit en C++, facile à comprendre et à coder, propose plusieurs formes de graphiques spécialisées pour prendre en charge différents besoins d'utilisation et prend en charge les fonctions de recherche/visiteur BFS et DFS. Il a aussi son propre équivalent de cartes de propriétés pour les noeuds/arêtes, donc vous devriez être capable d'ajuster votre propre structure de graphe et d'autres données sur lui.

Essayez LEMON; il a un meilleur goût et causera moins d'ulcères. ;-)