Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??
From: Li Ning (Ning.c.Li_at_[hidden])
Date: 2009-05-08 05:40:36

Dmitry Bufistov wrote:
> 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 mailing list
> Boost-users_at_[hidden]

I wrote a recorder that derived from dijkstra_visitor<> and implement the
edge_relax to record the edges sequence.
template <class PredecessorVec>
class record_edge_predecessors : public dijkstra_visitor<>
        record_edge_predecessors(PredecessorVec& p)
                : m_predecessor(p) { }

                template <class Edge, class Graph>
                        void edge_relaxed(Edge e, Graph& g) {
                                m_predecessor.push_back(get(edge_index_t(), g, e));
        PredecessorVec& m_predecessor;

template <class PredecessorMap> record_edge_predecessors<PredecessorMap>
make_edge_predecessor_recorder(PredecessorMap& p)
        return record_edge_predecessors<PredecessorMap>(p);
std::vector<int> q;
graph_traits<G>::vertex_descriptor s = vertex(1, g);
dijkstra_shortest_paths(g, s,

The code works...

I don't know how to use edge_predecessor_recorder, it seems unable to slove
this problem, because it just has a operator().
And I has some additional questions:
1. Why BGL introduce descriptor? This new thing bring what advantage? In
STL, the communication between Algo & Container is iterator. But in BGL, a
new "iterator-like" thing: descriptor has been introduced. What is the
difference? The document says descriptor is a "handle", isn't iterator also
a "handle"??
2. Can descriptor convertable with iterator?

View this message in context:
Sent from the Boost - Users mailing list archive at

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at