
Boost Users : 
Subject: Re: [Boostusers] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 20090508 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 Aedge1vertex 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
Boostusers 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