[Graph] iterator range splitting
I've run into some problems with the Graph library as there is a lot of code that splits iterator ranges. An example of this is: (from depth_first_search.hpp) template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color) { // // should the below not be: // graph_traits<VertexListGraph>::iterator vi, vend; // tie(vi, vend) = vertices(g); // if ( vi == vend ) ... ??? // or perhaps to be more terse // if ( empty_range(vertices(g)) ) // where empty_range(g) compares first and second // if (vertices(g).first == vertices(g).second) return; depth_first_search(g, vis, color, *vertices(g).first); } This is causing problems in my code where I have defined custom graph classes. In my case out_edges(g) != out_edges(g) because memory is allocated within the out_edges call and successive calls will return different ranges (vertex ranges are not a problem in my case as I use a simple counting iterator). Must out_edges(g) == out_edges(g) for a graph class to meet the Graph library requirements? If not, then a good bit of the code needs to be altered and possibly some of the iterator macros deprecated. Below I've located every instance where the first or second member of an iterator pair is thrown away. These cases are only problematic if the retained iterator is later compared to an iterator from another range. The fix is simple. One only needs to retain both members of the iterator pair. I am willing to provide a patch if it is agreed that the current code is wrong. THK egrep '(vertices|edges)\(.*\)\.(first|second)' * adjacency_list_io.hpp: for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){ adjacency_list_io.hpp: for (ei = edges(graph).first; ei != edges(graph).second; ++ei){ adjacency_list_io.hpp: for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){ adjacency_matrix.hpp: return *vertices(g).first; adjacency_matrix.hpp: return *vertices(g).first; adj_list_serialize.hpp: for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi) { adj_list_serialize.hpp: for (ei = edges(graph).first; ei != edges(graph).second; ++ei){ bc_clustering.hpp: if (edges(g).first == edges(g).second) return; bc_clustering.hpp: edge_descriptor e = *max_element(edges(g).first, edges(g).second, cmp); bc_clustering.hpp: } while (!is_done && edges(g).first != edges(g).second); cuthill_mckee_ordering.hpp: if (vertices(G).first == vertices(G).second) cuthill_mckee_ordering.hpp: if (vertices(G).first == vertices(G).second) depth_first_search.hpp: if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g); depth_first_search.hpp: if (vertices(g).first == vertices(g).second) depth_first_search.hpp: depth_first_search(g, vis, color, *vertices(g).first); depth_first_search.hpp: if (vertices(g).first == vertices(g).second) depth_first_search.hpp: *vertices(g).first), edge_connectivity.hpp: std::set_difference(vertices(g).first, vertices(g).second, edge_connectivity.hpp: std::set_difference(vertices(g).first, vertices(g).second, fruchterman_reingold.hpp: Dim minX = position[*vertices(g).first].x, maxX = minX; fruchterman_reingold.hpp: Dim minY = position[*vertices(g).first].y, maxY = minY; graph_test.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; graph_test.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; howard_cycle_ratio.hpp: if (boost::out_edges(vd1, m_g).first == boost::out_edges(vd1, m_g).second) throw bad_graph(m_vim[vd1]); howard_cycle_ratio.hpp: mcr_edge_t ed = *boost::out_edges(vd1, m_g).first; howard_cycle_ratio.hpp: good_vertex = boost::target(*boost::out_edges(good_vertex, m_pi_g).first, m_pi_g); howard_cycle_ratio.hpp: pi_edge_t tmp_ed = *(boost::out_edges(vd, m_pi_g).first); howard_cycle_ratio.hpp: remove_edge(*(out_edges(m_g2pi_g_vm[vd], m_pi_g).first), m_pi_g); is_kuratowski_subgraph.hpp: bipartition_start = next(next(next(vertices(K_3_3).first))); is_kuratowski_subgraph.hpp: si = vertices(contracted_graph).first; isomorphism.hpp: for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first; isomorphism.hpp: e1 != edges(g1).second; ++e1) { isomorphism.hpp: for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first; isomorphism.hpp: e2 != edges(g2).second && !found_edge; ++e2) { iteration_macros.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; iteration_macros.hpp: BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \ johnson_all_pairs_shortest.hpp: typename Traits2::vertex_descriptor s = *vertices(g2).first; kamada_kawai_spring_layout.hpp: for (vertex_iterator ui = vertices(g).first, end = vertices(g).second; kamada_kawai_spring_layout.hpp: vertex_iterator ui, end = vertices(g).second; kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: vertex_descriptor p = *vertices(g).first; kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { king_ordering.hpp: if (vertices(G).first == vertices(G).second) king_ordering.hpp: if (vertices(G).first == vertices(G).second) metric_tsp_approx.hpp: Vertex v(*vertices(g).first); metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, w, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis); metric_tsp_approx.hpp: Tree t(mst, *vertices(mst).first, minimum_degree_ordering.hpp: adj_iter nu = adjacent_vertices(u_node, G).first; planar_canonical_ordering.hpp: vertex_t first_vertex = *vertices(g).first; prim_minimum_spanning_tree.hpp: choose_param(get_param(params, root_vertex_t()), *vertices(g).first), prim_minimum_spanning_tree.hpp: (g, *vertices(g).first, predecessor_map(p_map). property_iter_range.hpp: return std::make_pair(iter(vertices(graph).first, get(tag, graph)), property_iter_range.hpp: iter(vertices(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(vertices(graph).first, get(tag, graph)), property_iter_range.hpp: iter(vertices(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(edges(graph).first, get(tag, graph)), property_iter_range.hpp: iter(edges(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(edges(graph).first, get(tag, graph)), property_iter_range.hpp: iter(edges(graph).second, get(tag, graph))); push_relabel_max_flow.hpp: current(num_vertices(g_), out_edges(*vertices(g_).first, g_).second), push_relabel_max_flow.hpp: current[u] = out_edges(u, g).first; push_relabel_max_flow.hpp: current[v] = out_edges(v, g).first; push_relabel_max_flow.hpp: for (ai = current[u], ai_end = out_edges(u, g).second; push_relabel_max_flow.hpp: current[u] = out_edges(u, g).first; push_relabel_max_flow.hpp: for (; current[u] != out_edges(u, g).second; ++current[u]) { push_relabel_max_flow.hpp: if (current[u] == out_edges(u, g).second) { push_relabel_max_flow.hpp: ai = out_edges(u, g).first; push_relabel_max_flow.hpp: while (excess_flow[u] > 0 && ai != out_edges(u, g).second) { push_relabel_max_flow.hpp: ai = out_edges(u, g).first; random.hpp: i = vertices(g).first; random.hpp: return *vertices(g).first; random.hpp: i = edges(g).first; random.hpp: return *edges(g).first; sloan_ordering.hpp: s = *(vertices(G).first); undirected_dfs.hpp: if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex, g); undirected_dfs.hpp: undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first); undirected_dfs.hpp: *vertices(g).first), -- Timothy H. Keitt http://www.keittlab.org/
on Sun Dec 14 2008, "Tim Keitt" <tkeitt+list-AT-gmail.com> wrote:
I've run into some problems with the Graph library as there is a lot of code that splits iterator ranges. An example of this is:
(from depth_first_search.hpp)
template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color) { // // should the below not be: // graph_traits<VertexListGraph>::iterator vi, vend; // tie(vi, vend) = vertices(g); // if ( vi == vend ) ... ??? // or perhaps to be more terse // if ( empty_range(vertices(g)) ) // where empty_range(g) compares first and second // if (vertices(g).first == vertices(g).second) return;
depth_first_search(g, vis, color, *vertices(g).first); }
This is causing problems in my code where I have defined custom graph classes. In my case
out_edges(g) != out_edges(g)
because memory is allocated within the out_edges call and successive calls will return different ranges (vertex ranges are not a problem in my case as I use a simple counting iterator). Must out_edges(g) == out_edges(g) for a graph class to meet the Graph library requirements?
Hmm. Well, it doesn't look like that's a documented requirement, but maybe it should be (actually, out_edges(u,g) == out_edges(u,g)). After all, writing algorithms without making that assumption could be very difficult. I can even imagine that one might need to store these iterators (in a heap or something) and come back to them compare them with the end iterator later, which would be awkward at best and impossible at worst unless one could make that assumption.
If not, then a good bit of the code needs to be altered and possibly some of the iterator macros deprecated.
Below I've located every instance where the first or second member of an iterator pair is thrown away. These cases are only problematic if the retained iterator is later compared to an iterator from another range.
The fix is simple. One only needs to retain both members of the iterator pair. I am willing to provide a patch if it is agreed that the current code is wrong.
I'm not entirely against it, but I guess I'd need to be convinced that it was really a worthwhile generalization. Since your out_edges() calls are already heavyweight, why don't you do something to make iterators from consecutive calls compare equal? For example, you could store the source vertex descriptor and offset in them. If that's at all practical, I would consider it a fairly good argument for tightening the IncidenceGraph requirements a little bit so the assumption was valid. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sun, Dec 14, 2008 at 2:31 PM, David Abrahams <dave@boostpro.com> wrote:
on Sun Dec 14 2008, "Tim Keitt" <tkeitt+list-AT-gmail.com> wrote:
I've run into some problems with the Graph library as there is a lot of code that splits iterator ranges. An example of this is:
(from depth_first_search.hpp)
template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color) { // // should the below not be: // graph_traits<VertexListGraph>::iterator vi, vend; // tie(vi, vend) = vertices(g); // if ( vi == vend ) ... ??? // or perhaps to be more terse // if ( empty_range(vertices(g)) ) // where empty_range(g) compares first and second // if (vertices(g).first == vertices(g).second) return;
depth_first_search(g, vis, color, *vertices(g).first); }
This is causing problems in my code where I have defined custom graph classes. In my case
out_edges(g) != out_edges(g)
because memory is allocated within the out_edges call and successive calls will return different ranges (vertex ranges are not a problem in my case as I use a simple counting iterator). Must out_edges(g) == out_edges(g) for a graph class to meet the Graph library requirements?
Hmm. Well, it doesn't look like that's a documented requirement, but maybe it should be (actually, out_edges(u,g) == out_edges(u,g)). After
right -- forgot the vertex descriptor
all, writing algorithms without making that assumption could be very difficult. I can even imagine that one might need to store these iterators (in a heap or something) and come back to them compare them with the end iterator later, which would be awkward at best and impossible at worst unless one could make that assumption.
Its actually quite straightforward. All you need to do is store an iterator pair rather than an iterator. It was not hard to modify eg push_relabel_max_flow to store iterator pairs (currently it holds vectors of iterators that are incremented across several loops and if I recall across some function calls).
If not, then a good bit of the code needs to be altered and possibly some of the iterator macros deprecated.
Below I've located every instance where the first or second member of an iterator pair is thrown away. These cases are only problematic if the retained iterator is later compared to an iterator from another range.
The fix is simple. One only needs to retain both members of the iterator pair. I am willing to provide a patch if it is agreed that the current code is wrong.
I'm not entirely against it, but I guess I'd need to be convinced that it was really a worthwhile generalization.
Since your out_edges() calls are already heavyweight, why don't you do something to make iterators from consecutive calls compare equal? For example, you could store the source vertex descriptor and offset in them. If that's at all practical, I would consider it a fairly good argument for tightening the IncidenceGraph requirements a little bit so the assumption was valid.
What I am trying to achieve is to not have the entire graph in memory. Currently I use shared_container_iterator to iterate over out edges so they are deallocated when there are no more references. I can easily change that by holding onto a reference, but then I might as well copy everything into an adjacency_list since pretty much any use of the IncidenceGraph concept will call out_edges on every vertex. Storing an offset into the array is possible, but awkward as every call to out_edges issues a SQL query and allocates memory, so I would incur that overhead simply to retrieve the out degree (which would then be used to compare to the current value of the offset). THK
-- Dave Abrahams BoostPro Computing http://www.boostpro.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Timothy H. Keitt http://www.keittlab.org/
On Sun, Dec 14, 2008 at 3:22 PM, Tim Keitt <tkeitt@gmail.com> wrote:
On Sun, Dec 14, 2008 at 2:31 PM, David Abrahams <dave@boostpro.com> wrote:
on Sun Dec 14 2008, "Tim Keitt" <tkeitt+list-AT-gmail.com> wrote:
I've run into some problems with the Graph library as there is a lot of code that splits iterator ranges. An example of this is:
(from depth_first_search.hpp)
template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color) { // // should the below not be: // graph_traits<VertexListGraph>::iterator vi, vend; // tie(vi, vend) = vertices(g); // if ( vi == vend ) ... ??? // or perhaps to be more terse // if ( empty_range(vertices(g)) ) // where empty_range(g) compares first and second // if (vertices(g).first == vertices(g).second) return;
depth_first_search(g, vis, color, *vertices(g).first); }
This is causing problems in my code where I have defined custom graph classes. In my case
out_edges(g) != out_edges(g)
because memory is allocated within the out_edges call and successive calls will return different ranges (vertex ranges are not a problem in my case as I use a simple counting iterator). Must out_edges(g) == out_edges(g) for a graph class to meet the Graph library requirements?
Hmm. Well, it doesn't look like that's a documented requirement, but maybe it should be (actually, out_edges(u,g) == out_edges(u,g)). After
right -- forgot the vertex descriptor
all, writing algorithms without making that assumption could be very difficult. I can even imagine that one might need to store these iterators (in a heap or something) and come back to them compare them with the end iterator later, which would be awkward at best and impossible at worst unless one could make that assumption.
Its actually quite straightforward. All you need to do is store an iterator pair rather than an iterator. It was not hard to modify eg push_relabel_max_flow to store iterator pairs (currently it holds vectors of iterators that are incremented across several loops and if I recall across some function calls).
If not, then a good bit of the code needs to be altered and possibly some of the iterator macros deprecated.
Below I've located every instance where the first or second member of an iterator pair is thrown away. These cases are only problematic if the retained iterator is later compared to an iterator from another range.
The fix is simple. One only needs to retain both members of the iterator pair. I am willing to provide a patch if it is agreed that the current code is wrong.
I'm not entirely against it, but I guess I'd need to be convinced that it was really a worthwhile generalization.
Since your out_edges() calls are already heavyweight, why don't you do something to make iterators from consecutive calls compare equal? For example, you could store the source vertex descriptor and offset in them. If that's at all practical, I would consider it a fairly good argument for tightening the IncidenceGraph requirements a little bit so the assumption was valid.
What I am trying to achieve is to not have the entire graph in memory. Currently I use shared_container_iterator to iterate over out edges so they are deallocated when there are no more references. I can easily change that by holding onto a reference, but then I might as well copy everything into an adjacency_list since pretty much any use of the IncidenceGraph concept will call out_edges on every vertex.
Storing an offset into the array is possible, but awkward as every call to out_edges issues a SQL query and allocates memory, so I would incur that overhead simply to retrieve the out degree (which would then be used to compare to the current value of the offset).
Thinking about this more, it seems that if you are going to return iterator pairs, then it makes sense to assume they are unique per call and you should not compare iterators from different ranges (ie subsequent calls). Otherwise, I would suggest that calls like out_edges be split into out_edges_begin and out_edges_end because you may want very different things to happen when retrieving the beginning of a range and the end of a range. I will probably revert my code to simply copying the entire graph into an adjacency_list. Its a time-space trade-off and for many of the algorithms run-time will trump space efficiency anyway. I liked the idea of graph classes that use a database for storage, but it seems impractical with the current Graph library. THK
THK
-- Dave Abrahams BoostPro Computing http://www.boostpro.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Timothy H. Keitt http://www.keittlab.org/
-- Timothy H. Keitt http://www.keittlab.org/
on Mon Dec 15 2008, "Tim Keitt" <tkeitt-AT-gmail.com> wrote:
What I am trying to achieve is to not have the entire graph in memory. Currently I use shared_container_iterator to iterate over out edges so they are deallocated when there are no more references. I can easily change that by holding onto a reference, but then I might as well copy everything into an adjacency_list since pretty much any use of the IncidenceGraph concept will call out_edges on every vertex.
Storing an offset into the array is possible, but awkward as every call to out_edges issues a SQL query and allocates memory, so I would incur that overhead simply to retrieve the out degree (which would then be used to compare to the current value of the offset).
Well, you could also keep a cache of N recently-accessed out_edges results that would save you from the expense for trivial cases like the ones you've described.
Thinking about this more, it seems that if you are going to return iterator pairs, then it makes sense to assume they are unique per call and you should not compare iterators from different ranges (ie subsequent calls). Otherwise, I would suggest that calls like out_edges be split into out_edges_begin and out_edges_end because you may want very different things to happen when retrieving the beginning of a range and the end of a range.
You're making a good point.
I will probably revert my code to simply copying the entire graph into an adjacency_list. Its a time-space trade-off and for many of the algorithms run-time will trump space efficiency anyway. I liked the idea of graph classes that use a database for storage, but it seems impractical with the current Graph library.
I think you're giving up a little too easily on your ability to do it within the current library definition, and on influencing the library's design itself. As for a decision about changing BGL, I'm not that library's maintainer, so it's really not up to me. I tend to look for arguments on both sides, which I now have, before I make judgements about things like this. I guess the concepts need to be clarified, and clarifying them as you suggest (less strict) cannot break any code. If we discover the need for a StableOutEdgesGraph concept one day, it can certainly be added. I'm guessing that if you submit a patch for the library that updates the code and docs, and passes the library's test suite (you should test that yourself), it would probably be accepted. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Thinking about this more, it seems that if you are going to return iterator pairs, then it makes sense to assume they are unique per call and you should not compare iterators from different ranges (ie subsequent calls). Otherwise, I would suggest that calls like out_edges be split into out_edges_begin and out_edges_end because you may want very different things to happen when retrieving the beginning of a range and the end of a range.
You're making a good point.
I don't know that I agree with this - or perhaps I conditionally agree, depending on the concepts modeled by the custom graph - who knows. The IncidenceGraph, which defines the out_edges requirement is intended to abstract a view over a container. For adjacency lists, this is a transform iterator over a container's range. For an incidence list or adjaceny matrix, it's probably filter+transform iterator over the list of edges or row/column of a vertex. If you assume this property holds: make_pair(C.begin(), c.end()) == make_pair(C.begin(), C.end()) then it *should* follow that the ranges of adapted iterators also exhibit the same property. This is probably expressable as some kind of congruence relation. Something like: typedef adapted_iterator<C::iterator> iterator; make_pair(iterator(C.begin()), iterator(C.end())) == make_pair(iterator(C.begin()), iterator(C.end())) Obviously, allocating the range from an SQL query is substantially different than pulling iterators from an in-memory container, but I think I would argue that this property should be preserved. If you can make your out_edge_iterators model this behavior, then your graph should be interoperable. Of course, this is all conjeture, undocumented and up for discussion.
I will probably revert my code to simply copying the entire graph into
an adjacency_list. Its a time-space trade-off and for many of the algorithms run-time will trump space efficiency anyway. I liked the idea of graph classes that use a database for storage, but it seems impractical with the current Graph library.
I think you're giving up a little too easily on your ability to do it within the current library definition, and on influencing the library's design itself.
Agreed. I don't think that SQL-based graphs are necessarily impractical with the current implementation - just difficult to adapt. Of course, the same can probably be said about *any* custom graph type.
As for a decision about changing BGL, I'm not that library's maintainer, so it's really not up to me. I tend to look for arguments on both sides, which I now have, before I make judgements about things like this. I guess the concepts need to be clarified, and clarifying them as you suggest (less strict) cannot break any code. If we discover the need for a StableOutEdgesGraph concept one day, it can certainly be added.
I'm guessing that if you submit a patch for the library that updates the code and docs, and passes the library's test suite (you should test that yourself), it would probably be accepted.
I'm not against adding *begin and *end variants for the iterator ranges, but I'm not sure how much it actually gives you - except avoiding this notation: *vertices(g).first. Andrew Sutton andrew.n.sutton@gmail.com
on Tue Dec 16 2008, "Andrew Sutton" <andrew.n.sutton-AT-gmail.com> wrote:
Thinking about this more, it seems that if you are going to return iterator pairs, then it makes sense to assume they are unique per call and you should not compare iterators from different ranges (ie subsequent calls). Otherwise, I would suggest that calls like out_edges be split into out_edges_begin and out_edges_end because you may want very different things to happen when retrieving the beginning of a range and the end of a range.
You're making a good point.
I don't know that I agree with this - or perhaps I conditionally agree, depending on the concepts modeled by the custom graph - who knows.
The IncidenceGraph, which defines the out_edges requirement is intended to abstract a view over a container.
Iterators are intended to be an abstraction of pointers, and yet not all categories carry the same requirements as pointers, and we're even going to drop the *p => T& requirement for random access iterators in C++0x.
For adjacency lists, this is a transform iterator over a container's range.
Yes, but a transform is not necessarily a projection.
For an incidence list or adjaceny matrix, it's probably filter+transform iterator over the list of edges or row/column of a vertex. If you assume this property holds:
make_pair(C.begin(), c.end()) == make_pair(C.begin(), C.end())
then it *should* follow that the ranges of adapted iterators also exhibit the same property. This is probably expressable as some kind of congruence relation. Something like:
typedef adapted_iterator<C::iterator> iterator; make_pair(iterator(C.begin()), iterator(C.end())) == make_pair(iterator(C.begin()), iterator(C.end()))
Obviously, allocating the range from an SQL query is substantially different than pulling iterators from an in-memory container, but I think I would argue that this property should be preserved.
That was my initial instinct, too. but Tim is pointing out that the algorithms can all be raised to a higher level of generality without loss of efficiency, and I am now inclined to agree that there's no reason they need to reply on this property.
If you can make your out_edge_iterators model this behavior, then your graph should be interoperable.
Of course, this is all conjeture, undocumented and up for discussion.
I'm guessing that if you submit a patch for the library that updates the code and docs, and passes the library's test suite (you should test that yourself), it would probably be accepted.
I'm not against adding *begin and *end variants for the iterator ranges, but I'm not sure how much it actually gives you - except avoiding this notation: *vertices(g).first.
That's not the patch I (or Tim, I think) had in mind. I'm talking about changing the algorithms so they no longer rely on out_edges(u,g) == out_edges(u,g) and updating the documentation to make it completely clear that the property just stated is not part of the concept requirements. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Yes, but a transform is not necessarily a projection.
typedef adapted_iterator<C::iterator> iterator; make_pair(iterator(C.begin()), iterator(C.end())) == make_pair(iterator(C.begin()), iterator(C.end()))
That was my initial instinct, too. but Tim is pointing out that the algorithms can all be raised to a higher level of generality without loss of efficiency, and I am now inclined to agree that there's no reason they need to reply on this property.
Good point. I concede :) I think this property is still valid in many cases - and I think the expected behavior of range-generating functions. I suppose this could be defined as a concept, but I'm not sure how many templates take range-generating functions as parameters. Probably none in the BGL. That's not the patch I (or Tim, I think) had in mind. I'm talking
about changing the algorithms so they no longer rely on out_edges(u,g) == out_edges(u,g) and updating the documentation to make it completely clear that the property just stated is not part of the concept requirements.
I know, but it was mentioned. It might also be better applied in cases where an iterator from the range is discarded. Andrew Sutton andrew.n.sutton@gmail.com
On Tue, Dec 16, 2008 at 1:06 PM, David Abrahams <dave@boostpro.com> wrote:
on Tue Dec 16 2008, "Andrew Sutton" <andrew.n.sutton-AT-gmail.com> wrote:
Thinking about this more, it seems that if you are going to return iterator pairs, then it makes sense to assume they are unique per call and you should not compare iterators from different ranges (ie subsequent calls). Otherwise, I would suggest that calls like out_edges be split into out_edges_begin and out_edges_end because you may want very different things to happen when retrieving the beginning of a range and the end of a range.
You're making a good point.
I don't know that I agree with this - or perhaps I conditionally agree, depending on the concepts modeled by the custom graph - who knows.
The IncidenceGraph, which defines the out_edges requirement is intended to abstract a view over a container.
Iterators are intended to be an abstraction of pointers, and yet not all categories carry the same requirements as pointers, and we're even going to drop the *p => T& requirement for random access iterators in C++0x.
For adjacency lists, this is a transform iterator over a container's range.
Yes, but a transform is not necessarily a projection.
For an incidence list or adjaceny matrix, it's probably filter+transform iterator over the list of edges or row/column of a vertex. If you assume this property holds:
make_pair(C.begin(), c.end()) == make_pair(C.begin(), C.end())
then it *should* follow that the ranges of adapted iterators also exhibit the same property. This is probably expressable as some kind of congruence relation. Something like:
typedef adapted_iterator<C::iterator> iterator; make_pair(iterator(C.begin()), iterator(C.end())) == make_pair(iterator(C.begin()), iterator(C.end()))
Obviously, allocating the range from an SQL query is substantially different than pulling iterators from an in-memory container, but I think I would argue that this property should be preserved.
That was my initial instinct, too. but Tim is pointing out that the algorithms can all be raised to a higher level of generality without loss of efficiency, and I am now inclined to agree that there's no reason they need to reply on this property.
If you can make your out_edge_iterators model this behavior, then your graph should be interoperable.
Of course, this is all conjeture, undocumented and up for discussion.
I'm guessing that if you submit a patch for the library that updates the code and docs, and passes the library's test suite (you should test that yourself), it would probably be accepted.
I'm not against adding *begin and *end variants for the iterator ranges, but I'm not sure how much it actually gives you - except avoiding this notation: *vertices(g).first.
That's not the patch I (or Tim, I think) had in mind. I'm talking about changing the algorithms so they no longer rely on out_edges(u,g) == out_edges(u,g) and updating the documentation to make it completely clear that the property just stated is not part of the concept requirements.
I've checked out http://svn.boost.org/svn/boost/trunk/boost/graph and have converted almost all the cases where iterators are compared across calls. A few questions: 1) does something like template<class T> inline bool equal_pair(const std::pair<T, T>& p) { return p.first == p.second; } exist somewhere in std or boost? If not would it be useful to add? It would help with eg if ( equal_pair(vertices(g)) ) ... 2) what is the best way to test changes to the graph library? 3) I assume svn diff is sufficient. How do I submit the patch? THK
-- Dave Abrahams BoostPro Computing http://www.boostpro.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Timothy H. Keitt http://www.keittlab.org/
1) does something like
template<class T> inline bool equal_pair(const std::pair<T, T>& p) { return p.first == p.second; }
exist somewhere in std or boost? If not would it be useful to add? It would help with eg if ( equal_pair(vertices(g)) ) ...
If you're treating the pair as an iterator range, I believe Boost.Range has an overload named empty() that will do that for you. Otherwise, it would probably okay to stick it in graph_utility.hpp.
2) what is the best way to test changes to the graph library?
Build and run the test suite. You'll have to use bjam for that.
3) I assume svn diff is sufficient. How do I submit the patch?
Post the diff here. I'll pull it, apply it, and re-test it on my build systems. Andrew Sutton andrew.n.sutton@gmail.com
Hi Tim/Andrew, Was wondering if the splitting of out_edges range got fixed. thanks Sandeep On Wed, Dec 17, 2008 at 7:52 PM, Andrew Sutton<andrew.n.sutton@gmail.com> wrote:
1) does something like
template<class T> inline bool equal_pair(const std::pair<T, T>& p) { return p.first == p.second; }
exist somewhere in std or boost? If not would it be useful to add? It would help with eg if ( equal_pair(vertices(g)) ) ...
If you're treating the pair as an iterator range, I believe Boost.Range has an overload named empty() that will do that for you. Otherwise, it would probably okay to stick it in graph_utility.hpp.
2) what is the best way to test changes to the graph library?
Build and run the test suite. You'll have to use bjam for that.
3) I assume svn diff is sufficient. How do I submit the patch?
Post the diff here. I'll pull it, apply it, and re-test it on my build systems.
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Fri, 26 Jun 2009, Sandeep Gupta wrote:
Hi Tim/Andrew, Was wondering if the splitting of out_edges range got fixed.
Are you talking about minimizing the number of calls to vertices() and out_edges()? If so, that was put in a while ago. Please note the information from the previous emails that you should not rely on being able to create new containers for each call, though, since new algorithms might not respect this particular implementation detail. -- Jeremiah Willcock
Hi Jeremiah, The issue Tim brought up was regarding the case when the graph is not fully read in the main memory. Instead memory is allocated per out_edges invocation. For this to work the algorithm should not break range obtained from a out_edges call. However current implementation of dijkstra's does exactly that. -- an example of range split: "depth_first_search(g, vis, color, *vertices(g).first);" Tim proposed that he should be able to provide patch to fix such cases. I hope he has because for my current project I intend to process a graph stored externally. thanks Sandeep On Fri, Jun 26, 2009 at 3:22 PM, Jeremiah Willcock<jewillco@osl.iu.edu> wrote:
On Fri, 26 Jun 2009, Sandeep Gupta wrote:
Hi Tim/Andrew, Was wondering if the splitting of out_edges range got fixed.
Are you talking about minimizing the number of calls to vertices() and out_edges()? If so, that was put in a while ago. Please note the information from the previous emails that you should not rely on being able to create new containers for each call, though, since new algorithms might not respect this particular implementation detail.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Fri, 26 Jun 2009, Sandeep Gupta wrote:
Hi Jeremiah, The issue Tim brought up was regarding the case when the graph is not fully read in the main memory. Instead memory is allocated per out_edges invocation. For this to work the algorithm should not break range obtained from a out_edges call. However current implementation of dijkstra's does exactly that.
-- an example of range split: "depth_first_search(g, vis, color, *vertices(g).first);"
Tim proposed that he should be able to provide patch to fix such cases. I hope he has because for my current project I intend to process a graph stored externally.
What is wrong with the call to depth_first_search? That is getting a single vertex, not the whole range. I applied the kinds of things that were in his patch (not always in the same way), so his issues should be fixed. BGL was not built for out-of-core applications, though, so a lot of the changes are implementation details that can't really be relied upon. Are you trying to page in and out edge sets as needed, and that's why you need ranges to be used more consistently? -- Jeremiah Willcock
On Fri, Jun 26, 2009 at 4:15 PM, Jeremiah Willcock<jewillco@osl.iu.edu> wrote:
On Fri, 26 Jun 2009, Sandeep Gupta wrote:
Hi Jeremiah, The issue Tim brought up was regarding the case when the graph is not fully read in the main memory. Instead memory is allocated per out_edges invocation. For this to work the algorithm should not break range obtained from a out_edges call. However current implementation of dijkstra's does exactly that.
-- an example of range split: "depth_first_search(g, vis, color, *vertices(g).first);"
Tim proposed that he should be able to provide patch to fix such cases. I hope he has because for my current project I intend to process a graph stored externally.
What is wrong with the call to depth_first_search? That is getting a single vertex, not the whole range. I applied the kinds of things that were in his patch (not always in the same way), so his issues should be fixed. BGL was not built for out-of-core applications, though, so a lot of the changes are implementation details that can't really be relied upon. Are you trying to page in and out edge sets as needed, and that's why you need ranges to be used more consistently?
Yes, ideally i would like to page-in and -out the edge sets. Glad to know that these issues are fixed. I believe that as long as the calls to out_edges are indepenet/decoupled paging-in and -out should work. Although I will double check things once i get around to implementing it. -thanks sandeep
On Fri, Jun 26, 2009 at 6:33 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Fri, Jun 26, 2009 at 4:15 PM, Jeremiah Willcock<jewillco@osl.iu.edu> wrote:
On Fri, 26 Jun 2009, Sandeep Gupta wrote:
Hi Jeremiah, The issue Tim brought up was regarding the case when the graph is not fully read in the main memory. Instead memory is allocated per out_edges invocation. For this to work the algorithm should not break range obtained from a out_edges call. However current implementation of dijkstra's does exactly that.
-- an example of range split: "depth_first_search(g, vis, color, *vertices(g).first);"
Tim proposed that he should be able to provide patch to fix such cases. I hope he has because for my current project I intend to process a graph stored externally.
What is wrong with the call to depth_first_search? That is getting a single vertex, not the whole range. I applied the kinds of things that were in his patch (not always in the same way), so his issues should be fixed. BGL was not built for out-of-core applications, though, so a lot of the changes are implementation details that can't really be relied upon. Are you trying to page in and out edge sets as needed, and that's why you need ranges to be used more consistently?
Yes, ideally i would like to page-in and -out the edge sets. Glad to know that these issues are fixed. I believe that as long as the calls to out_edges are indepenet/decoupled paging-in and -out should work. Although I will double check things once i get around to implementing
Sandeep, Check the current trunk. I think all the "problem" cases are now fixed. Most notably, the iteration macros now only compare iterators from the same call to vertices, edges, et al. so algorithms that rely on those will work in cases where each call produces a new iterator range. The changes were motivated by storing edges in postgresql: https://launchpad.net/postgraph. THK
it.
-thanks sandeep _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Timothy H. Keitt http://www.keittlab.org/
On Sat, Jun 27, 2009 at 3:44 PM, Tim Keitt<tkeitt@gmail.com> wrote:
On Fri, Jun 26, 2009 at 6:33 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Fri, Jun 26, 2009 at 4:15 PM, Jeremiah Willcock<jewillco@osl.iu.edu> wrote:
On Fri, 26 Jun 2009, Sandeep Gupta wrote:
Hi Jeremiah, The issue Tim brought up was regarding the case when the graph is not fully read in the main memory. Instead memory is allocated per out_edges invocation. For this to work the algorithm should not break range obtained from a out_edges call. However current implementation of dijkstra's does exactly that.
-- an example of range split: "depth_first_search(g, vis, color, *vertices(g).first);"
Tim proposed that he should be able to provide patch to fix such cases. I hope he has because for my current project I intend to process a graph stored externally.
What is wrong with the call to depth_first_search? That is getting a single vertex, not the whole range. I applied the kinds of things that were in his patch (not always in the same way), so his issues should be fixed. BGL was not built for out-of-core applications, though, so a lot of the changes are implementation details that can't really be relied upon. Are you trying to page in and out edge sets as needed, and that's why you need ranges to be used more consistently?
Yes, ideally i would like to page-in and -out the edge sets. Glad to know that these issues are fixed. I believe that as long as the calls to out_edges are indepenet/decoupled paging-in and -out should work. Although I will double check things once i get around to implementing
Sandeep,
Check the current trunk. I think all the "problem" cases are now fixed. Most notably, the iteration macros now only compare iterators from the same call to vertices, edges, et al. so algorithms that rely on those will work in cases where each call produces a new iterator range. The changes were motivated by storing edges in postgresql: https://launchpad.net/postgraph.
THK
Would do so. Thanks for clarifying and also for postgraph. -sandeep
participants (6)
-
Andrew Sutton -
David Abrahams -
Jeremiah Willcock -
Sandeep Gupta -
Tim Keitt -
Tim Keitt