Discussion :

[mick009]

Bonjour,
J'ai lu beaucoup de tutoriels sur la librairie Graph proposée par Boost, mais je ne comprends pas comment l'appliquer dans mon cas...
J'ai un vector à deux dimensions contenant des bool. 0 signifie un passage et 1 un mur.
J'aimerais faire une fonction qui me retourne un vector des passages à prendre pour passer rapidement d'un point A à un point B, sans passer par les diagonales. Je n'arrive pas à programmer cela...

Pouvez-vous m'aider ?
Si vous avez des codes exemples ou autres, je prends !
Je suis déjà aller à ce lien http://matthieu-brucher.developpez.c...mentation/#LIV.

L'ennui c'est que je n'ai pas tout compris...
Merci par avance pour votre aide !

[Matthieu Brucher]

Tu veux faire un Dijkstra, c'est ça ?

Tout d'abord, tu dois construire ton graphe. Tu as réussi ?

[mick009]

Oui je veux utiliser cet algorithme !
Ou le A star, cela ne me dérange pas...

Mais non, je n'ai pas réussi à construire le graphe, puisqu'il y a plein de classes, la documentation sur le site de boost est un peu désordonnée (ou c'est moi qui m'y repère pas ).
Et je ne sais pas comment appliquer à mon cas cette classe. Du style, je ne sais pas qu'est ce que les edges, les vertex, si j'en ai réellement besoin sachant qu'il ne s'agit que de 0 ou 1...

Merci d'avance pour vos réponses

[Matthieu Brucher]

Comme tu as une matrice (un graphe complètement connecté), une adjacency_matrix est ce qui paraît le plus logique. Par la suite, tu crées tes propriétés comme pour l'adjacency_list.

Mais je te l'accorde, c'est une bibliothèque complexe (et après un long temps sans elle, j'ai aussi du mal à m'y retrouver )

[mick009]

Oui, mais ce que je voulais aussi savoir c'est qu'est-ce que je mets comme type pour les vertex, les edges, ....
Et comment je remplis alors mon graphe ? Comme j'indique que 0 est un passage et 1 un mur ?

Merci beaucoup pour ta patience

[Matthieu Brucher]

Le type des vertex, c'est des entiers normalement. Pour les arcs, tu prends aussi des entiers.
Après, c'est comme mon tutoriel.

[mick009]

Mais je n'ai pas vu l'utilisation de l'algorithme.
Je crois que je vais essayer de le relire plus en détail....

Mais je pense que les développeurs de cette librairie auraient peut-être dût plus détailler la documentation... (avec des images et tout ça).
Mais bon, c'est déjà assez complexe à assimiler les graphes, donc on peut voir déjà ça comme du bon travail

PS : est-ce que je vais avoir à utiliser les property_maps ? Et pourquoi ne pas utiliser les booléens puisque je travaille directement dessus ?

[Matthieu Brucher]

Je n'ai pas fait d'article sur l'utilisation des fonctions.

Tes property maps seront, si je me souviens bien, les poids que tu mets sur le graphe, à savoir des poids de 0 ou de 1. Tu n'as pas le choix

[mick009]

Même si j'aurais voulu comprendre (et utiliser) boost Graph, je crois qu'il vaut mieux que je développe mon propre algorithme (je prendrai algorithme A*) appropriée pour mon cas !

Merci beaucoup pour votre aide !
Et espérons qu'ils amélioreront leur documentation (car même si cela fait un bout de temps que l'on travaille pas sur Boost, la documentation devrait être capable de s'en remémorer facilement et rapidement...