Re: [Boost-users] Graph Library Question

17 May 2014

      Hi Alex,

I tried to implement the simplified code but I guess I really do not understand the Boost Graph lib.

Here is my function:

std::string myGraph::GetPathAndDistanceBetweenNodes(int StartNode, int EndNode)
{
 std::string OutputPath = "";
 std::stringstream TempString;

   boost::property_map::type
     vertex_id = get(vertex_index, g);

   std::vector<int> distance(_GraphSize, (std::numeric_limits<int>::max)());

   typedef boost::graph_traits::vertex_descriptor Vertex;
   std::vector<Vertex> parent(_GraphSize);

 parent[vertex(StartNode, g)] = vertex(StartNode, g);
   adjacency_list > g_copy(_GraphSize);

 dijkstra_shortest_paths
     (g, vertex(StartNode, g),
      distance_map(make_iterator_property_map(distance.begin(), vertex_id,
                                              distance[0])).
      predecessor_map(make_iterator_property_map(parent.begin(), vertex_id,
                                                 parent[0])).
      visitor(make_dijkstra_visitor(copy_graph(g_copy, on_examine_edge()))));

// This is the simplified code
 vector<vertex> path;
 for ( vertex current = EndNode; current != StartNode; current = predecessor[current] )
 {
  // Append string here
  TempString << current;
  OutputPath.append(TempString.str());
  OutputPath.append(" ");
  path.push_back(current);
 }
 path.push_back(source);
 std::reverse(path.begin(), path.end());

 property_map::type
     d_map = get(vertex_distance, g);
   dag_shortest_paths(g, StartNode, distance_map(d_map));

   OutputPath.append(" (");
   TempString << d_map[EndNode];
   OutputPath.append(TempString.str());
   OutputPath.append(")");

   return OutputPath;
}

I am trying to output the list of nodes 1 3 4 5 (20) and the distance.

Thanks in advance.

Ken

 From: alex 
To: boost-users@lists.boost.org 
Sent: Friday, May 16, 2014 9:13 AM
Subject: Re: [Boost-users] Graph Library Question
...
I was able to find the shortest distances between my starting node and the
rest
of the nodes.
Now I would like to output the path between my starting node and
destination
node.  I have tried a number of different examples but none of them seem to
do what I want.
For this you need the predecessor map, just as you needed the distance map
to look up distances.

This is what Arne Vogel wrote last week:

To read the path from the PredecessorMap, you work your way backwards 
from the destination vertex to the source vertex, always looking up the 
predecessor of the current vertex in the predecessor map, until the 
current vertex is equal to the source vertex. Then you just reverse the 
path if necessary. Or, as simplified code:

vector<vertex> path;
for ( vertex current = destination; current != source; current = 
predecessor[current] )
{
     path.push_back(current);
}
path.push_back(source);
std::reverse(path.begin(), path.end());

_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

Re: [Boost-users] Graph Library Question

Ken Kazinski