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
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
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%...
Sent from the Boost - Users mailing list archive at Nabble.com.
