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: 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<>
{
public:
        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);
                        }
protected:
        PredecessorMap m_predecessor;
};

template <class PredecessorMap>
record_edge_predecessors<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
edge. 
// I am try to get edge-to-edge map in recorder, but it seems hard to
implement.

// 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
dest)
{
        std::vector<int> res;
        while(vm[dest] != dest)
        {
                res.push_back(im[em[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
else)??
-- 
View this message in context: http://www.nabble.com/-BGL-Why-the-output-of-algorithms-are-vertex-sequence%28PredecessorMap%29--How-about-parallel-edges---tp23439356p23496847.html
Sent from the Boost - Users mailing list archive at Nabble.com.