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

Subject: [Boost-commit] svn:boost r52938 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-05-12 13:01:10

Author: jewillco
Date: 2009-05-12 13:01:09 EDT (Tue, 12 May 2009)
New Revision: 52938
URL: http://svn.boost.org/trac/boost/changeset/52938

Log:
Added in-place construction of CSR graphs from separate, mutable vectors of sources and targets
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |   223 ++++++++++++++++++++++++++++++++++++++++
   trunk/libs/graph/test/csr_graph_test.cpp          |    78 +++++++++++++                           
   2 files changed, 301 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-05-12 13:01:09 EDT (Tue, 12 May 2009)
@@ -17,17 +17,21 @@
 #include <utility>
 #include <algorithm>
 #include <climits>
+#include <cassert>
 #include <iterator>
+#include <iostream> // FIXME
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/properties.hpp>
 #include <boost/graph/detail/indexed_properties.hpp>
 #include <boost/iterator/counting_iterator.hpp>
+#include <boost/property_map/property_map.hpp>
 #include <boost/integer.hpp>
 #include <boost/iterator/iterator_facade.hpp>
 #include <boost/mpl/if.hpp>
 #include <boost/graph/graph_selectors.hpp>
 #include <boost/static_assert.hpp>
 #include <boost/functional/hash.hpp>
+#include <boost/utility.hpp>
 
 #ifdef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 #  error The Compressed Sparse Row graph only supports bundled properties.
@@ -47,6 +51,28 @@
 inline void edges_are_sorted(edges_are_sorted_internal) {}
 typedef void (*edges_are_sorted_t)(edges_are_sorted_internal);
 
+// 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
+// to construct the CSR graph.  These vectors are sorted in-place and then the
+// targets and properties are swapped into the graph data structure.
+struct construct_inplace_from_sources_and_targets_internal {};
+inline void construct_inplace_from_sources_and_targets(construct_inplace_from_sources_and_targets_internal) {}
+typedef void (*construct_inplace_from_sources_and_targets_t)(construct_inplace_from_sources_and_targets_internal);
+
+// A type (construct_inplace_from_sources_and_targets_global_t) and a value
+// (construct_inplace_from_sources_and_targets_global) used to indicate that
+// mutable vectors of sources and targets (and possibly edge properties) are
+// being used to construct the CSR graph.  These vectors are sorted in-place
+// and then the targets and properties are swapped into the graph data
+// structure.  It is assumed that global indices (for distributed CSR) are
+// used, and a map is required to convert those to local indices.  This
+// constructor is intended for internal use by the various CSR graphs
+// (sequential and distributed).
+struct construct_inplace_from_sources_and_targets_global_internal {};
+inline void construct_inplace_from_sources_and_targets_global(construct_inplace_from_sources_and_targets_global_internal) {}
+typedef void (*construct_inplace_from_sources_and_targets_global_t)(construct_inplace_from_sources_and_targets_global_internal);
+
 /****************************************************************************
  * Local helper macros to reduce typing and clutter later on.               *
  ****************************************************************************/
@@ -62,6 +88,17 @@
 template<typename Vertex, typename EdgeIndex>
 class csr_edge_descriptor;
 
+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>());
+    }
+  };
+}
+
 /** Compressed sparse row graph.
  *
  * Vertex and EdgeIndex should be unsigned integral types and should
@@ -329,6 +366,192 @@
       m_rowstart[current_vertex_plus_one] = current_edge;
   }
 
+  //  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.
+  compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
+                              std::vector<vertex_descriptor>& sources,
+                              std::vector<vertex_descriptor>& targets,
+                              vertices_size_type numverts,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numverts), m_rowstart(),
+      m_column(), m_property(prop), m_last_source(numverts)
+  {
+    assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
+  }
+
+  //  From number of vertices and mutable vectors of sources and targets,
+  //  expressed with global vertex indices; vectors are 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>
+  compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
+                              std::vector<vertex_descriptor>& sources,
+                              std::vector<vertex_descriptor>& targets,
+                              vertices_size_type numlocalverts,
+                              GlobalToLocal global_to_local,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numlocalverts), m_rowstart(),
+      m_column(), m_property(prop), m_last_source(numlocalverts)
+  {
+    assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
+  }
+
+  //  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.
+  compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
+                              std::vector<vertex_descriptor>& sources,
+                              std::vector<vertex_descriptor>& targets,
+                              std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+                              vertices_size_type numverts,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numverts), m_rowstart(),
+      m_column(), m_property(prop), m_last_source(numverts)
+  {
+    assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
+  }
+
+  //  From number of vertices and mutable vectors of sources and targets and
+  //  edge properties, expressed with global vertex indices; vectors are
+  //  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>
+  compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
+                              std::vector<vertex_descriptor>& sources,
+                              std::vector<vertex_descriptor>& targets,
+                              std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+                              vertices_size_type numlocalverts,
+                              GlobalToLocal global_to_local,
+                              const GraphProperty& prop = GraphProperty())
+    : inherited_vertex_properties(numlocalverts), m_rowstart(),
+      m_column(), m_property(prop), m_last_source(numlocalverts)
+  {
+    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.
+  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) {
+    assert (sources.size() == targets.size());
+    typedef typename std::vector<vertex_descriptor>::iterator vertex_vec_iter;
+    EdgeIndex numedges = sources.size();
+#if 0
+    std::cerr << "Edges before:";
+    for (size_t i = 0; i < numedges; ++i) {
+      std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
+    }
+    std::cerr << std::endl;
+#endif
+    // Do an in-place histogram sort (at least that's what I think it is) to
+    // sort sources and targets
+    // 1. Count degrees; degree of vertex v is in m_rowstart[v + 1]
+    m_rowstart.clear();
+    m_rowstart.resize(numverts + 1);
+    for (size_t i = 0; i < numedges; ++i) {
+      ++m_rowstart[get(global_to_local, sources[i]) + 1];
+    }
+    // 2. Do a prefix sum on those to get starting positions of each row
+    for (size_t i = 0; i < numverts; ++i) {
+      m_rowstart[i + 1] += m_rowstart[i];
+    }
+    // 3. Copy m_rowstart (except last element) to get insert positions
+    std::vector<EdgeIndex> insert_positions(m_rowstart.begin(), boost::prior(m_rowstart.end()));
+    // 4. Swap the sources and targets into place
+    for (size_t i = 0; i < numedges; ++i) {
+      // While edge i is not in the right bucket:
+      while (!(i >= m_rowstart[get(global_to_local, sources[i])] && i < insert_positions[get(global_to_local, sources[i])])) {
+        // Add a slot in the right bucket
+        size_t target_pos = insert_positions[get(global_to_local, sources[i])]++;
+        assert (target_pos < m_rowstart[get(global_to_local, sources[i]) + 1]);
+        if (target_pos == i) continue;
+        // Swap this edge into place
+        using std::swap;
+        swap(sources[i], sources[target_pos]);
+        swap(targets[i], targets[target_pos]);
+      }
+    }
+#if 0
+    std::cerr << "Edges after:";
+    for (size_t i = 0; i < sources.size(); ++i) {
+      std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
+    }
+    std::cerr << std::endl;
+#endif
+    // Now targets is the correct vector (properly sorted by source) for
+    // m_column
+    m_column.swap(targets);
+  }
+
+  // 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>
+  void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
+                                         std::vector<vertex_descriptor>& targets,
+                                         std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+                                         vertices_size_type numverts,
+                                         GlobalToLocal global_to_local) {
+    assert (sources.size() == targets.size());
+    assert (sources.size() == edge_props.size());
+    EdgeIndex numedges = sources.size();
+#if 0
+    std::cerr << "Edges before:";
+    for (size_t i = 0; i < numedges; ++i) {
+      std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
+    }
+    std::cerr << std::endl;
+#endif
+    // Do an in-place histogram sort (at least that's what I think it is) to
+    // sort sources and targets
+    // 1. Count degrees; degree of vertex v is in m_rowstart[v + 1]
+    m_rowstart.clear();
+    m_rowstart.resize(numverts + 1);
+    for (size_t i = 0; i < numedges; ++i) {
+      ++m_rowstart[get(global_to_local, sources[i]) + 1];
+    }
+    // 2. Do a prefix sum on those to get starting positions of each row
+    for (size_t i = 0; i < numverts; ++i) {
+      m_rowstart[i + 1] += m_rowstart[i];
+    }
+    // 3. Copy m_rowstart (except last element) to get insert positions
+    std::vector<EdgeIndex> insert_positions(m_rowstart.begin(), boost::prior(m_rowstart.end()));
+    // 4. Swap the sources and targets into place
+    for (size_t i = 0; i < numedges; ++i) {
+      // While edge i is not in the right bucket:
+      while (!(i >= m_rowstart[get(global_to_local, sources[i])] && i < insert_positions[get(global_to_local, sources[i])])) {
+        // Add a slot in the right bucket
+        size_t target_pos = insert_positions[get(global_to_local, sources[i])]++;
+        assert (target_pos < m_rowstart[get(global_to_local, sources[i]) + 1]);
+        if (target_pos == i) continue;
+        // Swap this edge into place
+        using std::swap;
+        swap(sources[i], sources[target_pos]);
+        swap(targets[i], targets[target_pos]);
+        swap(edge_props[i], edge_props[target_pos]);
+      }
+    }
+#if 0
+    std::cerr << "Edges after:";
+    for (size_t i = 0; i < sources.size(); ++i) {
+      std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
+    }
+    std::cerr << std::endl;
+#endif
+    // Now targets is the correct vector (properly sorted by source) for
+    // m_column, and edge_props for m_edge_properties
+    m_column.swap(targets);
+    this->m_edge_properties.swap(edge_props);
+  }
+
+
   //   Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function
   template<typename Graph, typename VertexIndexMap>
   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,

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-05-12 13:01:09 EDT (Tue, 12 May 2009)
@@ -80,6 +80,14 @@
 
       std::sort(edges1.begin(), edges1.end());
       std::sort(edges2.begin(), edges2.end());
+      if (edges1 != edges2) {
+        std::cerr << "edges1:";
+        for (size_t i = 0; i < edges1.size(); ++i) std::cerr << " " << edges1[i];
+        std::cerr << std::endl;
+        std::cerr << "edges2:";
+        for (size_t i = 0; i < edges2.size(); ++i) std::cerr << " " << edges2[i];
+        std::cerr << std::endl;
+      }
       BOOST_CHECK (edges1 == edges2);
     }
   }
@@ -194,6 +202,76 @@
                       g3, boost::identity_property_map(),
                       boost::identity_property_map());
 
+  // Check constructing a graph using in-place modification of vectors
+  {
+    std::vector<std::size_t> sources(num_edges(g2));
+    std::vector<std::size_t> targets(num_edges(g2));
+    std::size_t idx = 0;
+    // Edges actually sorted
+    BGL_FORALL_EDGES(e, g2, CSRGraphT) {
+      sources[idx] = source(e, g2);
+      targets[idx] = target(e, g2);
+      ++idx;
+    }
+    CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
+                  sources,
+                  targets,
+                  num_vertices(g2));
+    check_consistency(g3a);
+    assert_graphs_equal(g2, boost::identity_property_map(),
+                        g3a, boost::identity_property_map(),
+                        boost::identity_property_map());
+  }
+  {
+    std::vector<std::size_t> sources(num_edges(g2));
+    std::vector<std::size_t> targets(num_edges(g2));
+    std::size_t idx = 0;
+    // Edges reverse-sorted
+    BGL_FORALL_EDGES(e, g2, CSRGraphT) {
+      sources[num_edges(g2) - 1 - idx] = source(e, g2);
+      targets[num_edges(g2) - 1 - idx] = target(e, g2);
+      ++idx;
+    }
+    CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
+                  sources,
+                  targets,
+                  num_vertices(g2));
+    check_consistency(g3a);
+    assert_graphs_equal(g2, boost::identity_property_map(),
+                        g3a, boost::identity_property_map(),
+                        boost::identity_property_map());
+  }
+  {
+    std::vector<std::size_t> sources(num_edges(g2));
+    std::vector<std::size_t> targets(num_edges(g2));
+    std::size_t idx = 0;
+    // Edges scrambled using Fisher-Yates shuffle (Durstenfeld variant) from
+    // Wikipedia
+    BGL_FORALL_EDGES(e, g2, CSRGraphT) {
+      sources[idx] = source(e, g2);
+      targets[idx] = target(e, g2);
+      ++idx;
+    }
+    boost::minstd_rand gen(1);
+    if (num_edges(g) != 0) {
+      for (std::size_t i = num_edges(g) - 1; i > 0; --i) {
+        std::size_t scrambled = boost::uniform_int<>(0, i)(gen);
+        if (scrambled == i) continue;
+        using std::swap;
+        swap(sources[i], sources[scrambled]);
+        swap(targets[i], targets[scrambled]);
+      }
+    }
+    CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
+                  sources,
+                  targets,
+                  num_vertices(g2));
+    check_consistency(g3a);
+    assert_graphs_equal(g2, boost::identity_property_map(),
+                        g3a, boost::identity_property_map(),
+                        boost::identity_property_map());
+  }
+
   // Check constructing a graph using add_edge and add_vertices
   CSRGraphT g4;
   BOOST_CHECK(num_vertices(g4) == 0);