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

Subject: [Boost-commit] svn:boost r53836 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2009-06-12 17:07:39

Author: jewillco
Date: 2009-06-12 17:07:38 EDT (Fri, 12 Jun 2009)
New Revision: 53836
URL: http://svn.boost.org/trac/boost/changeset/53836

Log:
Added more special constructors for distributed CSR; refs #3134
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |    60 ++++++++++++++++++++++++++++++++++++++++
   1 files changed, 60 insertions(+), 0 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 17:07:38 EDT (Fri, 12 Jun 2009)
@@ -93,6 +93,15 @@
 // (sequential and distributed).
 enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
 
+// A type (edges_are_unsorted_for_distributed_graph_t) and a value
+// (edges_are_unsorted_for_distributed_graph) used to indicate that the edge
+// list passed into the CSR graph is not sorted by source vertex.  The data is
+// also stored using global vertex indices, and must be filtered to choose only
+// local vertices.  This constructor caches the edge information in memory, and
+// thus requires only a single pass over the input data.  This constructor is
+// intended for internal use by the distributed CSR constructors.
+enum edges_are_unsorted_for_distributed_graph_t {edges_are_unsorted_for_distributed_graph};
+
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
 /****************************************************************************
@@ -626,6 +635,57 @@
     assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
   }
 
+  //  From number of vertices and single-pass range of unsorted edges.  Data is
+  //  cached in coordinate form before creating the actual graph.  Edges are
+  //  filtered and transformed for use in a distributed graph.
+  template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
+  compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              vertices_size_type numlocalverts,
+                              GlobalToLocal global_to_local,
+                              const EdgePred& edge_pred,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numlocalverts), m_rowstart(),
+      m_column(), m_property(prop)
+  {
+    std::vector<vertex_descriptor> sources, targets;
+    for (; edge_begin != edge_end; ++edge_begin) {
+      if (edge_pred(*edge_begin)) {
+        sources.push_back(edge_begin->first);
+        targets.push_back(edge_begin->second);
+      }
+    }
+    assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
+  }
+
+  //  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.  Edges are filtered and transformed for
+  //  use in a distributed graph.
+  template<typename InputIterator, typename EdgePropertyIterator,
+           typename GlobalToLocal, typename EdgePred>
+  compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              EdgePropertyIterator ep_iter,
+                              vertices_size_type numlocalverts,
+                              GlobalToLocal global_to_local,
+                              const EdgePred& edge_pred,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numlocalverts), m_rowstart(),
+      m_column(), m_property(prop)
+  {
+    std::vector<vertex_descriptor> sources, targets;
+    std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+    for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
+      if (edge_pred(*edge_begin)) {
+        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, numlocalverts, global_to_local);
+  }
+
   // 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.