[Boost-commit] svn:boost r54738 - in branches/release: boost/graph libs/graph/doc libs/graph/test

Subject: [Boost-commit] svn:boost r54738 - in branches/release: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-07-06 20:32:11

Author: jewillco
Date: 2009-07-06 20:32:10 EDT (Mon, 06 Jul 2009)
New Revision: 54738
URL: http://svn.boost.org/trac/boost/changeset/54738

Log:
Merged patches from messages 55-57 of #3134, plus r54737; refs #3134
Text files modified: 
   branches/release/boost/graph/compressed_sparse_row_graph.hpp |   193 ++++++++++++++++++++++++++++++++++++++- 
   branches/release/libs/graph/doc/compressed_sparse_row.html   |    25 +++++                                   
   branches/release/libs/graph/test/csr_graph_test.cpp          |     3                                         
   3 files changed, 212 insertions(+), 9 deletions(-)

Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp	(original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp	2009-07-06 20:32:10 EDT (Mon, 06 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 const 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
 }
 
@@ -983,12 +1005,14 @@
 #ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   // Add edges from a sorted (smallest sources first) range of pairs and edge
   // properties
-  template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+  template <typename BidirectionalIteratorOrig, typename EPIterOrig,
+            typename GlobalToLocal>
   void
   add_edges_sorted_internal(
       BidirectionalIteratorOrig first_sorted,
       BidirectionalIteratorOrig last_sorted,
-      EPIterOrig ep_iter_sorted) {
+      EPIterOrig ep_iter_sorted,
+      const GlobalToLocal& global_to_local) {
     typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
     typedef boost::reverse_iterator<EPIterOrig> EPIter;
     // Flip sequence
@@ -999,6 +1023,7 @@
     typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
     typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
     edge_num new_edge_count = std::distance(first, last);
+
     EPIter ep_iter(ep_iter_sorted);
     std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
     edge_num edges_added_before_i = new_edge_count; // Count increment to add to rowstarts
@@ -1012,7 +1037,7 @@
       // edges_added_to_this_vertex = #mbrs of new_edges with first == i
       edge_num edges_added_to_this_vertex = 0;
       while (current_new_edge != last) {
-        if (current_new_edge->first != i) break;
+        if (get(global_to_local, current_new_edge->first) != i) break;
         ++current_new_edge;
         ++current_new_edge_prop;
         ++edges_added_to_this_vertex;
@@ -1049,6 +1074,16 @@
     }
   }
 
+  template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+  void
+  add_edges_sorted_internal(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      EPIterOrig ep_iter_sorted)  {
+    add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
+                              identity_property_map());
+  }
+
   // Add edges from a sorted (smallest sources first) range of pairs
   template <typename BidirectionalIteratorOrig>
   void
@@ -1058,10 +1093,33 @@
     add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>());
   }
 
+  template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
+  void
+  add_edges_sorted_internal_global(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      const GlobalToLocal& global_to_local) {
+    add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>(),
+                              global_to_local);
+  }
+
+  template <typename BidirectionalIteratorOrig, typename EPIterOrig, 
+	    typename GlobalToLocal>
+  void
+  add_edges_sorted_internal_global(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      EPIterOrig ep_iter_sorted,
+      const GlobalToLocal& global_to_local) {
+    add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
+                              global_to_local);
+  }
+
   // Add edges from a range of (source, target) pairs that are unsorted
-  template <typename InputIterator>
+  template <typename InputIterator, typename GlobalToLocal>
   inline void
