
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/