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

Subject: [Boost-commit] svn:boost r54684 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-07-05 16:35:44

Author: jewillco
Date: 2009-07-05 16:35:44 EDT (Sun, 05 Jul 2009)
New Revision: 54684
URL: http://svn.boost.org/trac/boost/changeset/54684

Log:
Added add_edges() function with edge properties; refs #3134
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |    68 ++++++++++++++++++++++++++++++++++++++++
   trunk/libs/graph/doc/compressed_sparse_row.html   |    25 ++++++++++++++                          
   trunk/libs/graph/test/csr_graph_test.cpp          |     3 +                                       
   3 files changed, 95 insertions(+), 1 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-07-05 16:35:44 EDT (Sun, 05 Jul 2009)
@@ -28,6 +28,9 @@
 #include <boost/graph/detail/indexed_properties.hpp>
 #include <boost/iterator/counting_iterator.hpp>
 #include <boost/iterator/reverse_iterator.hpp>
+#include <boost/iterator/zip_iterator.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/tuple/tuple.hpp>
 #include <boost/property_map/property_map.hpp>
 #include <boost/integer.hpp>
 #include <boost/iterator/iterator_facade.hpp>
@@ -175,6 +178,25 @@
     void advance(typename base_type::difference_type) {}
     typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
   };
+
+  template <typename Less>
+  struct compare_first {
+    Less less;
+    compare_first(Less less = Less()): less(less) {}
+    template <typename Tuple>
+    bool operator()(const Tuple& a, const Tuple& b) const {
+      return less(a.template get<0>(), b.template get<0>());
+    }
+  };
+
+  template <int N, typename Result>
+  struct my_tuple_get_class {
+    typedef Result result_type;
+    template <typename Tuple>
+    result_type operator()(const Tuple& t) const {
+      return t.template get<N>();
+    }
+  };
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 }
 
@@ -1102,6 +1124,41 @@
     std::sort(new_edges.begin(), new_edges.end());
     add_edges_sorted_internal(new_edges.begin(), new_edges.end());
   }
+
+  // Add edges from a range of (source, target) pairs and edge properties that
+  // are unsorted
+  template <typename InputIterator, typename EPIterator>
+  inline void
+  add_edges_internal(InputIterator first, InputIterator last,
+                     EPIterator ep_iter, EPIterator ep_iter_end) {
+    typedef compressed_sparse_row_graph Graph;
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+    typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+    typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+    typedef std::pair<vertex_t, vertex_t> vertex_pair;
+    typedef std::vector<
+              boost::tuple<vertex_pair,
+                           typename inherited_edge_properties::edge_bundled> >
+      edge_vector_t;
+    edge_vector_t new_edges
+      (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
+       boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
+    if (new_edges.empty()) return;
+    std::sort(new_edges.begin(), new_edges.end(),
+              boost::detail::compare_first<
+                std::less<vertex_pair> >());
+    add_edges_sorted_internal
+      (boost::make_transform_iterator(
+         new_edges.begin(),
+         boost::detail::my_tuple_get_class<0, vertex_pair>()),
+       boost::make_transform_iterator(
+         new_edges.end(),
+         boost::detail::my_tuple_get_class<0, vertex_pair>()),
+       boost::make_transform_iterator(
+         new_edges.begin(),
+         boost::detail::my_tuple_get_class
+           <1, typename inherited_edge_properties::edge_bundled>()));
+  }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
   using inherited_vertex_properties::operator[];
@@ -1244,6 +1301,17 @@
   add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
     g.add_edges_internal(first, last);
   }
+
+  // Add edges from a range of (source, target) pairs and edge properties that
+  // are unsorted
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS,
+            typename InputIterator, typename EPIterator>
+  inline void
+  add_edges(InputIterator first, InputIterator last,
+            EPIterator ep_iter, EPIterator ep_iter_end,
+            BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_internal(first, last, ep_iter, ep_iter_end);
+  }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
 // From VertexListGraph

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-07-05 16:35:44 EDT (Sun, 05 Jul 2009)
@@ -295,6 +295,10 @@
 void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph&amp; g);
 
 <b>(new interface only)</b>
+template&lt;typename InputIterator, typename EPIter, typename Graph&gt;
+void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph&amp; g);
+
+<b>(new interface only)</b>
 template&lt;typename BidirectionalIterator, typename Graph&gt;
 void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph&amp; g);
 
@@ -941,6 +945,27 @@
 
     <hr></hr>
 
+    <pre><a name="add_edges_prop"></a>
+template&lt;typename InputIterator, typename EPIter&gt;
+void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph&amp; g)
+    </pre>
+    
+    <p class="indent">
+      Add a range of edges (from <tt>first</tt> to <tt>last</tt>) with
+      corresponding edge properties (from <tt>ep_first</tt> to
+      <tt>ep_last</tt>) to the graph.  The <tt>InputIterator</tt> and
+      <tt>EPIter</tt> must be models of <a
+      href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>;
+      the <code>value_type</code> of <tt>InputIterator</tt> must be an
+      <code>std::pair</code> of integer values, and the <code>value_type</code>
+      of <tt>EPIter</tt> must be the edge property type of the graph. The
+      integer values produced by the <tt>InputIterator</tt> are the source and
+      target vertices of the new edges.  The edges do not need to be sorted.
+      <b>(This function is only provided by the new interface.)</b>
+    </p>
+
+    <hr></hr>
+
     <pre><a name="add_edges_sorted"></a>
 template&lt;typename BidirectionalIterator&gt;
 void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph&amp; g)

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-07-05 16:35:44 EDT (Sun, 05 Jul 2009)
@@ -492,7 +492,8 @@
     // Test building a graph using add_edges on unsorted lists
     CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges, 6); // Empty range
     add_edges(unsorted_edges, unsorted_edges + 3, g3);
-    add_edges(unsorted_edges + 3, unsorted_edges + 6, g3);
+    boost::no_property edge_data[3];
+    add_edges(unsorted_edges + 3, unsorted_edges + 6, edge_data, edge_data + 3, g3);
     graph_test(g3);
     assert_graphs_equal(g, boost::identity_property_map(),
                         g3, boost::identity_property_map(),