Discussion :

[r0d]

Bonsoir,

je ne parviens pas à achever mon A* avec boost.
Je me suis insipiré de la doc officielle sur boost:a_star, de celle sur boost::graph et du tuto de Matthieu, mais je bloque sur le remplissage du graphe

Voici où j'en suis:

J'ai un type Sommet et un vecteur qui contient tous mes sommets:

Code :

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

vector<Sommet*> sommets; // ce sont des pointeurs car en plus il y a une histoire de polymorphisme

Ensuite j'ai un vecteur d'arcs (Edge) qui représente tous les arcs de mon graphes (un arc relie deux sommets):

Code :

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

1
2
typedef std::pair<Sommet*, Sommet*> Edge;
vector<Edge> edges;

Ensuite j'ai un vecteur de coûts (le coût qu'il faut dépenser pour aller d'un sommet à un autre). Un coût est représenté par un entier:

Code :

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

vector<int> costs;

Ensuite, je créé un graphe ainsi:

Code :

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

1
2
3
4
5
// déclaration du type de mon graphe
typedef adjacency_list<listS, vecS, undirectedS, no_property, property<edge_weight_t, int> > mygraph_t;
 
// construction du graphe:
mygraph_t g( edges.size() );

Ca semble fonctionner. Ca compile et ça ne plante pas.
Mais maintenant, je ne parviens pas à le remplir. J'ai tenté plusieurs choses du style:

Code :

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

1
2
3
4
5
6
7
8
9
10
// déclaration de edge_descriptor
typedef mygraph_t::edge_descriptor edge_descriptor;
 
// remplissage du graphe
for( size_t j = 0; j < edges.size(); ++j ) 
{
	edge_descriptor e; 
	bool inserted;
	tie( e, inserted ) = add_edge( edges[j].first, edges[j].second, g );
}

Mais ça ne fonctionne pas et je ne comprends pas les erreurs affichées
Par exemple je ne comprends pas à quel endroit je dois lui dire que les sommets du graphe sont de type Sommet*.
Je ne comprends pas non plus ce que c'est que ce edge_descriptor. Et cette fonction tie() ?

Si quelqu'un a une idée, une piste, une explication ou un lien à me fournir, toute aide sera la bienvenue

merci.