[Boost-commit] svn:boost r53835 - in trunk: boost/graph libs/graph/doc libs/graph/test

Subject: [Boost-commit] svn:boost r53835 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-06-12 16:56:54

Author: jewillco
Date: 2009-06-12 16:56:54 EDT (Fri, 12 Jun 2009)
New Revision: 53835
URL: http://svn.boost.org/trac/boost/changeset/53835

Log:
Added constructors from unsorted single-pass ranges for CSR graph by caching data in vectors; refs #3134
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |    97 +++++++++++++++++++++++++++++++++++---- 
   trunk/libs/graph/doc/compressed_sparse_row.html   |    86 ++++++++++++++++++++++++++++++++--      
   trunk/libs/graph/test/csr_graph_test.cpp          |     5 ++                                      
   3 files changed, 171 insertions(+), 17 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-12 16:56:54 EDT (Fri, 12 Jun 2009)
@@ -65,9 +65,16 @@
 #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.
+// source vertex.  This version caches the edge information in memory, and thus
+// requires only a single pass over the input data.
 enum edges_are_unsorted_t {edges_are_unsorted};
 
+// A type (edges_are_unsorted_multi_pass_t) and a value
+// (edges_are_unsorted_multi_pass) used to indicate that the edge list passed
+// into the CSR graph is not sorted by source vertex.  This version uses less
+// memory but requires multi-pass capability on the iterators.
+enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
+
 // 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
@@ -105,14 +112,33 @@
 
 #ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 namespace detail {
-  // Less-than operator for comparing only the first elements of two arbitrary
-  // Boost tuples
-  struct compare_first_elements_in_tuples {
-    template <typename Tuple>
-    bool operator()(const Tuple& a, const Tuple& b) const {
-      return (a.template get<0>()) < (b.template get<0>());
-    }
-  };
+  template<typename InputIterator>
+  size_t
+  reserve_count_for_single_pass_helper(InputIterator, InputIterator,
+                                       std::input_iterator_tag)
+  {
+    // Do nothing: we have no idea how much storage to reserve.
+    return 0;
+  }
+
+  template<typename InputIterator>
+  size_t
+  reserve_count_for_single_pass_helper(InputIterator first, InputIterator last,
+                                       std::random_access_iterator_tag)
+  {
+    using std::distance;
+    typename std::iterator_traits<InputIterator>::difference_type n =
+      distance(first, last);
+    return (size_t)n;
+  }
+
+  template<typename InputIterator>
+  size_t
+  reserve_count_for_single_pass(InputIterator first, InputIterator last) {
+    typedef typename std::iterator_traits<InputIterator>::iterator_category
+      category;
+    return reserve_count_for_single_pass_helper(first, last, category());
+  }
 }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
@@ -237,7 +263,7 @@
 #ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   //  From number of vertices and unsorted list of edges
   template <typename MultiPassInputIterator>
-  compressed_sparse_row_graph(edges_are_unsorted_t,
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
                               MultiPassInputIterator edge_begin,
                               MultiPassInputIterator edge_end,
                               vertices_size_type numverts,
@@ -273,7 +299,7 @@
 
   //  From number of vertices and unsorted list of edges, plus edge properties
   template <typename MultiPassInputIterator, typename EdgePropertyIterator>
-  compressed_sparse_row_graph(edges_are_unsorted_t,
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
                               MultiPassInputIterator edge_begin,
                               MultiPassInputIterator edge_end,
                               EdgePropertyIterator ep_iter,
@@ -551,6 +577,55 @@
     assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
   }
 
+  //  From number of vertices and single-pass range of unsorted edges.  Data is
+  //  cached in coordinate form before creating the actual graph.
+  template<typename InputIterator>
+  compressed_sparse_row_graph(edges_are_unsorted_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              vertices_size_type numverts,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numverts), m_rowstart(),
+      m_column(), m_property(prop)
+  {
+    std::vector<vertex_descriptor> sources, targets;
+    size_t reserve_size
+      = detail::reserve_count_for_single_pass(edge_begin, edge_end);
+    sources.reserve(reserve_size);
+    targets.reserve(reserve_size);
+    for (; edge_begin != edge_end; ++edge_begin) {
+      sources.push_back(edge_begin->first);
+      targets.push_back(edge_begin->second);
+    }
+    assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
+  }
+
+  //  From number of vertices and single-pass range of unsorted edges and
+  //  single-pass range of edge properties.  Data is cached in coordinate form
+  //  before creating the actual graph.
+  template<typename InputIterator, typename EdgePropertyIterator>
+  compressed_sparse_row_graph(edges_are_unsorted_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              EdgePropertyIterator ep_iter,
+                              vertices_size_type numverts,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numverts), m_rowstart(),
+      m_column(), m_property(prop)
+  {
+    std::vector<vertex_descriptor> sources, targets;
+    std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+    size_t reserve_size
+      = detail::reserve_count_for_single_pass(edge_begin, edge_end);
+    sources.reserve(reserve_size);
+    targets.reserve(reserve_size);
+    edge_props.reserve(reserve_size);
+    for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
+      sources.push_back(edge_begin->first);
+      targets.push_back(edge_begin->second);
+      edge_props.push_back(*ep_iter);
+    }
+    assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
+  }
+
   // Replace graph with sources and targets given, sorting them in-place, and
   // using the given global-to-local property map to get local indices from
   // global ones in the two arrays.

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-12 16:56:54 EDT (Fri, 12 Jun 2009)
@@ -115,14 +115,27 @@
   <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;
