Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r53655 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-06-05 14:21:43


Author: jewillco
Date: 2009-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
New Revision: 53655
URL: http://svn.boost.org/trac/boost/changeset/53655

Log:
Reverted old version of CSR graph for compatibility, with a #define to switch between the modes; cleaned up interface of new CSR graph; fixed tests and docs accordingly
Text files modified:
   trunk/boost/graph/compressed_sparse_row_graph.hpp | 231 ++++++++++++++++++++++++++++++++++++---
   trunk/libs/graph/doc/compressed_sparse_row.html | 119 +++++++++++++++++--
   trunk/libs/graph/test/csr_graph_test.cpp | 28 ++++
   3 files changed, 336 insertions(+), 42 deletions(-)

Modified: trunk/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ trunk/boost/graph/compressed_sparse_row_graph.hpp 2009-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
@@ -1,4 +1,4 @@
-// Copyright 2005-2006 The Trustees of Indiana University.
+// Copyright 2005-2009 The Trustees of Indiana University.
 
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
@@ -38,6 +38,17 @@
 # error You will need a compiler that conforms better to the C++ standard.
 #endif
 
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+#warning "Using deprecated BGL compressed sparse row graph interface --"
+#warning "please see the documentation for the new interface and then"
+#warning "#define BOOST_GRAPH_USE_NEW_CSR_INTERFACE before including"
+#warning "<boost/graph/compressed_sparse_row_graph.hpp>"
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+#define BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+#endif
+
 namespace boost {
 
 // A tag type indicating that the graph in question is a compressed
@@ -51,6 +62,14 @@
 inline void edges_are_sorted(edges_are_sorted_internal) {}
 typedef void (*edges_are_sorted_t)(edges_are_sorted_internal);
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
+// indicate that the edge list passed into the CSR graph is not sorted by
+// source vertex.
+struct edges_are_unsorted_internal {};
+inline void edges_are_unsorted(edges_are_unsorted_internal) {}
+typedef void (*edges_are_unsorted_t)(edges_are_unsorted_internal);
+
 // A type (construct_inplace_from_sources_and_targets_t) and a value
 // (construct_inplace_from_sources_and_targets) used to indicate that mutable
 // vectors of sources and targets (and possibly edge properties) are being used
@@ -73,6 +92,8 @@
 inline void construct_inplace_from_sources_and_targets_global(construct_inplace_from_sources_and_targets_global_internal) {}
 typedef void (*construct_inplace_from_sources_and_targets_global_t)(construct_inplace_from_sources_and_targets_global_internal);
 
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
 /****************************************************************************
  * Local helper macros to reduce typing and clutter later on. *
  ****************************************************************************/
@@ -88,6 +109,7 @@
 template<typename Vertex, typename EdgeIndex>
 class csr_edge_descriptor;
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 namespace detail {
   // Less-than operator for comparing only the first elements of two arbitrary
   // Boost tuples
@@ -98,6 +120,7 @@
     }
   };
 }
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
 /** Compressed sparse row graph.
  *
@@ -199,26 +222,34 @@
 
   // Default constructor: an empty graph.
   compressed_sparse_row_graph()
- : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property(),
- m_last_source(0) {}
+ : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property()
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ , m_last_source(0)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ {}
 
   // With numverts vertices
   compressed_sparse_row_graph(vertices_size_type numverts)
     : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_last_source(numverts)
+ m_column(0)
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ , m_last_source(numverts)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
   {
     for (Vertex v = 0; v < numverts + 1; ++v)
       m_rowstart[v] = 0;
   }
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // From number of vertices and unsorted list of edges
   template <typename MultiPassInputIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin,
                               MultiPassInputIterator edge_end,
                               vertices_size_type numverts,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), m_property(prop)
   {
     // Put the degree of each vertex v into m_rowstart[v + 1]
     for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
@@ -248,13 +279,14 @@
 
   // From number of vertices and unsorted list of edges, plus edge properties
   template <typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin,
                               MultiPassInputIterator edge_end,
                               EdgePropertyIterator ep_iter,
                               vertices_size_type numverts,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), m_property(prop)
   {
     // Put the degree of each vertex v into m_rowstart[v + 1]
     for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
@@ -284,8 +316,94 @@
       inherited_edge_properties::write_by_index(insert_pos, *ep_iter);
     }
   }
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+
+ // From number of vertices and sorted list of edges (deprecated
+ // interface)
+ template<typename InputIterator>
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
+ m_column(0), m_property(prop), m_last_source(numverts)
+ {
+ // Reserving storage in advance can save us lots of time and
+ // memory, but it can only be done if we have forward iterators or
+ // the user has supplied the number of edges.
+ if (numedges == 0) {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category
+ category;
+ maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
+ } else {
+ m_column.reserve(numedges);
+ }
+
+ EdgeIndex current_edge = 0;
+ Vertex current_vertex_plus_one = 1;
+ m_rowstart[0] = 0;
+ for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
+ Vertex src = ei->first;
+ Vertex tgt = ei->second;
+ for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ m_column.push_back(tgt);
+ ++current_edge;
+ }
+
+ // The remaining vertices have no edges
+ for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+
+ // Default-construct properties for edges
+ inherited_edge_properties::resize(m_column.size());
+ }
+
+ // From number of vertices and sorted list of edges (deprecated
+ // interface)
+ template<typename InputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
+ m_column(0), m_property(prop), m_last_source(numverts)
+ {
+ // Reserving storage in advance can save us lots of time and
+ // memory, but it can only be done if we have forward iterators or
+ // the user has supplied the number of edges.
+ if (numedges == 0) {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category
+ category;
+ maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
+ } else {
+ m_column.reserve(numedges);
+ }
+
+ EdgeIndex current_edge = 0;
+ Vertex current_vertex_plus_one = 1;
+ m_rowstart[0] = 0;
+ for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
+ Vertex src = ei->first;
+ Vertex tgt = ei->second;
+ for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ m_column.push_back(tgt);
+ inherited_edge_properties::push_back(*ep_iter);
+ ++current_edge;
+ }
+
+ // The remaining vertices have no edges
+ for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ }
+
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
 
- // From number of vertices and sorted list of edges
+ // From number of vertices and sorted list of edges (new interface)
   template<typename InputIterator>
   compressed_sparse_row_graph(edges_are_sorted_t,
                               InputIterator edge_begin, InputIterator edge_end,
@@ -293,7 +411,10 @@
                               edges_size_type numedges = 0,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), m_property(prop)
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ , m_last_source(numverts)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
   {
     // Reserving storage in advance can save us lots of time and
     // memory, but it can only be done if we have forward iterators or
@@ -326,7 +447,7 @@
     inherited_edge_properties::resize(m_column.size());
   }
 
- // From number of vertices and sorted list of edges
+ // From number of vertices and sorted list of edges (new interface)
   template<typename InputIterator, typename EdgePropertyIterator>
   compressed_sparse_row_graph(edges_are_sorted_t,
                               InputIterator edge_begin, InputIterator edge_end,
@@ -335,7 +456,10 @@
                               edges_size_type numedges = 0,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), m_property(prop)
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ , m_last_source(numverts)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
   {
     // Reserving storage in advance can save us lots of time and
     // memory, but it can only be done if we have forward iterators or
@@ -366,6 +490,7 @@
       m_rowstart[current_vertex_plus_one] = current_edge;
   }
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // From number of vertices and mutable vectors of sources and targets;
   // vectors are returned with unspecified contents but are guaranteed not to
   // share storage with the constructed graph.
@@ -375,7 +500,7 @@
                               vertices_size_type numverts,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numverts)
+ m_column(), m_property(prop)
   {
     assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
   }
@@ -393,7 +518,7 @@
                               GlobalToLocal global_to_local,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numlocalverts)
+ m_column(), m_property(prop)
   {
     assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
   }
@@ -408,7 +533,7 @@
                               vertices_size_type numverts,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numverts)
+ m_column(), m_property(prop)
   {
     assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
   }
@@ -427,7 +552,7 @@
                               GlobalToLocal global_to_local,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numlocalverts)
+ m_column(), m_property(prop)
   {
     assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
   }
@@ -551,13 +676,15 @@
     this->m_edge_properties.swap(edge_props);
   }
 
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
 
   // Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function
   template<typename Graph, typename VertexIndexMap>
   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
                               vertices_size_type numverts,
                               edges_size_type numedges)
- : m_property(), m_last_source(0)
+ : m_property()
   {
     assign(g, vi, numverts, numedges);
   }
@@ -565,7 +692,7 @@
   // Requires VertexListGraph and EdgeListGraph
   template<typename Graph, typename VertexIndexMap>
   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
- : m_property(), m_last_source(0)
+ : m_property()
   {
     assign(g, vi, num_vertices(g), num_edges(g));
   }
@@ -573,7 +700,7 @@
   // Requires vertex index map plus requirements of previous constructor
   template<typename Graph>
   explicit compressed_sparse_row_graph(const Graph& g)
- : m_property(), m_last_source(0)
+ : m_property()
   {
     assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
   }
@@ -598,13 +725,24 @@
     for (Vertex i = 0; i != numverts; ++i) {
       m_rowstart[i] = current_edge;
       g_vertex v = vertex(i, g);
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ // Out edges in a single vertex are only sorted for the old interface
+ EdgeIndex num_edges_before_this_vertex = current_edge;
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
       g_out_edge_iter ei, ei_end;
       for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
         m_column[current_edge++] = get(vi, target(*ei, g));
       }
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ // Out edges in a single vertex are only sorted for the old interface
+ std::sort(m_column.begin() + num_edges_before_this_vertex,
+ m_column.begin() + current_edge);
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
     }
     m_rowstart[numverts] = current_edge;
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
     m_last_source = numverts;
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
   }
 
   // Requires the above, plus VertexListGraph and EdgeListGraph
@@ -633,7 +771,11 @@
   std::vector<EdgeIndex> m_rowstart;
   std::vector<Vertex> m_column;
   GraphProperty m_property;
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ // This member is only needed to support add_edge(), which is not provided by
+ // the new interface
   Vertex m_last_source; // Last source of added edge, plus one
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
 };
 
 template<typename Vertex, typename EdgeIndex>
@@ -690,8 +832,9 @@
   return old_num_verts_plus_one - 1;
 }
 
-// This function requires that src be at least as large as the largest source
-// in the graph so far
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+// This function requires that (src, tgt) be lexicographically at least as
+// large as the largest edge in the graph so far
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
 add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) {
@@ -724,7 +867,7 @@
   g.edge_properties().push_back(p);
   return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
 }
-
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
 
 // From VertexListGraph
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -835,6 +978,43 @@
   return i;
 }
 
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+// These require that the out edges from a vertex are sorted, which is only
+// guaranteed by the old interface
+
+// Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))
+// time
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
+ typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
+edge_range(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
+{
+ typedef typename std::vector<Vertex>::const_iterator adj_iter;
+ typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
+ typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edge_desc;
+ std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
+ std::pair<adj_iter, adj_iter> adjacencies =
+ std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
+ EdgeIndex idx_begin = adjacencies.first - g.m_column.begin();
+ EdgeIndex idx_end = adjacencies.second - g.m_column.begin();
+ return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
+ out_edge_iter(edge_desc(i, idx_end)));
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
+edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
+{
+ typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
+ std::pair<out_edge_iter, out_edge_iter> range = edge_range(i, j, g);
+ if (range.first == range.second)
+ return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
+ false);
+ else
+ return std::make_pair(*range.first, true);
+}
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+
 // Find an edge given its index in the graph
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
@@ -844,7 +1024,14 @@
   assert (idx < num_edges(g));
   row_start_iter src_plus_1 =
     std::upper_bound(g.m_rowstart.begin(),
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ // This handles the case where there are some vertices
+ // with rowstart 0 after the last provided vertex; this
+ // case does not happen with the new interface
                      g.m_rowstart.begin() + g.m_last_source + 1,
+#else // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ g.m_rowstart.end(),
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
                      idx);
     // Get last source whose rowstart is at most idx
     // upper_bound returns this position plus 1

Modified: trunk/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- trunk/libs/graph/doc/compressed_sparse_row.html (original)
+++ trunk/libs/graph/doc/compressed_sparse_row.html 2009-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
@@ -1,7 +1,7 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
 <html>
 <!--
- Copyright (c) 2005 Trustees of Indiana University
+ Copyright (c) 2005-2009 Trustees of Indiana University
     
      Distributed under the Boost Software License, Version 1.0.
      (See accompanying file LICENSE_1_0.txt or copy at
@@ -47,6 +47,17 @@
     or edges from a CSR graph. Use this format in high-performance
     applications or for very large graphs that you do not need to
     change.</p>
+
+ <p>There are two interfaces to the compressed sparse row graph. The
+ old interface requires that all out edges from a single vertex are
+ sorted by target, and does not support construction of the graph from
+ unsorted arrays of sources and targets. The new interface has these
+ new constructors, but does not support incremental construction of the
+ graph or the <tt>edge_range()</tt> and <tt>edge()</tt> functions. The
+ old interface is the default, but will be removed in a later version of
+ Boost. To select the new interface, add <tt>#define
+ BOOST_GRAPH_USE_NEW_CSR_INTERFACE</tt> before including
+ <tt>&lt;boost/graph/compressed_sparse_row_graph.hpp&gt;</tt>.</p>
         
     <p>The CSR format stores vertices and edges in separate arrays,
     with the indices into these arrays corresponding to the identifier
@@ -103,17 +114,35 @@
   <i>// Graph constructors</i>
   <a href="#default-const">compressed_sparse_row_graph</a>();
 
+ <i>// Unsorted edge list constructors <b>(new interface only)</b></i>
   template&lt;typename MultiPassInputIterator&gt;
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
                               vertices_size_type numverts,
                               const GraphProperty&amp; prop = GraphProperty());
 
   template&lt;typename MultiPassInputIterator, typename EdgePropertyIterator&gt;
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
                               EdgePropertyIterator ep_iter,
                               vertices_size_type numverts,
                               const GraphProperty&amp; prop = GraphProperty());
 
+ <i>// Old sorted edge list constructors <b>(old interface only)</b></i>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
+
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
+
+ <i>// New sorted edge list constructors <b>(both interfaces)</b></i>
   template&lt;typename InputIterator&gt;
   <a href="#edge-sorted-const">compressed_sparse_row_graph</a>(edges_are_sorted_t,
                               InputIterator edge_begin, InputIterator edge_end,
@@ -129,6 +158,7 @@
                               edges_size_type numedges = 0,
                               const GraphProperty&amp; prop = GraphProperty());
 
+ <i>// In-place unsorted edge list constructors <b>(new interface only)</b></i>
   template&lt;typename InputIterator&gt;
   <a href="#edge-inplace-const">compressed_sparse_row_graph</a>(construct_inplace_from_sources_and_targets_t,
                               std::vector&lt;vertex_descriptor&gt;&amp; sources,
@@ -144,6 +174,7 @@
                               vertices_size_type numverts,
                               const GraphProperty&amp; prop = GraphProperty());
 
+ <i>// Miscellaneous constructors <b>(both interfaces)</b></i>
   template&lt;typename Graph, typename VertexIndexMap&gt;
   <a href="#graph-const">compressed_sparse_row_graph</a>(const Graph&amp; g, const VertexIndexMap&amp; vi,
                               vertices_size_type numverts,
@@ -155,7 +186,7 @@
   template&lt;typename Graph&gt;
   explicit compressed_sparse_row_graph(const Graph&amp; g);
 
- <i>// Graph mutators</i>
+ <i>// Graph mutators (both interfaces)</i>
   template&lt;typename Graph, typename VertexIndexMap&gt;
   void assign(const Graph&amp; g, const VertexIndexMap&amp; vi,
               vertices_size_type numverts, edges_size_type numedges);
@@ -166,36 +197,46 @@
   template&lt;typename Graph&gt;
   void assign(const Graph&amp; g);
 
- <i>// Property Access</i>
+ <i>// Property Access (both interfaces)</i>
   VertexProperty&amp; operator[](vertex_descriptor v);
   const VertexProperty&amp; operator[](vertex_descriptor v) const;
   EdgeProperty&amp; operator[](edge_descriptor v);
   const EdgeProperty&amp; operator[](edge_descriptor v) const;
 };
 
-<i>// Incidence Graph requirements</i>
+<i>// Incidence Graph requirements (both interfaces)</i>
 vertex_descriptor source(edge_descriptor, const compressed_sparse_row_graph&amp;);
 vertex_descriptor target(edge_descriptor, const compressed_sparse_row_graph&amp;);
 std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
   out_edges(vertex_descriptor, const compressed_sparse_row_graph&amp;);
 degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&amp;);
 
-<i>// Adjacency Graph requirements</i>
+<i>// Adjacency Graph requirements (both interfaces)</i>
 std::pair&lt;adjacency_iterator, adjacency_iterator&gt;
   adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&amp;);
 
-<i>// Vertex List Graph requirements</i>
+<i>// Vertex List Graph requirements (both interfaces)</i>
 std::pair&lt;vertex_iterator, vertex_iterator&gt; vertices(const compressed_sparse_row_graph&amp;);
 vertices_size_type num_vertices(const compressed_sparse_row_graph&amp;);
 
-<i>// Edge List Graph requirements</i>
+<i>// Edge List Graph requirements (both interfaces)</i>
 std::pair&lt;edge_iterator, edge_iterator&gt; edges(const compressed_sparse_row_graph&amp;);
 edges_size_type num_edges(const compressed_sparse_row_graph&amp;);
 
-<i>// Vertex access</i>
+<i>// Vertex access (both interfaces)</i>
 vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&amp;);
 
-<i>// Property map accessors</i>
+<i>// Edge access</i>
+<b>(old interface only)</b>
+std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
+ edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
+<b>(old interface only)</b>
+std::pair&lt;edge_descriptor, bool&gt;
+ edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
+<b>(both interfaces)</b>
+edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&amp;);
+
+<i>// Property map accessors (both interfaces)</i>
 template&lt;typename PropertyTag&gt;
 property_map&lt;compressed_sparse_row_graph, PropertyTag&gt;::type
 <a href="#get">get</a>(PropertyTag, compressed_sparse_row_graph&amp; g)
@@ -223,7 +264,7 @@
 void set_property(const compressed_sparse_row_graph&amp; g, GraphPropertyTag,
                   const typename graph_property&lt;compressed_sparse_row_graph, GraphPropertyTag&gt;::type&amp; value);
 
-<i>// Incremental construction functions</i>
+<i>// Incremental construction functions (old interface only)</i>
 template&lt;typename Graph&gt;
 vertex_descriptor add_vertex(compressed_sparse_row_graph&amp; g);
 
@@ -231,7 +272,7 @@
 vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph&amp; g);
 
 template&lt;typename Graph&gt;
-edge_descriptor add_vertices(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph&amp; g);
+edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph&amp; g);
 
 } <i>// end namespace boost</i>
    </pre>
@@ -361,7 +402,8 @@
 
     <pre><a name="edge-const"></a>
   template&lt;typename MultiPassInputIterator&gt;
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
                               vertices_size_type numverts,
                               const GraphProperty&amp; prop = GraphProperty());
     </pre>
@@ -377,6 +419,7 @@
       vertices for the edges, and must fall within the range <code>[0,
       numverts)</code>. The edges in <code>[edge_begin,
       edge_end)</code> do not need to be sorted.
+ <b>(This function is only provided by the new interface.)</b>
     </p>
 
     <p class="indent">
@@ -388,7 +431,8 @@
 
     <pre><a name="edge-prop-const"></a>
   template&lt;typename MultiPassInputIterator, typename EdgePropertyIterator&gt;
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
                               EdgePropertyIterator ep_iter,
                               vertices_size_type numverts,
                               const GraphProperty&amp; prop = GraphProperty());
@@ -406,6 +450,7 @@
         m)</tt> will be used to initialize the properties on the edges
       of the graph, where <tt>m</tt> is distance from
       <tt>edge_begin</tt> to <tt>edge_end</tt>.
+ <b>(This function is only provided by the new interface.)</b>
     </p>
 
     <hr></hr>
@@ -434,7 +479,9 @@
       numverts)</code>. The edges in <code>[edge_begin,
       edge_end)</code> must be sorted so that all edges originating
       from vertex <i>i</i> preceed any edges originating from all
- vertices <i>j</i> where <i>j &gt; i</i>.
+ vertices <i>j</i> where <i>j &gt; i</i>. <b>(The version of this
+ constructor without the <tt>edges_are_sorted</tt> tag is deprecated and
+ only provided by the old interface.)</b>
     </p>
 
     <p class="indent">
@@ -472,7 +519,9 @@
       <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
         m)</tt> will be used to initialize the properties on the edges
       of the graph, where <tt>m</tt> is distance from
- <tt>edge_begin</tt> to <tt>edge_end</tt>.
+ <tt>edge_begin</tt> to <tt>edge_end</tt>. <b>(The version of this
+ constructor without the <tt>edges_are_sorted</tt> tag is deprecated and
+ only provided by the old interface.)</b>
     </p>
 
     <hr></hr>
@@ -493,6 +542,7 @@
       share storage with the constructed graph (and so are safe to destroy).
       The parameter <code>prop</code>, if provided, is used to initialize the
       graph property.
+ <b>(This function is only provided by the new interface.)</b>
     </p>
 
     <hr></hr>
@@ -515,6 +565,7 @@
       not share storage with the constructed graph (and so are safe to
       destroy). The parameter <code>prop</code>, if provided, is used to
       initialize the graph property.
+ <b>(This function is only provided by the new interface.)</b>
     </p>
 
     <hr></hr>
@@ -620,6 +671,37 @@
 
     <hr></hr>
 
+ <a name="edge-access"></a><h3>Edge access</h3>
+ <pre><a name="edge_range"></a>
+ std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
+ edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
+ </pre>
+
+ <p class="indent">
+ Returns all edges from <tt>u</tt> to <tt>v</tt>. Requires time
+ linear in the number of edges outgoing from <tt>u</tt>.
+ <b>(This function is only provided by the old interface.)</b>
+ </p>
+
+ <hr></hr>
+
+ <pre><a name="edge"></a>
+ std::pair&lt;edge_descriptor, bool&gt;
+ edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
+ </pre>
+
+ <p class="indent">
+ If there exists an edge <i>(u, v)</i> in the graph, returns the
+ descriptor for that edge and <tt>true</tt>; otherwise, the
+ second value in the pair will be <tt>false</tt>. If multiple
+ edges exist from <tt>u</tt> to <tt>v</tt>, the first edge will
+ be returned; use edge_range
+ to retrieve all edges.
+ <b>(This function is only provided by the old interface.)</b>
+ </p>
+
+ <hr></hr>
+
     <pre><a name="edge_from_index"></a>
   edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&amp;);
     </pre>
@@ -720,6 +802,7 @@
       Add a new vertex to the end of the graph <tt>g</tt>, and return a
       descriptor for that vertex. The new vertex will be greater than any of
       the previous vertices in <tt>g</tt>.
+ <b>(This function is only provided by the old interface.)</b>
     </p>
 
     <hr></hr>
@@ -732,6 +815,7 @@
       Add <tt>count</tt> new vertices to the end of the graph <tt>g</tt>, and
       return a descriptor for the smallest new vertex. The new vertices will
       be greater than any of the previous vertices in <tt>g</tt>.
+ <b>(This function is only provided by the old interface.)</b>
     </p>
 
     <hr></hr>
@@ -746,6 +830,7 @@
       whose source vertex is greater than <tt>src</tt>. If the vertex
       <tt>src</tt> has out edges before this operation is called, there must be
       none whose target is larger than <tt>tgt</tt>.
+ <b>(This function is only provided by the old interface.)</b>
     </p>
 
     <hr></hr>

Modified: trunk/libs/graph/test/csr_graph_test.cpp
==============================================================================
--- trunk/libs/graph/test/csr_graph_test.cpp (original)
+++ trunk/libs/graph/test/csr_graph_test.cpp 2009-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
@@ -13,6 +13,9 @@
 # undef _GLIBCXX_DEBUG
 #endif
 
+// Use new CSR interface
+#define BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
 // Test for the compressed sparse row graph type
 #include <boost/graph/compressed_sparse_row_graph.hpp>
 #include <boost/graph/adjacency_list.hpp>
@@ -157,19 +160,29 @@
 
 void check_consistency(const CSRGraphT& g) {
   // Do a bunch of tests on the graph internal data
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // Check that m_last_source is valid
   BOOST_CHECK(g.m_last_source <= num_vertices(g));
+#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // Check that m_rowstart entries are valid, and that entries after
   // m_last_source + 1 are all zero
   BOOST_CHECK(g.m_rowstart[0] == 0);
- for (CSRGraphT::vertices_size_type i = 0; i < g.m_last_source; ++i) {
+ for (CSRGraphT::vertices_size_type i = 0;
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ i < num_vertices(g);
+#else // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ i < g.m_last_source;
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ ++i) {
     BOOST_CHECK(g.m_rowstart[i + 1] >= g.m_rowstart[i]);
     BOOST_CHECK(g.m_rowstart[i + 1] <= num_edges(g));
   }
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   for (CSRGraphT::vertices_size_type i = g.m_last_source + 1;
        i < g.m_rowstart.size(); ++i) {
     BOOST_CHECK(g.m_rowstart[i] == 0);
   }
+#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // Check that m_column entries are within range
   for (CSRGraphT::edges_size_type i = 0; i < num_edges(g); ++i) {
     BOOST_CHECK(g.m_column[i] < num_vertices(g));
@@ -202,6 +215,7 @@
                       g3, boost::identity_property_map(),
                       boost::identity_property_map());
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // Check constructing a graph using in-place modification of vectors
   {
     std::vector<std::size_t> sources(num_edges(g2));
@@ -271,7 +285,11 @@
                         g3a, boost::identity_property_map(),
                         boost::identity_property_map());
   }
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+ CSRGraphT::edge_iterator ei, ei_end;
 
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // Check constructing a graph using add_edge and add_vertices
   CSRGraphT g4;
   BOOST_CHECK(num_vertices(g4) == 0);
@@ -281,7 +299,6 @@
 
   BOOST_CHECK(first_vert == 0);
   BOOST_CHECK(num_vertices(g4) == num_vertices(g3));
- CSRGraphT::edge_iterator ei, ei_end;
   int i;
   for (boost::tie(ei, ei_end) = edges(g3), i = 0; ei != ei_end; ++ei, ++i) {
     CSRGraphT::edge_descriptor e = add_edge(source(*ei, g3), target(*ei, g3), g4);
@@ -292,6 +309,7 @@
   assert_graphs_equal(g3, boost::identity_property_map(),
                       g4, boost::identity_property_map(),
                       boost::identity_property_map());
+#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
   // Check edge_from_index (and implicitly the edge_index property map) for
   // each edge in g2
@@ -436,6 +454,7 @@
   // graph_test(1000, 0.1, seed);
   graph_test(1000, 0.001, seed);
   graph_test(1000, 0.0005, seed);
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   {
     std::cout << "Testing partially constructed CSR graph" << std::endl;
     CSRGraphT g;
@@ -452,16 +471,19 @@
     }
     graph_test(g);
   }
+#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
   test_graph_properties();
   test_vertex_and_edge_properties();
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   {
     std::cout << "Testing CSR graph built from unsorted edges" << std::endl;
     std::pair<int, int> unsorted_edges[] = {std::make_pair(5, 0), std::make_pair(3, 2), std::make_pair(4, 1), std::make_pair(4, 0), std::make_pair(0, 2), std::make_pair(5, 2)};
- CSRGraphT g(unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+ CSRGraphT g(boost::edges_are_unsorted, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
     graph_test(g);
   }
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
   return 0;
 }


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk