Boost Graph [Tutoriel]

**gbdivers** · 07/12/2011, 11h16

Première version (incomplète) pour une FAQ sur Boost Graph. J'ai remarqué que beaucoup de débutant (moi compris) hésitaient à l'utiliser parce qu'elle semble complexe en premier abord.

EDIT : version finale dans l'article : http://gbelz.developpez.com/boost/graph/

**3DArchi** · 07/12/2011, 12h15

whouh

Pourquoi ne pas proposer un tutoriel ?

**r0d** · 07/12/2011, 12h48

Ooomaagaaad!!!!
Si tu avais écris ça il y a deux ans, ça m'aurait évité des heures et des heures de codage de ma propre lib de graphe, qui au final est toute pourrite en plus. Je n'étais pas parvenu à utiliser boost.graph et j'avais abandonné

Un énorme

Je regarderai ça quand j'aurais quelques heures devant moi

Encore merci!

**gbdivers** · 07/12/2011, 12h50

Il y a déjà un tutoriel sur Boost graph, ça ferait doublon. Et le but est surtout de donner des lignes de code directement exploitable (comprendre copié-collable) avec juste les explications nécessaires.

**Luc Hermitte** · 07/12/2011, 14h19

Je manque de recul aussi.
Toujours est-il que c'est plus pour du tuto que de la FAQ à mon goût.

PS: (syntaxe vim pour substitute)
s/graph\(s\=\)\>/graphe\1/gc
s/généric/générique/
s/librairie/bibliothèque/

Désolé de ne pas être plus constructif, je ne pratique pas cette bibliothèque.

**gbdivers** · 07/12/2011, 14h41

# Que signifie les paramètres passés à adjacent_list ?
adjacency_list est une classe templatée acceptant plusieurs paramètres permettant de spécifier le comportement de cette classe. Ces paramètres permettent de choisir les types de conteneurs utilisés en interne (OutEdgeList, VertexList et EdgeList), les propriétés associées aux éléments du graphe (VertexProperties, EdgeProperties, GraphProperties et Directed).

Voici la liste des paramètres et les valeurs par défaut de adjacency_list :

Code :

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

1
2
3
4
5
6
7
8
9
adjacency_list<
   OutEdgeList 		= vecS, 
   VertexList 		= vecS, 
   Directed		= directedS,
   VertexProperties 	= no_property,  
   EdgeProperties 	= no_property,
   GraphProperties 	= no_property, 
   EdgeList		= listS
>

1. Les types des conteneurs (OutEdgeList, VertexList et EdgeList) peuvent être choisir en utilisant les tags précisés dans la liste suivante :

Code :

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

1
2
3
4
5
6
vecS		= std::vector
listS		= std::list
slistS		= std::slist
setS		= std::set
multisetS	= std::multiset
hash_setS	= std::hash_set

Le choix du type de conteneur aura une influence sur les performances des algorithmes utilisés. La complexité des fonctions de Boost Graph en fonction du type de conteneur est indiqué dans la page suivante : Choosing the Edgelist and VertexList

2. Pour les propriétés associées aux éléments d'un graphe, on peut soit utiliser le mot clé no_property pour ne pas associer d'information, soit utiliser une des méthodes indiquées dans la FAQ
# Quelles sont les différentes méthodes permettant d'associer des informations à un élément de Boost Graph ?

3. Pour terminer, le paramètre Directed permet de préciser si le graphe est orienté ou non et si les arcs seront unidirectionnels ou bidirectionnels.

Code :

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

1
2
3
undirectedS	= graphe non orienté
directedS	= graphe orienté avec des arcs unidirectionnels
bidirectionalS	= graphe orienté avec des arcs bidirectionnels

En fonction du type de graphe, certaines fonctions ne seront pas disponibles. Par exemple, avec un graphe orienté unidirectionnel, la fonction in_edges, permettant de récupérer la liste des arcs entrant, n'est pas possible.

**gbdivers** · 07/12/2011, 14h56

Envoyé par Luc Hermitte

PS: (syntaxe vim pour substitute)
s/graph\(s\=\)\>/graphe\1/gc
s/généric/générique/
s/librairie/bibliothèque/

Fait

**gbdivers** · 07/12/2011, 14h59

En fait, à la base, ce n'était que quelques notes que j'avais pris lorsque j'avais regardé BGL. Je pensais pas que ça prendrait tant de place au final. Finalement, ça va probablement finir en article.

**bretus** · 07/12/2011, 23h55

Bonsoir,

Très bonne initiative! En effet, un article, ça serait pas mal. Quelques remarques (à valider).

Renvoyer aussi vers ce tuto?

http://matthieu-brucher.developpez.c...mplementation/

remove/clear

Code :

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

1
2
3
 
// suppression d'un sommet
remove_vertex(v1, g);

Peut-être souligner le fait qu'un sommet est supposé "clean" avant de faire "remove" (sinon, on provoque une catastrophe)

=> pour ne pas se prendre le choux

Code :

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

1
2
3
 
clear_vertex(v1,g);
remove_vertex(v1, g);

undirectedS/directedS/bidirectionalS

Code :

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

1
2
3
4
 
undirectedS	   = graphe non orienté
directedS	   = graphe orienté avec des arcs unidirectionnels
bidirectionalS = graphe orienté avec des arcs bidirectionnels

Peut-être préciser la notion de unidirectionnels/bidirectionnels. En gros :

