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 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.

Andrew Sutton wrote: [skip]

The biggest reason for using descriptors is that they can provide a higher degree of stability than iterators. For example, a vector will invalidate all iterators on insert and remove. [skip]

"Remove" also invalidates vertex descriptors! Dmitry

Andrew Sutton wrote:

The biggest reason for using descriptors is that they can provide a higher degree of stability than iterators. For example, a vector will invalidate all iterators on insert and remove.

[skip]

"Remove" also invalidates vertex descriptors!

For VertexList == vecS, yes. My advice regarding this would be: If you're using vecS for vectors, don't remove vertices. If you have to remove vertices, use listS and never call num_vertices,

For anything other than vecS, remove_vertex shouldn't invalidate descriptors other than the one removed. I hope.

Yes, and as I understand it, ditto iterators. So the question still stands! Louis.

Andrew Sutton-2 wrote:

...

"Remove" also invalidates vertex descriptors!

...

For VertexList == vecS, yes. My advice regarding this would be: If you're using vecS for vectors, don't remove vertices. If you have to remove vertices, use listS and never call num_vertices,

For anything other than vecS, remove_vertex shouldn't invalidate descriptors other than the one removed. I hope.

Yes, and as I understand it, ditto iterators. So the question still stands!

I can rephrase my previous answer. Descriptors provide improved stability over iterators. With vectors, iterators are invalidated on insert and erase, but descriptors are only invalidated on erase/remove. With linked memory structures (e.g,. lists and trees) neither set of operations (should) invalidate other iterators or descriptors.

Andrew Sutton andrew.n.sutton@gmail.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I understand. The descriptor exists because of 'add_edge' like functions. And the inter-reference between vertex & edge is operated on descriptor will eliminate affect of 'add' operation. However, remove still has invalidate problem. -- 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.

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; }

I would recommend using the get() and put() functions for property maps instead of operator[]. It allows a broader class of property maps to be used with the algorithm. Andrew Sutton andrew.n.sutton@gmail.com