
Boost Users : 
Subject: Re: [Boostusers] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??
From: Li Ning (Ning.c.Li_at_[hidden])
Date: 20090512 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 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?
>
>
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 edgetoedge 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 "Pathrelaxation 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/BGLWhytheoutputofalgorithmsarevertexsequence%28PredecessorMap%29Howaboutparalleledgestp23439356p23496847.html Sent from the Boost  Users mailing list archive at Nabble.com.
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