Boost Graph

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/

whouh

Pourquoi ne pas proposer un tutoriel ?

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

Un énorme :merci:
Je regarderai ça quand j'aurais quelques heures devant moi :)

Encore merci! :ccool:

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.

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.

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

---

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:

---

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:

---

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.

Citation:

---

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

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.

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:

---

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:

---

1 2 3

clear_vertex(v1,g); remove_vertex(v1, g);

---

undirectedS/directedS/bidirectionalS

Code:

---

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:

---

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 :aie:).

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:

---

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?


++

Citation:

---

Renvoyer aussi vers ce tuto?

---

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

Citation:

---

remove/clear

---

Citation:

---

undirectedS/directedS/bidirectionalS

---

Citation:

---

Faire une note sur boost::tie

---

Citation:

---

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.

Citation:

---

bundle properties

---

Un oubli de ma part :)


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

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

Citation:

---

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

Citation:

---

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

Voici une première dernière version

Nickel, merci!

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

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:

---

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:

---

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;

---

:ccool:

Citation:

---

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:

---

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:

---

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

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