[Boost-commit] svn:boost r52910 - in trunk/boost/graph: . detail

Subject: [Boost-commit] svn:boost r52910 - in trunk/boost/graph: . detail
From: asutton_at_[hidden]
Date: 2009-05-11 13:37:47

Author: asutton
Date: 2009-05-11 13:37:47 EDT (Mon, 11 May 2009)
New Revision: 52910
URL: http://svn.boost.org/trac/boost/changeset/52910

Log:
WS cleanup.

Added:
   trunk/boost/graph/detail/labeled_graph_traits.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/adjacency_list.hpp |   101 ++++++++++++++++++++++++++------------- 
   1 files changed, 67 insertions(+), 34 deletions(-)

Modified: trunk/boost/graph/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/adjacency_list.hpp	(original)
+++ trunk/boost/graph/adjacency_list.hpp	2009-05-11 13:37:47 EDT (Mon, 11 May 2009)
@@ -63,17 +63,20 @@
 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 
 #if !defined BOOST_NO_SLIST
-  struct slistS {};  
+  struct slistS {};
 #endif
 
   struct vecS  { };
   struct listS { };
   struct setS { };
-  struct multisetS { };
   struct mapS  { };
+  struct multisetS { };
+  struct multimapS { };
 #if !defined BOOST_NO_HASH
-  struct hash_mapS { };
   struct hash_setS { };
+  struct hash_mapS { };
+  struct hash_multisetS { };
+  struct hash_multimapS { };
 #endif
 
   template <class Selector, class ValueType>
@@ -109,16 +112,31 @@
     typedef std::multiset<ValueType> type;
   };
 
+  template <class ValueType>
+  struct container_gen<multimapS, ValueType> {
+    typedef std::multiset<ValueType> type;
+  };
+
 #if !defined BOOST_NO_HASH
   template <class ValueType>
