[boost] [Graph] iterator range splitting

Subject: [boost] [Graph] iterator range splitting
From: Tim Keitt (tkeitt+list_at_[hidden])
Date: 2008-12-14 12:28:55

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/