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-12 02:24:58

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?

Finally I have figure out how to write the recorder. Following is the codes:

template <class PredecessorMap>
class record_edge_predecessors : public dijkstra_visitor<>
        record_edge_predecessors(PredecessorMap p)
                : m_predecessor(p){ }

                template <class Edge, class Graph>
                        void edge_relaxed(Edge e, Graph& g) {
                                put(m_predecessor, target(e, g), e);
        PredecessorMap m_predecessor;

template <class PredecessorMap>
make_edge_predecessor_recorder(PredecessorMap p)
        return record_edge_predecessors<PredecessorMap>(p);

// Notice that the EdgePredecessorMap is map from vertex to edge not edge to
// I am try to get edge-to-edge map in recorder, but it seems hard to

// And there is a helper function to translate result to edges index:

template<typename EdgePredecessorMap, typename VertexPredecessorMap,
typename EdgeIndexMap, typename VertexDescriptor>
std::vector<int> translate_to_edges_index(const EdgePredecessorMap& em,
const VertexPredecessorMap& vm, const EdgeIndexMap& im, VertexDescriptor
        std::vector<int> res;
        while(vm[dest] != dest)
                dest = vm[dest];
        return res;

The recorder works because "Path-relaxation property" in CLR charpter 24.
Question remains:
In above helper function, the return type is hard coded to vector<int>. Is
it possible to traits out the edge_index type of a graph type G(or some type

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