Re: [Boost-users] Graph Library Question

Subject: Re: [Boost-users] Graph Library Question
From: Ken Kazinski (kjkazinski_at_[hidden])
Date: 2014-05-16 22:21:00

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<graph_t, vertex_index_t>::type
     vertex_id = get(vertex_index, g);

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

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

 parent[vertex(StartNode, g)] = vertex(StartNode, g);
   adjacency_list<listS, vecS, directedS,
     property<vertex_color_t, default_color_type> > 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<graph_t, vertex_distance_t>::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 <alexhighviz_at_[hidden]>
To: boost-users_at_[hidden] 
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_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users