+  template&lt;typename InputIterator&gt;
   <a href="#edge-const">compressed_sparse_row_graph</a>(edges_are_unsorted_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              vertices_size_type numverts,
+                              const GraphProperty&amp; prop = GraphProperty());
+
+  template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+  compressed_sparse_row_graph(edges_are_unsorted_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              EdgePropertyIterator ep_iter,
+                              vertices_size_type numverts,
+                              const GraphProperty&amp; prop = GraphProperty());
+
+  template&lt;typename MultiPassInputIterator&gt;
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_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(edges_are_unsorted_t,
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
                               MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
                               EdgePropertyIterator ep_iter,
                               vertices_size_type numverts,
@@ -401,8 +414,67 @@
     <hr></hr>
 
     <pre><a name="edge-const"></a>
-  template&lt;typename MultiPassInputIterator&gt;
+  template&lt;typename InputIterator&gt;
   compressed_sparse_row_graph(edges_are_unsorted_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              vertices_size_type numverts,
+                              const GraphProperty&amp; prop = GraphProperty());
+    </pre>
+
+    <p class="indent">
+      Constructs a graph with <code>numverts</code> vertices whose
+      edges are specified by the iterator range <code>[edge_begin,
+      edge_end)</code>. The <tt>InputIterator</tt> must be a model of
+      <a
+      href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
+      whose <code>value_type</code> is an <code>std::pair</code> of
+      integer values. These integer values are the source and target
+      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.  This constructor uses extra
+      memory to save the edge information before adding it to the graph,
+      avoiding the requirement for the iterator to have multi-pass capability.
+      <b>(This function is only provided by the new interface.)</b>
+    </p>
+
+    <p class="indent">
+      The value <code>prop</code> will be used to initialize the graph
+      property.
+    </p>
+
+    <hr></hr>
+
+    <pre><a name="edge-prop-const"></a>
+  template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+  compressed_sparse_row_graph(edges_are_unsorted_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              EdgePropertyIterator ep_iter,
+                              vertices_size_type numverts,
+                              const GraphProperty&amp; prop = GraphProperty());
+    </pre>
+    <p class="indent">
+      This constructor constructs a graph with <code>numverts</code>
+      vertices and the edges provided in the iterator range
+      <code>[edge_begin, edge_end)</code>. Its semantics are identical
+      to the edge range constructor, except
+      that edge properties are also initialized. The type
+      <tt>EdgePropertyIterator</tt> must be a model of the <a
+      href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
+      concept whose <tt>value_type</tt> is convertible to
+      <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>.  This constructor uses extra
+      memory to save the edge information before adding it to the graph,
+      avoiding the requirement for the iterator to have multi-pass capability.
+      <b>(This function is only provided by the new interface.)</b>
+    </p>
+
+    <hr></hr>
+
+    <pre><a name="edge-const"></a>
+  template&lt;typename MultiPassInputIterator&gt;
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
                               MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
                               vertices_size_type numverts,
                               const GraphProperty&amp; prop = GraphProperty());
@@ -418,7 +490,8 @@
       integer values. These integer values are the source and target
       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.
+      edge_end)</code> do not need to be sorted.  Multiple passes will be made
+      over the edge range.
       <b>(This function is only provided by the new interface.)</b>
     </p>
 
@@ -431,7 +504,7 @@
 
     <pre><a name="edge-prop-const"></a>
   template&lt;typename MultiPassInputIterator, typename EdgePropertyIterator&gt;
-  compressed_sparse_row_graph(edges_are_unsorted_t,
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
                               MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
                               EdgePropertyIterator ep_iter,
                               vertices_size_type numverts,
@@ -449,7 +522,8 @@
       <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>.  Multiple passes will be made
+      over the edge and property ranges.
       <b>(This function is only provided by the new interface.)</b>
     </p>
 

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-12 16:56:54 EDT (Fri, 12 Jun 2009)
@@ -481,7 +481,12 @@
     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(boost::edges_are_unsorted, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+    CSRGraphT g2(boost::edges_are_unsorted_multi_pass, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
     graph_test(g);
+    graph_test(g2);
+    assert_graphs_equal(g, boost::identity_property_map(),
+                        g2, boost::identity_property_map(),
+                        boost::identity_property_map());
   }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE