[Boost-commit] svn:boost r81770 - in trunk/boost: graph pending

Subject: [Boost-commit] svn:boost r81770 - in trunk/boost: graph pending
From: jewillco_at_[hidden]
Date: 2012-12-07 14:29:13

Author: jewillco
Date: 2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
New Revision: 81770
URL: http://svn.boost.org/trac/boost/changeset/81770

Log:
Fixed directed_graph and undirected_graph handling of vertex_all and edge_all properties
Text files modified: 
   trunk/boost/graph/directed_graph.hpp   |   133 +++++++++++++++++++++++++++------------ 
   trunk/boost/graph/undirected_graph.hpp |    92 +++++++++++++++++++++++++--             
   trunk/boost/pending/property.hpp       |    21 ++++++                                  
   3 files changed, 197 insertions(+), 49 deletions(-)

Modified: trunk/boost/graph/directed_graph.hpp
==============================================================================
--- trunk/boost/graph/directed_graph.hpp	(original)
+++ trunk/boost/graph/directed_graph.hpp	2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
@@ -9,6 +9,10 @@
 
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/properties.hpp>
+#include <boost/pending/property.hpp>
+#include <boost/property_map/transform_value_property_map.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
 
 namespace boost
 {
@@ -27,8 +31,8 @@
  */
 template <
     typename VertexProp = no_property,
-    typename EdgeProp= no_property,
-    typename GraphProp= no_property>
+    typename EdgeProp = no_property,
+    typename GraphProp = no_property>
 class directed_graph
 {
 public:
@@ -39,15 +43,14 @@
     typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
     typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
 
-private:
-    // Wrap the user-specified properties with an index.
-    typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
-    typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
-
+public:
+    // Embed indices into the vertex type.
+    typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
+    typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
 public:
     typedef adjacency_list<
         listS, listS, bidirectionalS,
-        vertex_property, edge_property, GraphProp,
+        internal_vertex_property, internal_edge_property, GraphProp,
         listS
     > graph_type;
 
@@ -80,8 +83,8 @@
     typedef typename graph_type::edge_parallel_category edge_parallel_category;
     typedef typename graph_type::traversal_category traversal_category;
 
-    typedef unsigned vertex_index_type;
-    typedef unsigned edge_index_type;
+    typedef std::size_t vertex_index_type;
+    typedef std::size_t edge_index_type;
 
     directed_graph(GraphProp const& p = GraphProp())
         : m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
@@ -137,6 +140,7 @@
     vertices_size_type num_vertices() const
     { return m_num_vertices; }
 
+
 private:
     // This helper function manages the attribution of vertex indices.
     vertex_descriptor make_index(vertex_descriptor v) {
@@ -150,7 +154,7 @@
     { return make_index(boost::add_vertex(m_graph)); }
 
     vertex_descriptor add_vertex(vertex_property_type const& p)
-    { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+    { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
 
     void clear_vertex(vertex_descriptor v)
     {
@@ -186,7 +190,7 @@
 
     std::pair<edge_descriptor, bool>
     add_edge(vertex_descriptor u, vertex_descriptor v, edge_property_type const& p)
-    { return make_index(boost::add_edge(u, v, edge_property(0u, p), m_graph)); }
+    { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
 
     void remove_edge(vertex_descriptor u, vertex_descriptor v)
     {
@@ -516,37 +520,32 @@
                 DIRECTED_GRAPH& g)
 { return remove_in_edge_if(v, pred, g.impl()); }
 
-// Helper code for working with property maps
-namespace detail
-{
-    struct directed_graph_vertex_property_selector {
-        template <class DirectedGraph, class Property, class Tag>
-        struct bind_ {
-            typedef typename DirectedGraph::graph_type Graph;
-            typedef property_map<Graph, Tag> PropertyMap;
-            typedef typename PropertyMap::type type;
-            typedef typename PropertyMap::const_type const_type;
-        };
-    };
-
-    struct directed_graph_edge_property_selector {
-        template <class DirectedGraph, class Property, class Tag>
-        struct bind_ {
-            typedef typename DirectedGraph::graph_type Graph;
-            typedef property_map<Graph, Tag> PropertyMap;
-            typedef typename PropertyMap::type type;
-            typedef typename PropertyMap::const_type const_type;
-        };
-    };
-}
+template <DIRECTED_GRAPH_PARAMS, typename Property>
+struct property_map<DIRECTED_GRAPH, Property>: property_map<typename DIRECTED_GRAPH::graph_type, Property> {};
 
-template <>
-struct vertex_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_vertex_property_selector type; };
-
-template <>
-struct edge_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_edge_property_selector type; };
+template <DIRECTED_GRAPH_PARAMS>
+struct property_map<DIRECTED_GRAPH, vertex_all_t> {
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
+    const_type;
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::type>
+    type;
+};
+
+template <DIRECTED_GRAPH_PARAMS>
+struct property_map<DIRECTED_GRAPH, edge_all_t> {
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
+    const_type;
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::type>
+    type;
+};
 
 // PropertyGraph concepts
 template <DIRECTED_GRAPH_PARAMS, typename Property>
@@ -559,6 +558,26 @@
 get(Property p, DIRECTED_GRAPH const& g)
 { return get(p, g.impl()); }
 
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::type
+get(vertex_all_t, DIRECTED_GRAPH& g)
+{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type
+get(vertex_all_t, DIRECTED_GRAPH const& g)
+{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, edge_all_t>::type
+get(edge_all_t, DIRECTED_GRAPH& g)
+{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type
+get(edge_all_t, DIRECTED_GRAPH const& g)
+{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
 template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key>
 inline typename property_traits<
     typename property_map<
@@ -568,10 +587,40 @@
 get(Property p, DIRECTED_GRAPH const& g, Key const& k)
 { return get(p, g.impl(), k); }
 
+template <DIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+    typename property_map<
+        typename DIRECTED_GRAPH::graph_type, vertex_all_t
+    >::const_type
+>::value_type
+get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(vertex_all, g.impl(), k).m_base; }
+
+template <DIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+    typename property_map<
+        typename DIRECTED_GRAPH::graph_type, edge_all_t
+    >::const_type
+>::value_type
+get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(edge_all, g.impl(), k).m_base; }
+
 template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
 inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
 { put(p, g.impl(), k, v); }
 
+template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(vertex_all, g.impl(), k,
+      typename DIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
+}
+
+template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(edge_all, g.impl(), k,
+      typename DIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
+}
+
 template <DIRECTED_GRAPH_PARAMS, class Property>
 typename graph_property<DIRECTED_GRAPH, Property>::type&
 get_property(DIRECTED_GRAPH& g, Property p)

Modified: trunk/boost/graph/undirected_graph.hpp
==============================================================================
--- trunk/boost/graph/undirected_graph.hpp	(original)
+++ trunk/boost/graph/undirected_graph.hpp	2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
@@ -9,6 +9,10 @@
 
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/properties.hpp>
+#include <boost/pending/property.hpp>
+#include <boost/property_map/transform_value_property_map.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
 
 namespace boost
 {
@@ -39,16 +43,16 @@
     typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
     typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
 
-private:
+public:
     // Embed indices into the vertex type.
-    typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
-    typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
+    typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
+    typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
 public:
     typedef adjacency_list<listS,
                 listS,
                 undirectedS,
-                vertex_property,
-                edge_property,
+                internal_vertex_property,
+                internal_edge_property,
                 GraphProp,
                 listS> graph_type;
 private:
@@ -151,7 +155,7 @@
     { return make_index(boost::add_vertex(m_graph)); }
 
     vertex_descriptor add_vertex(vertex_property_type const& p)
-    { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+    { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
 
     void clear_vertex(vertex_descriptor v) {
         std::pair<out_edge_iterator, out_edge_iterator>
@@ -188,7 +192,7 @@
     std::pair<edge_descriptor, bool>
     add_edge(vertex_descriptor u, vertex_descriptor v,
              edge_property_type const& p)
-    { return make_index(boost::add_edge(u, v, edge_property(0u, p), m_graph)); }
+    { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
 
     void remove_edge(vertex_descriptor u, vertex_descriptor v) {
         // find all edges, (u, v)
@@ -525,6 +529,30 @@
 template <UNDIRECTED_GRAPH_PARAMS, typename Property>
 struct property_map<UNDIRECTED_GRAPH, Property>: property_map<typename UNDIRECTED_GRAPH::graph_type, Property> {};
 
+template <UNDIRECTED_GRAPH_PARAMS>
+struct property_map<UNDIRECTED_GRAPH, vertex_all_t> {
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
+    const_type;
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::type>
+    type;
+};
+
+template <UNDIRECTED_GRAPH_PARAMS>
+struct property_map<UNDIRECTED_GRAPH, edge_all_t> {
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
+    const_type;
+  typedef transform_value_property_map<
+            detail::remove_first_property,
+            typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::type>
+    type;
+};
+
 // PropertyGraph concepts
 template <UNDIRECTED_GRAPH_PARAMS, typename Property>
 inline typename property_map<UNDIRECTED_GRAPH, Property>::type
@@ -536,6 +564,26 @@
 get(Property p, UNDIRECTED_GRAPH const& g)
 { return get(p, g.impl()); }
 
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type
+get(vertex_all_t, UNDIRECTED_GRAPH& g)
+{ return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type
+get(vertex_all_t, UNDIRECTED_GRAPH const& g)
+{ return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type
+get(edge_all_t, UNDIRECTED_GRAPH& g)
+{ return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type
+get(edge_all_t, UNDIRECTED_GRAPH const& g)
+{ return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
 template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key>
 inline typename property_traits<
     typename property_map<
@@ -545,10 +593,40 @@
 get(Property p, UNDIRECTED_GRAPH const& g, Key const& k)
 { return get(p, g.impl(), k); }
 
+template <UNDIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+    typename property_map<
+        typename UNDIRECTED_GRAPH::graph_type, vertex_all_t
+    >::const_type
+>::value_type
+get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(vertex_all, g.impl(), k).m_base; }
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+    typename property_map<
+        typename UNDIRECTED_GRAPH::graph_type, edge_all_t
+    >::const_type
+>::value_type
+get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(edge_all, g.impl(), k).m_base; }
+
 template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
 inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
 { put(p, g.impl(), k, v); }
 
+template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(vertex_all, g.impl(), k,
+      typename UNDIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
+}
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(edge_all, g.impl(), k,
+      typename UNDIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
+}
+
 template <UNDIRECTED_GRAPH_PARAMS, class Property>
 inline typename graph_property<UNDIRECTED_GRAPH, Property>::type&
 get_property(UNDIRECTED_GRAPH& g, Property p)

Modified: trunk/boost/pending/property.hpp
==============================================================================
--- trunk/boost/pending/property.hpp	(original)
+++ trunk/boost/pending/property.hpp	2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
@@ -244,6 +244,27 @@
 
 } // namespace detail
 
+namespace detail {
+  // Stuff for directed_graph and undirected_graph to skip over their first
+  // vertex_index and edge_index properties when providing vertex_all and
+  // edge_all; make sure you know the exact structure of your properties if you
+  // use there.
+  struct remove_first_property {
+    template <typename F>
+    struct result {
+      typedef typename boost::function_traits<F>::arg1_type a1;
+      typedef typename boost::remove_reference<a1>::type non_ref;
+      typedef typename non_ref::next_type nx;
+      typedef typename boost::mpl::if_<boost::is_const<non_ref>, boost::add_const<nx>, nx>::type with_const;
+      typedef typename boost::add_reference<with_const>::type type;
+    };
+    template <typename Prop>
+    typename Prop::next_type& operator()(Prop& p) const {return p.m_base;}
+    template <typename Prop>
+    const typename Prop::next_type& operator()(const Prop& p) const {return p.m_base;}
+  };
+}
+
 } // namesapce boost
 
 #endif /* BOOST_PROPERTY_HPP */