Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net