directedS ne permet pas de récupérer les arcs entrants dans un sommet (in_edges) d'où l’existence de bidirectionalS. Tous deux sont des graphes orientés au niveau conceptuel.

=> Par défaut, on choisit entre undirectedS ou birectionalS en fonction de la nature du graphe (non orienté / orienté). directedS sera une optimisation possible pour consommer moins de mémoire.

Faire une note sur boost::tie

C'est assez paumant dans la documentation officielle quand on ne le connait pas.

Code :

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

1
2
3
4
5
6
 
// Récupérer tous les sommets
std::pair<vertex_iterator_t, vertex_iterator_t> it = boost::vertices(g);
// Equivalent à ce qu'on rencontre dans la doc sous forme de 
vertex_iterator it, it_end;
boost::tie( it, it_end ) = boost::vertices(g);

Mise en garde

La structure doit être adaptée aux algorithmes. Les algorithmes sont rarement implémentés en fonction du conteneur (escroquerie template

).

Exemple :

- On peut concevoir la notion de graphe planaire sur un graphe orienté (en ignorant l'orientation). Le test de planéité ne sera pourtant correct que sur un undirectedS.

- Si in_edges n'est pas présent dans la structure (directedS), boost::graph ne s'amuse pas à calculer sans. On n'a pas par exemple in_degree sur la base d'un scan/comptage de la liste des arcs.

Comme je le faisais remarquer, c'est un peu comme si std::find ne fonctionnait pas sur std::vector puisqu'il n'est pas indexé.

bundle properties

Tu ne parles pas de la syntaxe commode :

Code :

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

1
2
3
4
5
6
 
vertex_descriptor v = /* ... */
VertexProperties const& vertexProperties = g[v];
 
edge_descriptor e = /* ... */
EdgeProperties const& vertexProperties = g[e];

C'est le mal?

++

**gbdivers** · 08/12/2011, 00h12

Renvoyer aussi vers ce tuto?

Ça sera fait dans la version finale de l'article

remove/clear

undirectedS/directedS/bidirectionalS

Faire une note sur boost::tie

Mise en garde

Si le format devient un article plutôt qu'une FAQ, je pourrais détailler un peu plus ces parties. En particulier donner quelques lignes de code pour chaque analyses les plus utilisées sur les graphes. Et détailler les algorithmes fournit pas BGL.

bundle properties

Un oubli de ma part

HS : j'ai également plein de notes sur C++11, ça pourrait intéresser un article ?

**bretus** · 08/12/2011, 00h23

Pas facile d'organiser ce genre d'information. Je t'ai remis ce qui m'a le plus gêner il y a 3/4 mois.

Bon courage

Envoyé par gbdivers

HS : j'ai également plein de notes sur C++11, ça pourrait intéresser un article ?

Dans 10 ans oui (Il y en a qui espère encore le support de Visual 6...) Mais ne divergeons pas

**Flob90** · 08/12/2011, 00h26

Envoyé par gbdivers

HS : j'ai également plein de notes sur C++11, ça pourrait intéresser un article ?

Oui, mais plutôt pour des entrée de FaQ (je crois qu'il n'y a pas encore grand chose sur le C++11) AMA, ou des articles plus approfondis sur des points précis du C++11 (faire un seul article sur tout donnerait quelque chose d'un peu "brouillon" et superficiel je pense).

**gbdivers** · 13/12/2011, 16h44

Voici une première dernière version

**bretus** · 15/12/2011, 18h15

Nickel, merci!

**gbdivers** · 15/12/2011, 20h31

Petite précision, j'ai volontairement peu abordé la partie algo, si quelqu'un souhaite s'y coller, ça me va

Je posterai le tuto en relecture ortho pendant les vacances pour une annonce en début d'année

**CedricMocquillon** · 16/12/2011, 15h49

Salut,

J'ai pas tout lu en détail mais fin de la page 5, les méthodes source et target renvoient des vertex_descriptor et non pas des edge_descriptor:

Code :

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

1
2
3
4
Graph::edge_descriptor v1 = boost::target(e1, g);
Graph::edge_descriptor v2 = boost::source(e5, g);
if (v1 == v2)
  std::cout << "Same vertex" << std::endl;

à remplacer par

Code :

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

1
2
3
4
Graph::vertex_descriptor v1 = boost::target(e1, g);
Graph::vertex_descriptor v2 = boost::source(e5, g);
if (v1 == v2)
  std::cout << "Same vertex" << std::endl;

**3DArchi** · 16/12/2011, 20h25

**gbdivers** · 18/01/2012, 14h42

Envoyé par CedricMocquillon

Salut,

J'ai pas tout lu en détail mais fin de la page 5, les méthodes source et target renvoient des vertex_descriptor et non pas des edge_descriptor:

Code :

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

1
2
3
4
Graph::edge_descriptor v1 = boost::target(e1, g);
Graph::edge_descriptor v2 = boost::source(e5, g);
if (v1 == v2)
  std::cout << "Same vertex" << std::endl;

à remplacer par

Code :

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

1
2
3
4
Graph::vertex_descriptor v1 = boost::target(e1, g);
Graph::vertex_descriptor v2 = boost::source(e5, g);
if (v1 == v2)
  std::cout << "Same vertex" << std::endl;

Fait.

Et proposé en relecture ortho

**gbdivers** · 26/02/2012, 00h30

Version finale : http://gbelz.developpez.com/boost/graph
A archiver et à annoncer sur le portail
Merci à tous

Boost Graph [Tutoriel]

Contribuez C++

Discussions similaires

Partager

Partager