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

Subject: [Boost-commit] svn:boost r53217 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-05-23 14:07:02

Author: jewillco
Date: 2009-05-23 14:07:02 EDT (Sat, 23 May 2009)
New Revision: 53217
URL: http://svn.boost.org/trac/boost/changeset/53217

Log:
Added graph properties to adjacency_matrix; fixed constructors to match documentation; fixes #875
Text files modified: 
   trunk/boost/graph/adjacency_matrix.hpp          |    75 ++++++++++++++++++++++++++++++++++++++- 
   trunk/libs/graph/test/adjacency_matrix_test.cpp |    41 +++++++++++++++++++++                   
   2 files changed, 114 insertions(+), 2 deletions(-)

Modified: trunk/boost/graph/adjacency_matrix.hpp
==============================================================================
--- trunk/boost/graph/adjacency_matrix.hpp	(original)
+++ trunk/boost/graph/adjacency_matrix.hpp	2009-05-23 14:07:02 EDT (Sat, 23 May 2009)
@@ -600,13 +600,52 @@
     typedef adjacency_matrix_class_tag graph_tag;
 
     // Constructor required by MutableGraph
-    adjacency_matrix(vertices_size_type n_vertices)
+    adjacency_matrix(vertices_size_type n_vertices,
+                     const GraphProperty& p = GraphProperty())
       : m_matrix(Directed::is_directed ?
                  (n_vertices * n_vertices)
                  : (n_vertices * (n_vertices + 1) / 2)),
       m_vertex_set(0, n_vertices),
       m_vertex_properties(n_vertices),
-      m_num_edges(0) { }
+      m_num_edges(0),
+      m_property(p) { }
+
+    template <typename EdgeIterator>
+    adjacency_matrix(EdgeIterator first,
+                     EdgeIterator last,
+                     vertices_size_type n_vertices,
+                     const GraphProperty& p = GraphProperty())
+      : m_matrix(Directed::is_directed ?
+                 (n_vertices * n_vertices)
+                 : (n_vertices * (n_vertices + 1) / 2)),
+      m_vertex_set(0, n_vertices),
+      m_vertex_properties(n_vertices),
+      m_num_edges(0),
+      m_property(p)
+    {
+      for (; first != last; ++first) {
+        add_edge(first->first, first->second, *this);
+      }
+    }
+
+    template <typename EdgeIterator, typename EdgePropertyIterator>
+    adjacency_matrix(EdgeIterator first,
+                     EdgeIterator last,
+                     EdgePropertyIterator ep_iter,
+                     vertices_size_type n_vertices,
+                     const GraphProperty& p = GraphProperty())
+      : m_matrix(Directed::is_directed ?
+                 (n_vertices * n_vertices)
+                 : (n_vertices * (n_vertices + 1) / 2)),
+      m_vertex_set(0, n_vertices),
+      m_vertex_properties(n_vertices),
+      m_num_edges(0),
+      m_property(p)
+    {
+      for (; first != last; ++first, ++ep_iter) {
+        add_edge(first->first, first->second, *ep_iter, *this);
+      }
+    }
 
 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
     // Directly access a vertex or edge bundle
@@ -650,6 +689,7 @@
     VertexList m_vertex_set;
     std::vector<vertex_property_type> m_vertex_properties;
     size_type m_num_edges;
+    GraphProperty m_property;
   };
 
   //=========================================================================
@@ -995,6 +1035,37 @@
   }
 
   //=========================================================================
+  // Functions required by the PropertyGraph concept
+
+  // O(1)
+  template <typename D, typename VP, typename EP, typename GP, typename A,
+            typename Tag, typename Value>
+  inline void
+  set_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag, const Value& value)
+  {
+      get_property_value(g.m_property, Tag()) = value;
+  }
+
+  template <typename D, typename VP, typename EP, typename GP, typename A,
+            typename Tag>
+  inline
+  typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type&
+  get_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag)
+  {
+      return get_property_value(g.m_property, Tag());
+  }
+
+  template <typename D, typename VP, typename EP, typename GP, typename A,
+            typename Tag>
+  inline
+  const
+  typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type&
+  get_property(const adjacency_matrix<D,VP,EP,GP,A>& g, Tag)
+  {
+      return get_property_value(g.m_property, Tag());
+  }
+
+  //=========================================================================
   // Vertex Property Map
 
   template <typename GraphPtr, typename Vertex, typename T, typename R,

Modified: trunk/libs/graph/test/adjacency_matrix_test.cpp
==============================================================================
--- trunk/libs/graph/test/adjacency_matrix_test.cpp	(original)
+++ trunk/libs/graph/test/adjacency_matrix_test.cpp	2009-05-23 14:07:02 EDT (Sat, 23 May 2009)
@@ -42,6 +42,12 @@
 
 #include <boost/test/minimal.hpp>
 
+#include <vector>
+#include <algorithm> // For std::sort
+#include <boost/type_traits/is_convertible.hpp>
+
+#include <boost/graph/iteration_macros.hpp>
+
 template<typename Graph1, typename Graph2>
 void run_test()
 {
@@ -194,6 +200,41 @@
         BOOST_CHECK(boost::get(index_map1, boost::target(*iei1, g1)) == boost::get(index_map2, boost::target(*iei2, g2)));
       }
    }
+
+   // Test construction from a range of pairs
+   std::vector<std::pair<int, int> > edge_pairs_g1;
+   BGL_FORALL_EDGES_T(e, g1, Graph1) {
+     edge_pairs_g1.push_back(
+       std::make_pair(get(index_map1, source(e, g1)),
+                      get(index_map1, target(e, g1))));
+   }
+   Graph2 g3(edge_pairs_g1.begin(), edge_pairs_g1.end(), num_vertices(g1));
+   BOOST_CHECK(num_vertices(g1) == num_vertices(g3));
+   std::vector<std::pair<int, int> > edge_pairs_g3;
+   IndexMap2 index_map3 = boost::get(boost::vertex_index_t(), g3);
+   BGL_FORALL_EDGES_T(e, g3, Graph2) {
+     edge_pairs_g3.push_back(
+       std::make_pair(get(index_map3, source(e, g3)),
+                      get(index_map3, target(e, g3))));
+   }
+   // Normalize the edge pairs for comparison
+   if (boost::is_convertible<typename boost::graph_traits<Graph1>::directed_category*, boost::undirected_tag*>::value || boost::is_convertible<typename boost::graph_traits<Graph2>::directed_category*, boost::undirected_tag*>::value) {
+     for (size_t i = 0; i < edge_pairs_g1.size(); ++i) {
+       if (edge_pairs_g1[i].first < edge_pairs_g1[i].second) {
+         std::swap(edge_pairs_g1[i].first, edge_pairs_g1[i].second);
+       }
+     }
+     for (size_t i = 0; i < edge_pairs_g3.size(); ++i) {
+       if (edge_pairs_g3[i].first < edge_pairs_g3[i].second) {
+         std::swap(edge_pairs_g3[i].first, edge_pairs_g3[i].second);
+       }
+     }
+   }
+   std::sort(edge_pairs_g1.begin(), edge_pairs_g1.end());
+   std::sort(edge_pairs_g3.begin(), edge_pairs_g3.end());
+   edge_pairs_g1.erase(std::unique(edge_pairs_g1.begin(), edge_pairs_g1.end()), edge_pairs_g1.end());
+   edge_pairs_g3.erase(std::unique(edge_pairs_g3.begin(), edge_pairs_g3.end()), edge_pairs_g3.end());
+   BOOST_CHECK(edge_pairs_g1 == edge_pairs_g3);
 }
 
 template <typename Graph>