-  struct container_gen<hash_mapS, ValueType> {
+  struct container_gen<hash_setS, ValueType> {
     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
   };
 
   template <class ValueType>
-  struct container_gen<hash_setS, ValueType> {
+  struct container_gen<hash_mapS, ValueType> {
     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
   };
+
+  template <class ValueType>
+  struct container_gen<hash_multisetS, ValueType> {
+    typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<ValueType> type;
+  };
+
+  template <class ValueType>
+  struct container_gen<hash_multimapS, ValueType> {
+    typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<ValueType> type;
+  };
 #endif
 
 #else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
@@ -135,37 +153,51 @@
     struct bind_ { typedef std::vector<T> type; };
   };
 
-  struct listS { 
+  struct listS {
     template <class T>
     struct bind_ { typedef std::list<T> type; };
   };
 
-  struct setS  { 
+  struct setS  {
     template <class T>
     struct bind_ { typedef std::set<T, std::less<T> > type; };
   };
 
-  struct multisetS  { 
+
+  struct mapS  {
+    template <class T>
+    struct bind_ { typedef std::set<T, std::less<T> > type; };
+  };
+
+  struct multisetS  {
+    template <class T>
+    struct bind_ { typedef std::multiset<T, std::less<T> > type; };
+  };
+
+  struct multimapS  {
     template <class T>
     struct bind_ { typedef std::multiset<T, std::less<T> > type; };
   };
 
 #if !defined BOOST_NO_HASH
-  struct hash_setS { 
+  struct hash_setS {
     template <class T>
     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
   };
-#endif
 
-  struct mapS  { 
+  struct hash_mapS {
     template <class T>
-    struct bind_ { typedef std::set<T, std::less<T> > type; };
+    struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
   };
 
-#if !defined BOOST_NO_HASH
-  struct hash_mapS { 
+  struct hash_multisetS {
     template <class T>
-    struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
+    struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<T, std::less<T> > type; };
+  };
+
+  struct hash_multimapS {
+    template <class T>
+    struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<T, std::less<T> > type; };
   };
 #endif
 
@@ -202,54 +234,54 @@
   struct parallel_edge_traits { };
 
   template <>
-  struct parallel_edge_traits<vecS> { 
+  struct parallel_edge_traits<vecS> {
     typedef allow_parallel_edge_tag type; };
 
   template <>
-  struct parallel_edge_traits<listS> { 
+  struct parallel_edge_traits<listS> {
     typedef allow_parallel_edge_tag type; };
 
 #if !defined BOOST_NO_SLIST
   template <>
-  struct parallel_edge_traits<slistS> { 
+  struct parallel_edge_traits<slistS> {
     typedef allow_parallel_edge_tag type; };
 #endif
 
   template <>
-  struct parallel_edge_traits<setS> { 
+  struct parallel_edge_traits<setS> {
     typedef disallow_parallel_edge_tag type; };
 
   template <>
-  struct parallel_edge_traits<multisetS> { 
+  struct parallel_edge_traits<multisetS> {
     typedef allow_parallel_edge_tag type; };
 
 #if !defined BOOST_NO_HASH
   template <>
   struct parallel_edge_traits<hash_setS> {
-    typedef disallow_parallel_edge_tag type; 
+    typedef disallow_parallel_edge_tag type;
   };
 #endif
 
   // mapS is obsolete, replaced with setS
   template <>
-  struct parallel_edge_traits<mapS> { 
+  struct parallel_edge_traits<mapS> {
     typedef disallow_parallel_edge_tag type; };
 
 #if !defined BOOST_NO_HASH
   template <>
   struct parallel_edge_traits<hash_mapS> {
-    typedef disallow_parallel_edge_tag type; 
+    typedef disallow_parallel_edge_tag type;
   };
 #endif
 
   namespace detail {
-    template <class Directed> struct is_random_access { 
+    template <class Directed> struct is_random_access {
       enum { value = false};
       typedef mpl::false_ type;
     };
     template <>
-    struct is_random_access<vecS> { 
-      enum { value = true }; 
+    struct is_random_access<vecS> {
+      enum { value = true };
       typedef mpl::true_ type;
     };
 
@@ -298,7 +330,7 @@
     typedef typename container_gen<EdgeListS, dummy>::type EdgeContainer;
     typedef typename DirectedS::is_bidir_t BidirectionalT;
     typedef typename DirectedS::is_directed_t DirectedT;
-    typedef typename mpl::and_<DirectedT, 
+    typedef typename mpl::and_<DirectedT,
       typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
   public:
     typedef typename mpl::if_<on_edge_storage,
@@ -328,7 +360,7 @@
     : public detail::adj_list_gen<
       adjacency_list<OutEdgeListS,VertexListS,DirectedS,
                      VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
-      VertexListS, OutEdgeListS, DirectedS, 
+      VertexListS, OutEdgeListS, DirectedS,
 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
       typename detail::retag_property_list<vertex_bundle_t,
                                            VertexProperty>::type,
@@ -345,6 +377,7 @@
                                        EdgeListS>::vertex_descriptor,
         VertexProperty>
   {
+      public: // TODO Remove me
 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
     typedef typename detail::retag_property_list<vertex_bundle_t,
                                                  VertexProperty>::retagged
@@ -381,7 +414,7 @@
   private:
     typedef adjacency_list self;
     typedef typename detail::adj_list_gen<
-      self, VertexListS, OutEdgeListS, DirectedS, 
+      self, VertexListS, OutEdgeListS, DirectedS,
       vertex_property_type, edge_property_type, GraphProperty, EdgeListS
     >::type Base;
 
@@ -399,7 +432,7 @@
 
     typedef GraphProperty graph_property_type;
 
-    inline adjacency_list(const GraphProperty& p = GraphProperty()) 
+    inline adjacency_list(const GraphProperty& p = GraphProperty())
       : m_property(p) { }
 
     inline adjacency_list(const adjacency_list& x)
@@ -415,7 +448,7 @@
     }
 
     // Required by Mutable Graph
-    inline adjacency_list(vertices_size_type num_vertices, 
+    inline adjacency_list(vertices_size_type num_vertices,
                           const GraphProperty& p = GraphProperty())
       : Base(num_vertices), m_property(p) { }
 
@@ -531,12 +564,12 @@
   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
                                     GraphProperty, EdgeListS>& g)
   {
-    typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, 
+    typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
                                                  EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::type
       result_type;
     return result_type(&g, p);
   }
-  
+
   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
   inline
@@ -545,7 +578,7 @@
   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
                                     GraphProperty, EdgeListS> const & g)
   {
-    typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, 
+    typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
                                                  EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::const_type
       result_type;
     return result_type(&g, p);

Added: trunk/boost/graph/detail/labeled_graph_traits.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/detail/labeled_graph_traits.hpp	2009-05-11 13:37:47 EDT (Mon, 11 May 2009)
@@ -0,0 +1,237 @@
+// Copyright (C) 2009 Andrew Sutton
+
+// Use, modification and distribution is subject to the Boost Software
+// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP
+#define BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP
+
+#include <boost/graph/graph_mutability_traits.hpp>
+
+namespace boost {
+
+// Extend the graph mutability traits (and metafunctions) to include options
+// for labeled graphs.
+
+// NOTE: the label_vertex tag denotes the fact that you can basically assign
+// arbitrary labels to vertices without modifying the actual graph.
+
+// TODO: We might also overlay the uniqueness/multiplicity of labels in this
+// hierarchy also. For now, we just assumed that labels are unique.
+
+struct label_vertex_tag { };
+struct labeled_add_vertex_tag : virtual label_vertex_tag { };
+struct labeled_add_vertex_property_tag : virtual labeled_add_vertex_tag { };
+struct labeled_remove_vertex_tag { };
+struct labeled_add_edge_tag : virtual label_vertex_tag { };
+struct labeled_add_edge_property_tag : virtual labeled_add_edge_tag{ };
+struct labeled_remove_edge_tag { };
+
+struct labeled_mutable_vertex_graph_tag
+    : virtual labeled_add_vertex_tag, virtual labeled_remove_vertex_tag
+{ };
+struct labeled_mutable_vertex_property_graph_tag
+    : virtual labeled_add_vertex_property_tag, virtual labeled_remove_vertex_tag
+{ };
+struct labeled_mutable_edge_graph_tag
+    : virtual labeled_add_edge_tag, virtual labeled_remove_edge_tag
+{ };
+struct labeled_mutable_edge_property_graph_tag
+    : virtual labeled_add_edge_property_tag, virtual labeled_remove_edge_tag
+{ };
+
+struct labeled_graph_tag
+    : virtual label_vertex_tag
+{ };
+struct labeled_mutable_graph_tag
+    : virtual labeled_mutable_vertex_graph_tag
+    , virtual labeled_mutable_edge_graph_tag
+{ };
+struct labeled_mutable_property_graph_tag
+    : virtual labeled_mutable_vertex_property_graph_tag
+    , virtual labeled_mutable_edge_property_graph_tag
+{ };
+struct labeled_add_only_property_graph_tag
+    : virtual labeled_add_vertex_property_tag
+    , virtual labeled_mutable_edge_property_graph_tag
+{ };
+
+// Metafunctions
+
+template <typename Graph>
+struct graph_has_add_vertex_by_label
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            labeled_add_vertex_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_add_vertex_by_label_with_property
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            labeled_add_vertex_property_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_remove_vertex_by_label
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            labeled_remove_vertex_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_add_edge_by_label
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            labeled_add_edge_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_add_edge_by_label_with_property
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            labeled_add_edge_property_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_remove_edge_by_label
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            labeled_remove_edge_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_mutable_vertex_graph
+    : mpl::and_<
+        graph_has_add_vertex_by_label<Graph>,
+        graph_has_remove_vertex_by_label<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_mutable_vertex_property_graph
+    : mpl::and_<
+        graph_has_add_vertex_by_label<Graph>,
+        graph_has_remove_vertex_by_label<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_mutable_edge_graph
+    : mpl::and_<
+        graph_has_add_edge_by_label<Graph>,
+        graph_has_remove_edge_by_label<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_mutable_edge_property_graph
+    : mpl::and_<
+        graph_has_add_edge_by_label<Graph>,
+        graph_has_remove_edge_by_label<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_mutable_graph
+    : mpl::and_<
+        is_labeled_mutable_vertex_graph<Graph>,
+        is_labeled_mutable_edge_graph<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_mutable_property_graph
+    : mpl::and_<
+        is_labeled_mutable_vertex_property_graph<Graph>,
+        is_labeled_mutable_edge_property_graph<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_add_only_property_graph
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            labeled_add_only_property_graph_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct is_labeled_graph
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            label_vertex_tag
+        >::value
+    >
+{ };
+
+template <typename> class graph_mutability_traits;
+
+namespace graph_detail {
+    // The determine mutability metafunction computes a labeled mutability tag
+    // based on the mutability of the given graph type. This is used by the
+    // graph_mutability_traits specialization below.
+    template <typename Graph>
+    struct determine_mutability {
+        typedef typename mpl::if_<
+            is_add_only_property_graph<Graph>,
+            labeled_add_only_property_graph_tag,
+            typename mpl::if_<
+                is_mutable_property_graph<Graph>,
+                labeled_mutable_property_graph_tag,
+                typename mpl::if_<
+                    is_mutable_graph<Graph>,
+                    labeled_mutable_graph_tag,
+                    typename mpl::if_<
+                        is_mutable_edge_graph<Graph>,
+                        labeled_graph_tag,
+                        typename graph_mutability_traits<Graph>::category
+                    >::type
+                >::type
+            >::type
+        >::type type;
+    };
+} // namespace graph_detail
+
+#define LABELED_GRAPH_PARAMS typename G, typename L, typename S
+#define LABELED_GRAPH labeled_graph<G,L,S>
+
+// Specialize mutability traits for for the labeled graph.
+// This specialization depends on the mutability of the underlying graph type.
+// If the underlying graph is fully mutable, this this is also fully mutable.
+// Otherwise, it's different.
+template <LABELED_GRAPH_PARAMS>
+struct graph_mutability_traits< LABELED_GRAPH > {
+    typedef typename graph_detail::determine_mutability<
+        typename LABELED_GRAPH::graph_type
+    >::type category;
+};
+
+#undef LABELED_GRAPH_PARAMS
+#undef LABELED_GRAPH
+
+} // namespace boost
+
+#endif