Discussion :

[gbdivers]

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]

whouh

Pourquoi ne pas proposer un tutoriel ?

[r0d]

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]

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.

[gbdivers]

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

[Luc Hermitte]

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]

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

Fait

[gbdivers]

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]

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]

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 ?