Dmitry Bufistov wrote:
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?
For the shortest path problem you can translate "edgeless" representation to "vertexless" as follows:
vertexless_path translate(weight_map, pred_map, source, tail) { result := []; s := source; t := tail; while (t != s) { result += min_arg(weight_map[(pred_map[t], t)]); //Edge with the minimal weight t = pred_map[t]; } return result; }
Of cause, using the edge_predecessor_recorder is a better solution. If you provide your working code I will try to modify it accordingly.
Regards, Dmitry
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
I wrote a recorder that derived from dijkstra_visitor<> and implement the edge_relax to record the edges sequence. template <class PredecessorVec> class record_edge_predecessors : public dijkstra_visitor<> { public: record_edge_predecessors(PredecessorVec& p) : m_predecessor(p) { } template <class Edge, class Graph> void edge_relaxed(Edge e, Graph& g) { m_predecessor.push_back(get(edge_index_t(), g, e)); } protected: PredecessorVec& m_predecessor; }; template <class PredecessorMap> record_edge_predecessors<PredecessorMap> make_edge_predecessor_recorder(PredecessorMap& p) { return record_edge_predecessors<PredecessorMap>(p); } ............................ std::vector<int> q; graph_traits<G>::vertex_descriptor s = vertex(1, g); dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).weight_map(weightmap).visitor(make_edge_predecessor_recorder(q))); The code works... I don't know how to use edge_predecessor_recorder, it seems unable to slove this problem, because it just has a operator(). And I has some additional questions: 1. Why BGL introduce descriptor? This new thing bring what advantage? In STL, the communication between Algo & Container is iterator. But in BGL, a new "iterator-like" thing: descriptor has been introduced. What is the difference? The document says descriptor is a "handle", isn't iterator also a "handle"?? 2. Can descriptor convertable with iterator? -- 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.