[BGL] In what order does out_edge_iterator iterate?
Hi, In my application, the order in which edges are retreaved is also important to me. So my question is, when I iterate through an vertex's out_edges, do they show up in the order in which the edges are inserted, or any other principals are used in order of iteration? Example: ...... typename graph_traits<Graph>::out_edge_iterator out_i, out_end; typename graph_traits<Graph>::edge_descriptor e; for (tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) { e = *out_i; Vertex src = source(e, g), targ = target(e, g); std::cout << "(" << get(vertex_id, src) << "," << get(vertex_id, targ) << ") "; } ...... How are these edges ordered in the output? And is it right all those iterators iterates in the same principals/order? Thanks, Shufei
On 3/5/07, Shufei Fan <fansf@hotmail.com> wrote:
Hi, In my application, the order in which edges are retreaved is also important to me. So my question is, when I iterate through an vertex's out_edges, do they show up in the order in which the edges are inserted, or any other principals are used in order of iteration? Example: ...... typename graph_traits<Graph>::out_edge_iterator out_i, out_end; typename graph_traits<Graph>::edge_descriptor e; for (tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) { e = *out_i; Vertex src = source(e, g), targ = target(e, g); std::cout << "(" << get(vertex_id, src) << "," << get(vertex_id, targ) << ") "; } ...... How are these edges ordered in the output? And is it right all those iterators iterates in the same principals/order?
Hi Shufei, The order in which edges/vertices appear when you iterate over them is undefined - in both the BGL graph concepts (http://www.boost.org/libs/graph/doc/graph_concepts.html) and in the graph implementations provided with the BGL (adjacency_list, adjacency_matrix, etc.) Regards, Aaron
--- Aaron Windsor wrote:
Hi Shufei,
The order in which edges/vertices appear when you iterate over them is undefined - in both the BGL graph concepts
(http://www.boost.org/libs/graph/doc/graph_concepts.html)
and in the graph implementations provided with the BGL (adjacency_list, adjacency_matrix, etc.)
Regards, Aaron
Not necessarily. If you use adjacency_matrix (or adjacency_list with setS as the edge list selector) your edges and target vertices will be ordered by vertex index during out-edge iteration. See <BOOST-ROOT/libs/graph/test/adjacency_matrix_test.cpp> HTH, Cromwell D. Enage ____________________________________________________________________________________ Bored stiff? Loosen up... Download and play hundreds of games for free on Yahoo! Games. http://games.yahoo.com/games/front
On Mar 5, 2007, at 11:17 AM, Shufei Fan wrote:
In my application, the order in which edges are retreaved is also important to me. So my question is, when I iterate through an vertex's out_edges, do they show up in the order in which the edges are inserted, or any other principals are used in order of iteration? Example: ...... typename graph_traits<Graph>::out_edge_iterator out_i, out_end; typename graph_traits<Graph>::edge_descriptor e; for (tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) { e = *out_i; Vertex src = source(e, g), targ = target(e, g); std::cout << "(" << get(vertex_id, src) << "," << get(vertex_id, targ) << ") "; } ...... How are these edges ordered in the output? And is it right all those iterators iterates in the same principals/order?
The document doesn't define this, but it should. It depends on precisely which graph type you're using, but... If you're using an adjacency list with OutEdgeListS=setS, or if you're using an adjacency matrix, the out-edges will be ordered increasing order of the target. If you're using an adjacency list with any other OutEdgeListS, or if you're using a compressed sparse row graph, the out-edges will have the same order as the order that they were inserted into the graph. Cheers, Doug
Douglas Gregor <doug.gregor <at> gmail.com> writes:
The document doesn't define this, but it should. It depends on precisely which graph type you're using, but...
If you're using an adjacency list with OutEdgeListS=setS, or if you're using an adjacency matrix, the out-edges will be ordered increasing order of the target. If you're using an adjacency list with any other OutEdgeListS, or if you're using a compressed sparse row graph, the out-edges will have the same order as the order that they were inserted into the graph.
Cheers, Doug
At the same time, I actually experimented to find out the answer, which coincides with your explanations. Thanks to you all! Shufei
participants (2)
-
Aaron Windsor -
Cromwell Enage -
Douglas Gregor -
Shufei Fan