[Boost-commit] svn:boost r54737 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r54737 - trunk/boost/graph
From: ngedmond_at_[hidden]
Date: 2009-07-06 20:21:17

Author: ngedmond
Date: 2009-07-06 20:21:15 EDT (Mon, 06 Jul 2009)
New Revision: 54737
URL: http://svn.boost.org/trac/boost/changeset/54737

Log:
Added add_vertices and add_edges calls with global-to-local maps and resolved ambiguous overloads resulting from the new forms.

Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |   147 ++++++++++++++++++++++++++++++++++----- 
   1 files changed, 126 insertions(+), 21 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-06 20:21:15 EDT (Mon, 06 Jul 2009)
@@ -664,9 +664,8 @@
   //  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.
-  template <typename Source>
   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
-                              std::vector<Source>& sources,
+                              std::vector<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& targets,
                               vertices_size_type numverts,
                               const GraphProperty& prop = GraphProperty())
@@ -681,9 +680,9 @@
   //  unspecified contents but are guaranteed not to share storage with the
   //  constructed graph.  This constructor should only be used by the
   //  distributed CSR graph.
-  template <typename GlobalToLocal, typename Source>
+  template <typename GlobalToLocal>
   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
-                              std::vector<Source>& sources,
+                              std::vector<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& targets,
                               vertices_size_type numlocalverts,
                               GlobalToLocal global_to_local,
@@ -697,9 +696,8 @@
   //  From number of vertices and mutable vectors of sources, targets, and edge
   //  properties; vectors are returned with unspecified contents but are
   //  guaranteed not to share storage with the constructed graph.
-  template <typename Source>
   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
-                              std::vector<Source>& sources,
+                              std::vector<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& targets,
                               std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
                               vertices_size_type numverts,
@@ -715,9 +713,9 @@
   //  returned with unspecified contents but are guaranteed not to share
   //  storage with the constructed graph.  This constructor should only be used
   //  by the distributed CSR graph.
-  template <typename GlobalToLocal, typename Source>
+  template <typename GlobalToLocal>
   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
-                              std::vector<Source>& sources,
+                              std::vector<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& targets,
                               std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
                               vertices_size_type numlocalverts,
@@ -832,8 +830,8 @@
   // 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.
-  template <typename GlobalToLocal, typename Source>
-  void assign_sources_and_targets_global(std::vector<Source>& sources,
+  template <typename GlobalToLocal>
+  void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
                                          std::vector<vertex_descriptor>& targets,
                                          vertices_size_type numverts,
                                          GlobalToLocal global_to_local) {
@@ -891,8 +889,8 @@
   // Replace graph with sources and targets and edge properties 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.
-  template <typename GlobalToLocal, typename Source>
-  void assign_sources_and_targets_global(std::vector<Source>& sources,
+  template <typename GlobalToLocal>
+  void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
                                          std::vector<vertex_descriptor>& targets,
                                          std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
                                          vertices_size_type numverts,
@@ -1035,12 +1033,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
@@ -1051,6 +1051,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
@@ -1064,7 +1065,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;
@@ -1101,6 +1102,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
@@ -1110,10 +1121,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;
@@ -1122,15 +1156,22 @@
     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>
+  template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
   inline void
   add_edges_internal(InputIterator first, InputIterator last,
-                     EPIterator ep_iter, EPIterator ep_iter_end) {
+                     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;
@@ -1157,7 +1198,17 @@
        boost::make_transform_iterator(
          new_edges.begin(),
          boost::detail::my_tuple_get_class
-           <1, typename inherited_edge_properties::edge_bundled>()));
+           <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
 
@@ -1228,6 +1279,16 @@
 
 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();
   EdgeIndex numedges = g.m_rowstart.back();
@@ -1297,6 +1358,40 @@
     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
@@ -1314,6 +1409,16 @@
             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