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

Subject: [Boost-commit] svn:boost r60958 - in trunk: boost/graph boost/graph/detail libs/graph/test
From: jewillco_at_[hidden]
Date: 2010-03-30 13:50:30

Author: jewillco
Date: 2010-03-30 13:50:27 EDT (Tue, 30 Mar 2010)
New Revision: 60958
URL: http://svn.boost.org/trac/boost/changeset/60958

Log:
Added vertex_bundle and edge_bundle property maps, plus fixed some property map allocation bugs
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp         |   130 +++++++++++++++++++++++++++++++-------- 
   trunk/boost/graph/detail/compressed_sparse_row_struct.hpp |    27 +++++++                                 
   trunk/boost/graph/detail/indexed_properties.hpp           |    53 ++++++++++++++-                         
   trunk/libs/graph/test/csr_graph_test.cpp                  |    33 +++++++++                               
   4 files changed, 203 insertions(+), 40 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	2010-03-30 13:50:27 EDT (Tue, 30 Mar 2010)
@@ -185,11 +185,11 @@
          typename EdgeIndex>
 class compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
    : public detail::indexed_vertex_properties<BOOST_DIR_CSR_GRAPH_TYPE,
-                                              VertexProperty, Vertex>
+                                              VertexProperty, Vertex, identity_property_map>
 {
  public:
   typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
-                                            VertexProperty, Vertex>
+                                            VertexProperty, Vertex, identity_property_map>
     inherited_vertex_properties;
 
  public:
@@ -728,11 +728,11 @@
          typename EdgeIndex>
 class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
    : public detail::indexed_vertex_properties<BOOST_BIDIR_CSR_GRAPH_TYPE,
-                                              VertexProperty, Vertex>
+                                              VertexProperty, Vertex, identity_property_map>
 {
  public:
   typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
-                                            VertexProperty, Vertex>
+                                            VertexProperty, Vertex, identity_property_map>
     inherited_vertex_properties;
 
  public:
@@ -1394,24 +1394,6 @@
   return get_property_value(g.m_property, Tag());
 }
 
-// Add edge_index property map
-template<typename Index, typename Descriptor>
-struct csr_edge_index_map
-{
-  typedef Index                     value_type;
-  typedef Index                     reference;
-  typedef Descriptor                key_type;
-  typedef readable_property_map_tag category;
-};
-
-template<typename Index, typename Descriptor>
-inline Index
-get(const csr_edge_index_map<Index, Descriptor>&,
-    const typename csr_edge_index_map<Index, Descriptor>::key_type& key)
-{
-  return key.idx;
-}
-
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t>
 {
@@ -1422,17 +1404,25 @@
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>
 {
-private:
-  typedef typename graph_traits<BOOST_CSR_GRAPH_TYPE>::edge_descriptor
-    edge_descriptor;
-  typedef csr_edge_index_map<EdgeIndex, edge_descriptor> edge_index_type;
-
-public:
-  typedef edge_index_type type;
+  typedef detail::csr_edge_index_map<Vertex, EdgeIndex> type;
   typedef type const_type;
 };
 
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t>
+{
+  typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::vertex_map_type type;
+  typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::const_vertex_map_type const_type;
+};
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+struct property_map<BOOST_CSR_GRAPH_TYPE, edge_bundle_t>
+{
+  typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::edge_map_type type;
+  typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::const_edge_map_type const_type;
+};
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline identity_property_map
 get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
 {
@@ -1464,6 +1454,88 @@
   return e.idx;
 }
 
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t>::type
+get(vertex_bundle_t, BOOST_CSR_GRAPH_TYPE& g)
+{
+  return g.get_vertex_bundle(get(vertex_index, g));
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t>::const_type
+get(vertex_bundle_t, const BOOST_CSR_GRAPH_TYPE& g)
+{
+  return g.get_vertex_bundle(get(vertex_index, g));
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline VertexProperty&
+get(vertex_bundle_t,
+    BOOST_CSR_GRAPH_TYPE& g, Vertex v)
+{
+  return get(vertex_bundle, g)[v];
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline const VertexProperty&
+get(vertex_bundle_t,
+    const BOOST_CSR_GRAPH_TYPE& g, Vertex v)
+{
+  return get(vertex_bundle, g)[v];
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline void
+put(vertex_bundle_t,
+    BOOST_CSR_GRAPH_TYPE& g,
+    Vertex v,
+    const VertexProperty& val)
+{
+  put(get(vertex_bundle, g), v, val);
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_bundle_t>::type
+get(edge_bundle_t, BOOST_CSR_GRAPH_TYPE& g)
+{
+  return g.m_forward.get_edge_bundle(get(edge_index, g));
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_bundle_t>::const_type
+get(edge_bundle_t, const BOOST_CSR_GRAPH_TYPE& g)
+{
+  return g.m_forward.get_edge_bundle(get(edge_index, g));
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline EdgeProperty&
+get(edge_bundle_t,
+    BOOST_CSR_GRAPH_TYPE& g,
+    const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
+{
+  return get(edge_bundle, g)[e];
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline const EdgeProperty&
+get(edge_bundle_t,
+    const BOOST_CSR_GRAPH_TYPE& g,
+    const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
+{
+  return get(edge_bundle, g)[e];
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline void
+put(edge_bundle_t,
+    BOOST_CSR_GRAPH_TYPE& g,
+    const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e,
+    const EdgeProperty& val)
+{
+  put(get(edge_bundle, g), e, val);
+}
+
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle>
 inline
 typename property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>::type

Modified: trunk/boost/graph/detail/compressed_sparse_row_struct.hpp
==============================================================================
--- trunk/boost/graph/detail/compressed_sparse_row_struct.hpp	(original)
+++ trunk/boost/graph/detail/compressed_sparse_row_struct.hpp	2010-03-30 13:50:27 EDT (Tue, 30 Mar 2010)
@@ -54,6 +54,24 @@
   template<typename Vertex, typename EdgeIndex>
   class csr_edge_descriptor;
 
+  // Add edge_index property map
+  template<typename Vertex, typename EdgeIndex>
+  struct csr_edge_index_map
+  {
+    typedef EdgeIndex                 value_type;
+    typedef EdgeIndex                 reference;
+    typedef csr_edge_descriptor<Vertex, EdgeIndex> key_type;
+    typedef readable_property_map_tag category;
+  };
+
+  template<typename Vertex, typename EdgeIndex>
+  inline EdgeIndex
+  get(const csr_edge_index_map<Vertex, EdgeIndex>&,
+      const csr_edge_descriptor<Vertex, EdgeIndex>& key)
+  {
+    return key.idx;
+  }
+
   /** Compressed sparse row graph internal structure.
    *
    * Vertex and EdgeIndex should be unsigned integral types and should
@@ -65,12 +83,14 @@
     public detail::indexed_edge_properties<
              compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
              EdgeProperty,
-             csr_edge_descriptor<Vertex, EdgeIndex> > {
+             csr_edge_descriptor<Vertex, EdgeIndex>,
+             csr_edge_index_map<Vertex, EdgeIndex> > {
     public:
     typedef detail::indexed_edge_properties<
               compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
               EdgeProperty,
-              csr_edge_descriptor<Vertex, EdgeIndex> >
+              csr_edge_descriptor<Vertex, EdgeIndex>,
+              csr_edge_index_map<Vertex, EdgeIndex> >
       inherited_edge_properties;
 
     typedef Vertex vertices_size_type;
@@ -110,6 +130,7 @@
          source_pred, boost::make_property_map_function(global_to_local));
 
       m_column.resize(m_rowstart.back());
+      inherited_edge_properties::resize(m_rowstart.back());
 
       boost::graph::detail::histogram_sort
         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
@@ -248,6 +269,7 @@
       // Now targets is the correct vector (properly sorted by source) for
       // m_column
       m_column.swap(targets);
+      inherited_edge_properties::resize(m_rowstart.back());
     }
 
     // Replace graph with sources and targets and edge properties given, sorting
@@ -289,6 +311,7 @@
     {
       m_rowstart.resize(numverts + 1);
       m_column.resize(numedges);
+      inherited_edge_properties::resize(numedges);
       EdgeIndex current_edge = 0;
       typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
       typedef typename boost::graph_traits<Graph>::edge_descriptor g_edge;

Modified: trunk/boost/graph/detail/indexed_properties.hpp
==============================================================================
--- trunk/boost/graph/detail/indexed_properties.hpp	(original)
+++ trunk/boost/graph/detail/indexed_properties.hpp	2010-03-30 13:50:27 EDT (Tue, 30 Mar 2010)
@@ -23,17 +23,24 @@
 #include <boost/iterator/counting_iterator.hpp>
 #include <boost/integer.hpp>
 #include <boost/iterator/iterator_facade.hpp>
+#include <boost/property_map/property_map.hpp>
 #include <boost/mpl/if.hpp>
 
 namespace boost {
 namespace detail {
 
-template<typename Derived, typename Property, typename Descriptor>
+template<typename Derived, typename Property, typename Descriptor, typename IndexMap>
 class indexed_vertex_properties
 {
 public:
   typedef no_property vertex_property_type;
   typedef Property vertex_bundled;
+  typedef iterator_property_map<
+            typename std::vector<Property>::iterator,
+            IndexMap> vertex_map_type;
+  typedef iterator_property_map<
+            typename std::vector<Property>::const_iterator,
+            IndexMap> const_vertex_map_type;
 
   // Directly access a vertex or edge bundle
   Property& operator[](Descriptor v)
@@ -42,6 +49,14 @@
   const Property& operator[](Descriptor v) const
   { return m_vertex_properties[get(vertex_index, derived(), v)]; }
 
+  vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) {
+    return vertex_map_type(m_vertex_properties.begin(), index_map);
+  }
+
+  const_vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) const {
+    return const_vertex_map_type(m_vertex_properties.begin(), index_map);
+  }
+
 protected:
   // Default-construct with no property values
   indexed_vertex_properties() {}
@@ -90,17 +105,23 @@
   std::vector<Property> m_vertex_properties;
 };
 
-template<typename Derived, typename Descriptor>
-class indexed_vertex_properties<Derived, void, Descriptor>
+template<typename Derived, typename Descriptor, typename IndexMap>
+class indexed_vertex_properties<Derived, void, Descriptor, IndexMap>
 {
   struct secret {};
 
  public:
   typedef no_property vertex_property_type;
   typedef void vertex_bundled;
+  typedef secret vertex_map_type;
+  typedef secret const_vertex_map_type;
 
   secret operator[](secret) { return secret(); }
 
+  vertex_map_type get_vertex_bundle() const {
+    return vertex_map_type();
+  }
+
  protected:
   // All operations do nothing.
   indexed_vertex_properties() { }
@@ -112,13 +133,19 @@
   void reserve(std::size_t) { }
 };
 
-template<typename Derived, typename Property, typename Descriptor>
+template<typename Derived, typename Property, typename Descriptor, typename IndexMap>
 class indexed_edge_properties
 {
 public:
   typedef no_property edge_property_type;
   typedef Property edge_bundled;
   typedef Property edge_push_back_type;
+  typedef iterator_property_map<
+            typename std::vector<Property>::iterator,
+            IndexMap> edge_map_type;
+  typedef iterator_property_map<
+            typename std::vector<Property>::const_iterator,
+            IndexMap> const_edge_map_type;
 
   // Directly access a edge or edge bundle
   Property& operator[](Descriptor v)
@@ -127,6 +154,14 @@
   const Property& operator[](Descriptor v) const
   { return m_edge_properties[get(edge_index, derived(), v)]; }
 
+  edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) {
+    return edge_map_type(m_edge_properties.begin(), index_map);
+  }
+
+  const_edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) const {
+    return const_edge_map_type(m_edge_properties.begin(), index_map);
+  }
+
 protected:
   // Default-construct with no property values
   indexed_edge_properties() {}
@@ -205,8 +240,8 @@
   std::ptrdiff_t distance_to(const dummy_no_property_iterator) const {return 0;}
 };
 
-template<typename Derived, typename Descriptor>
-class indexed_edge_properties<Derived, void, Descriptor>
+template<typename Derived, typename Descriptor, typename IndexMap>
+class indexed_edge_properties<Derived, void, Descriptor, IndexMap>
 {
   struct secret {};
 
@@ -214,10 +249,16 @@
   typedef no_property edge_property_type;
   typedef void edge_bundled;
   typedef void* edge_push_back_type;
+  typedef secret edge_map_type;
+  typedef secret const_edge_map_type;
 
   secret operator[](secret) { return secret(); }
   void write_by_index(std::size_t idx, const no_property& prop) {}
 
+  edge_map_type get_edge_bundle(const IndexMap& = IndexMap()) const {
+    return edge_map_type();
+  }
+
  protected:
   // All operations do nothing.
   indexed_edge_properties() { }

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	2010-03-30 13:50:27 EDT (Tue, 30 Mar 2010)
@@ -19,6 +19,7 @@
 #include <boost/graph/erdos_renyi_generator.hpp>
 #include <boost/graph/graph_utility.hpp>
 #include <boost/random/linear_congruential.hpp>
+#include <boost/concept_check.hpp> // for ignore_unused_variable_warning
 #include <cassert>
 #include <iostream>
 #include <vector>
@@ -43,10 +44,15 @@
   int index;
 };
 
-typedef boost::compressed_sparse_row_graph<boost::directedS, VertexData>
+struct EdgeData 
+{
+  int index_e;
+};
+
+typedef boost::compressed_sparse_row_graph<boost::directedS, VertexData, EdgeData>
   CSRGraphT;
 
-typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, VertexData>
+typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, VertexData, EdgeData>
   BidirCSRGraphT;
 
 template <class G1, class VI1, class G2, class VI2, class IsomorphismMap>
@@ -423,6 +429,27 @@
     std::cout << "Testing CSR graph built from unsorted edges" << std::endl;
     std::pair<int, int> unsorted_edges[] = {std::make_pair(5, 0), std::make_pair(3, 2), std::make_pair(4, 1), std::make_pair(4, 0), std::make_pair(0, 2), std::make_pair(5, 2)};
     CSRGraphT g(boost::edges_are_unsorted, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+
+    // Test vertex and edge bundle access
+    boost::ignore_unused_variable_warning(
+      (VertexData&)get(get(boost::vertex_bundle, g), vertex(0, g)));
+    boost::ignore_unused_variable_warning(
+      (const VertexData&)get(get(boost::vertex_bundle, (const CSRGraphT&)g), vertex(0, g)));
+    boost::ignore_unused_variable_warning(
+      (VertexData&)get(boost::vertex_bundle, g, vertex(0, g)));
+    boost::ignore_unused_variable_warning(
+      (const VertexData&)get(boost::vertex_bundle, (const CSRGraphT&)g, vertex(0, g)));
+    put(boost::vertex_bundle, g, vertex(0, g), VertexData());
+    boost::ignore_unused_variable_warning(
+      (EdgeData&)get(get(boost::edge_bundle, g), *edges(g).first));
+    boost::ignore_unused_variable_warning(
+      (const EdgeData&)get(get(boost::edge_bundle, (const CSRGraphT&)g), *edges(g).first));
+    boost::ignore_unused_variable_warning(
+      (EdgeData&)get(boost::edge_bundle, g, *edges(g).first));
+    boost::ignore_unused_variable_warning(
+      (const EdgeData&)get(boost::edge_bundle, (const CSRGraphT&)g, *edges(g).first));
+    put(boost::edge_bundle, g, *edges(g).first, EdgeData());
+
     CSRGraphT g2(boost::edges_are_unsorted_multi_pass, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
     graph_test(g);
     graph_test(g2);
@@ -439,7 +466,7 @@
     // 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);
-    boost::no_property edge_data[3];
+    EdgeData 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(),