Discussion :

[donkeyquote]

Bonjour à tous,

Est-ce quelqu'un peut me donner quelques examples d'utilisation de la librairie des graphs de boost (d'autres mis à part ceux du site officiel ) et/ou un tutoriel illustré, please ? je galère pas mal avec cette livrairie.

En fait je voudrais faire des arbres avec des classes que j'ai crée. Je voudrais faire des parcours (direct, inverse, etc...) de l'arbre et faire appel aux méthodes de mes objets qui se trouvent dans les nodes.

Merci d'avance pour votre aide !

[olivier1978]

Salut,

C'est vrai que cette lib est un peu difficile à prendre en main et que la doc officielle est, à mon avis, loin d'être limpide ...
Pour commencer, il y le tutoriel de miles. Ca m'a donné de bonnes bases de départ, et j'ai ensuite pu faire ce que je voulais avec ce document et la documentation. La mailing list de boost est aussi assez réactive et souvent de bon conseil.
Grosso modo, les grands principes pour utiliser la BGL sont les suivants :

• Choisir sa structure de graphe
• Remplir son graphe
• Manipuler

Pour le choix de la structure de stockage, c'est assez délicat, et ça dépend de l'utilisation que tu comptes en faire. Je ne pourrai te parler que de l'adjacency_list, la seule que j'ai utilisé. Il faut choisisr un conteneur pour les aretes et un conteneur pour les noeuds. Je te conseille cette page qui détaille bien les intérêts et inconvénients de chacun.

Ensuite, tu peux attacher des propriétés à tes arêtes et / ou à tes noeuds. Ces propriétés peuvent être déjà définies dans la BGL (voir la doc), ou être des structures / classes qui te sont propres.
Un petit exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct AttribNoeuds
{
	MyRectangle Rectangle;
	double EDnoeud;
	double EPnoeud;
	bool _isintersected;
};

struct AttribArrete
{
	double EParrete;
};

// Et un typedef pour avoir un graphe dont chaque noeud et chaque arête se voient affectés une strcture
typedef adjacency_list<vecS, vecS, undirectedS, AttribNoeuds, AttribArrete> graphe_non_ori_avec_attrib;

Il me semble que d'après ce que tu décris, cela devrait convenir à tes besoins.

Bon, ensuite, pour ajouter des noeuds à ton graphe, c'est très simple :

Code :

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

1
2
3
4
5
6
7
8
9
graphe_non_ori_avec_attrib _Bgraphe;
MyRectangle rectangle();
// Tu ajoutes un noeud et récupère un vertex_descriptor dessus
vertex_descriptor desc = add_vertex(_Bgraphe);
// Tu fais ce que tu as à faire sur ce noeud
_Bgraphe[desc].Rectangle = rectangle;
_Bgraphe[desc].EDnoeud = 0.;
_Bgraphe[desc].EPnoeud = 0.;
_Bgraphe[desc]._isintersected = false;

Ensuite, si tu veux parcourir tes noeuds, tu fais ça avec un itérateur :

Code :

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

1
2
3
4
5
6
7
8
vertex_iterator v_it, v_end, debut;
boost::tie(debut,v_end) = vertices(_Bgraphe);
double Etotale = 0;
for (v_it=debut;v_it!=v_end;v_it++)
{
	Etotale += _Bgraphe[*v_it].EDnoeud;
	// ...
}

Bon, voilà pour la base, si tu as besoin d'autre chose, n'hésite pas. Le principe est similaire pour les arêtes. Après, pour faire des parcours, soit tu fais toi même ton algo (par exemple en récursif en marquant les noeuds découverts), soit tu regardes les algos existant de boost (breadth_first_search, depth_first_search, ...; c'est ici, point 21)

[JolyLoic]

Personnellement, pour de simples arbres, je n'utiliserais pas la mécanique boost::graph. C'est le marteau piqueur pour écraser une mouche.

[donkeyquote]

Je suis deja parti pour la solution boost...

Merci de ton aide Olivier. C'est assez explicite... j'ai implemente une bonne partie de mon code mais je ne sais pas comment utiliser les "visitors" pour faire les differents parcours de l'arbre.

Pouvez vous me donner un coup de main ?

Merci

[nina2007]

Merci après deux ans ton exemple m'a beaucoup aidé pour débuter avec les boost graph
tout ce qui se trouve sur internet est super compliqué pour un débutant

[Klaim]

JolyLoic> A ce propos, j'en suis venu à la même conclusion pour le graph principal dans mon jeu (j'avais envisagé boost::graph mais j'ai abandonné devant le temps nécessaire pour bien comprendre) et du coup je me demandais dans quel type de cas boost::graph est approprié finalement? Parceque si c'est aussi overkill que ça semble, alors j'ai du mal a imaginer dans quels cas il devient très utile?

[JolyLoic]

Dans le cas de vrais graphes, avec cycles, et si on envisage d'utiliser plus d'un algorithme, je pense que le temps d'apprentissage peut devenir rentabilisé.

[Klaim]

Est-ce que tu peux préciser ce que tu entends par "vrai graph"?

Par exemple celui que j'ai est "abitraire", ce sont des points dans un espace 3D qui peuvent être ou non liés entre eux (avec 8 liens maximum). A priori ça sous entends que des cycles sont possibles. C'est ce que tu appelles un "vrai graph"?

Pour l'instant j'ai dévelopé une solution maison pour la structure du graph mais je n'ai pas encore écrit les algorithmes de recherches (a priori juste un A* suffira).

[JolyLoic]

Je disais vrai graphe par opposition à un arbre, donc, oui, présence de cycles, ou d'éléments disjoints.

[Klaim]

Hmmm ok, merci. Dans ce cas je devrais quand même passer un peu de temps a tester voir si ça peut me permettre d'aller plus vite dans mon développement actuel...