Re: [Boost-users] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??

Subject: Re: [Boost-users] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2009-05-08 04:42:50

Li Ning wrote:
> For example, a graph has 2 nodes: A & B. There are 2 edges form A to B which
> are edge1 & edge2. edge1 has weight 1, edge2 has weight 2. Then the shortest
> path form A to B is: vertex A---edge1---vertex B. But the default output of
> all algorithm is vertex sequence. Why? How to get the edge sequence?? 
> I have noticed vistor.hpp has a class edge_predecessor_recorder, but I don't
> know how to use it. 
> Anybody give me a hint?
> 
For the shortest path problem you can translate "edgeless" 
representation to "vertexless" as follows:

vertexless_path translate(weight_map, pred_map, source, tail)
{
   result := [];
   s := source; t := tail;
   while (t != s)
   {
      result += min_arg(weight_map[(pred_map[t], t)]); //Edge with the 
minimal weight
      t = pred_map[t];	
   }
   return result;
}

Of cause, using the edge_predecessor_recorder is a better solution. If 
you provide your working code I will try to modify it accordingly.

Regards,
Dmitry