I am new to the boost graph library and I am trying to find the shortest path from one vertex to another one in the Graph using the boost graph library. I found some instructions on how to use the predecessor map in order to do that but it won't work for me. When I try to call p[some_vertex]
I get an error saying the []
operator is not defined. Can someone tell me why and what I am doing wrong?
typedef property<edge_weight_t, double, property<edge_index_t, tElementIDVector>> tEdgeProperty;
typedef property<vertex_index_t, tElementID> VertexIDPorperty;
typedef adjacency_list<vecS, setS, directedS, VertexIDPorperty, tEdgeProperty> tGraph;
typedef tGraph::vertex_descriptor tVertex;
typedef tGraph::edge_descriptor tEdge;
vector<tVertex> p(num_vertices(graph));
vector<double> d(num_vertices(graph));
// call dijkstra algorithm from boost to find shortest path
dijkstra_shortest_paths(graph, s,
predecessor_map(&p[0]).
distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));
//find path from start to end vertex
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start)
{
pathVertices.push_front(current);
current = p[current]; //this is where the error occures
}
I couldn't get your idea to work and had to make some other changes now, too which is why i changed my predecessor map now to:
typedef boost::property_map < tGraph, boost::vertex_index_t >::type IndexMap;
typedef boost::iterator_property_map < tVertex*, IndexMap, tVertex, tVertex& > PredecessorMap;
tVertex s = start;
IndexMap indexMap = get(vertex_index, graph);
vector<tVertex> p(num_vertices(graph));
PredecessorMap predecessorMap(&p[0], indexMap);
vector<double> d(num_vertices(graph));
// call dijkstra algorithm from boost to find shortest path
dijkstra_shortest_paths(graph, s, predecessor_map(predecessorMap).distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));
//find path from start to end vertex
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start)
{
pathVertices.push_front(current);
current = predecessorMap[current];
}
and this actually works now :)