-  add_edges_internal(InputIterator first, InputIterator last) {
+  add_edges_internal(InputIterator first, InputIterator last, 
+                     const GlobalToLocal& global_to_local) {
     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;
@@ -1070,7 +1128,59 @@
     edge_vector_t new_edges(first, last);
     if (new_edges.empty()) return;
     std::sort(new_edges.begin(), new_edges.end());
-    add_edges_sorted_internal(new_edges.begin(), new_edges.end());
+    add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
+  }
+
+  template <typename InputIterator>
+  inline void
+  add_edges_internal(InputIterator first, InputIterator last) {
+    add_edges_internal(first, last, identity_property_map());
+  }
+
+  // Add edges from a range of (source, target) pairs and edge properties that
+  // are unsorted
+  template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
+  inline void
+  add_edges_internal(InputIterator first, InputIterator last,
+                     EPIterator ep_iter, EPIterator ep_iter_end,
+                     const GlobalToLocal& global_to_local) {
+    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>()),
+       global_to_local);
+  }
+
+  // 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) {
+    add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
   }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
@@ -1133,16 +1243,28 @@
 inline Vertex
 add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
   Vertex old_num_verts_plus_one = g.m_rowstart.size();
-  g.m_rowstart.push_back(EdgeIndex(0));
+  EdgeIndex numedges = g.m_rowstart.back();
+  g.m_rowstart.push_back(numedges);
   g.vertex_properties().resize(num_vertices(g));
   return old_num_verts_plus_one - 1;
 }
 
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline Vertex
+add_vertex(BOOST_CSR_GRAPH_TYPE& g, 
+           typename BOOST_CSR_GRAPH_TYPE::vertex_bundled const& p) {
+  Vertex old_num_verts_plus_one = g.m_rowstart.size();
+  g.m_rowstart.push_back(EdgeIndex(0));
+  g.vertex_properties().push_back(p);
+  return old_num_verts_plus_one - 1;
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline Vertex
 add_vertices(typename BOOST_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_CSR_GRAPH_TYPE& g) {
   Vertex old_num_verts_plus_one = g.m_rowstart.size();
-  g.m_rowstart.resize(old_num_verts_plus_one + count, EdgeIndex(0));
+  EdgeIndex numedges = g.m_rowstart.back();
+  g.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
   g.vertex_properties().resize(num_vertices(g));
   return old_num_verts_plus_one - 1;
 }
@@ -1208,12 +1330,67 @@
     g.add_edges_sorted_internal(first_sorted, last_sorted);
   }
 
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+            typename EPIterOrig, typename GlobalToLocal>
+  void
+  add_edges_sorted_global(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      EPIterOrig ep_iter_sorted,
+      const GlobalToLocal& global_to_local,
+      BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_sorted_internal_global(first_sorted, last_sorted, ep_iter_sorted, 
+				       global_to_local);
+  }
+
+  // Add edges from a sorted (smallest sources first) range of pairs
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+            typename GlobalToLocal>
+  void
+  add_edges_sorted_global(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      const GlobalToLocal& global_to_local,
+      BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_sorted_internal_global(first_sorted, last_sorted, global_to_local);
+  }
+
+  // Add edges from a range of (source, target) pairs that are unsorted
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
+            typename GlobalToLocal>
+  inline void
+  add_edges_global(InputIterator first, InputIterator last, 
+		   const GlobalToLocal& global_to_local, BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_internal(first, last, global_to_local);
+  }
+
   // Add edges from a range of (source, target) pairs that are unsorted
   template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
   inline void
   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);
+  }
+
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS,
+            typename InputIterator, typename EPIterator, typename GlobalToLocal>
+  inline void
+  add_edges_global(InputIterator first, InputIterator last,
+            EPIterator ep_iter, EPIterator ep_iter_end,
+            const GlobalToLocal& global_to_local,
+            BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
+  }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
 // From VertexListGraph

Modified: branches/release/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- branches/release/libs/graph/doc/compressed_sparse_row.html	(original)
+++ branches/release/libs/graph/doc/compressed_sparse_row.html	2009-07-06 20:32:10 EDT (Mon, 06 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: branches/release/libs/graph/test/csr_graph_test.cpp
==============================================================================
--- branches/release/libs/graph/test/csr_graph_test.cpp	(original)
+++ branches/release/libs/graph/test/csr_graph_test.cpp	2009-07-06 20:32:10 EDT (Mon, 06 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(),