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