[Boost-commit] svn:boost r52907 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r52907 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-05-11 13:35:03

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

Log:
Added a new traits framework fro determining the mutability of graph
types. This is used extensively in the new testing framework.

Added:
   trunk/boost/graph/graph_mutability_traits.hpp   (contents, props changed)

Added: trunk/boost/graph/graph_mutability_traits.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/graph_mutability_traits.hpp	2009-05-11 13:35:03 EDT (Mon, 11 May 2009)
@@ -0,0 +1,243 @@
+// 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_MUTABILITY_TRAITS_HPP
+#define BOOST_GRAPH_MUTABILITY_TRAITS_HPP
+
+#include <boost/config.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace boost {
+
+// The mutabiltiy categories classify graphs by their mutating operations
+// on the edge and vertex sets. This is a substantially more refined
+// categorization than the MutableGraph and MutablePropertyGraph denote.
+// Currently, this framework is only used in the graph tests to help
+// dispatch test to the correct places. However, there are probably some
+// constructive or destructive algorithms (i.e., graph generators) that
+// may use these to describe requirements on graph inputs.
+
+struct add_vertex_tag { };
+struct add_vertex_property_tag : virtual add_vertex_tag { };
+struct add_edge_tag { };
+struct add_edge_property_tag : virtual add_edge_tag { };
+struct remove_vertex_tag { };
+struct remove_edge_tag { };
+
+struct mutable_vertex_graph_tag
+    : virtual add_vertex_tag, virtual remove_vertex_tag
+{ };
+struct mutable_vertex_property_graph_tag
+    : virtual add_vertex_property_tag, virtual remove_vertex_tag
+{ };
+
+struct mutable_edge_graph_tag
+    : virtual add_edge_tag, virtual remove_edge_tag
+{ };
+struct mutable_edge_property_graph_tag
+    : virtual add_edge_property_tag, virtual remove_edge_tag
+{ };
+
+struct mutable_graph_tag
+    : virtual mutable_vertex_graph_tag
+    , virtual mutable_edge_graph_tag
+{ };
+struct mutable_property_graph_tag
+    : virtual mutable_vertex_property_graph_tag
+    , virtual mutable_edge_property_graph_tag
+{ };
+
+// Some graphs just don't like to be torn down. Note this only restricts
+// teardown to the set of vertices, not the vertex set.
+// TODO: Find a better name for this tag.
+struct add_only_property_graph_tag
+    : virtual add_vertex_property_tag
+    , virtual mutable_edge_property_graph_tag
+{ };
+
+/**
+ * The graph_mutability_traits provide methods for determining the
+ * interfaces supported by graph classes for adding and removing vertices
+ * and edges.
+ */
+template <typename Graph>
+struct graph_mutability_traits {
+    typedef typename Graph::mutability_category category;
+};
+
+template <typename Graph>
+struct graph_has_add_vertex
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            add_vertex_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_add_vertex_with_property
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            add_vertex_property_tag
+        >::value
+    >
+{ };
+
+
+template <typename Graph>
+struct graph_has_remove_vertex
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            remove_vertex_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_add_edge
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            add_edge_tag
+        >::value
+    >
+{ };
+
+template <typename Graph>
+struct graph_has_add_edge_with_property
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            add_edge_property_tag
+        >::value
+    >
+{ };
+
+
+template <typename Graph>
+struct graph_has_remove_edge
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            remove_edge_tag
+        >::value
+    >
+{ };
+
+
+template <typename Graph>
+struct is_mutable_vertex_graph
+    : mpl::and_<
+        graph_has_add_vertex<Graph>,
+        graph_has_remove_vertex<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_mutable_vertex_property_graph
+    : mpl::and_<
+        graph_has_add_vertex_with_property<Graph>,
+        graph_has_remove_vertex<Graph>
+    >
+{ };
+
+
+template <typename Graph>
+struct is_mutable_edge_graph
+    : mpl::and_<
+        graph_has_add_edge<Graph>,
+        graph_has_remove_edge<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_mutable_edge_property_graph
+    : mpl::and_<
+        graph_has_add_edge_with_property<Graph>,
+        graph_has_remove_edge<Graph>
+    >
+{ };
+
+
+template <typename Graph>
+struct is_mutable_graph
+    : mpl::and_<
+        is_mutable_vertex_graph<Graph>,
+        is_mutable_edge_graph<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_mutable_property_graph
+    : mpl::and_<
+        is_mutable_vertex_property_graph<Graph>,
+        is_mutable_edge_property_graph<Graph>
+    >
+{ };
+
+template <typename Graph>
+struct is_add_only_property_graph
+    : mpl::bool_<
+        is_convertible<
+            typename graph_mutability_traits<Graph>::category,
+            add_only_property_graph_tag
+        >::value
+    >
+{ };
+
+/** @name Mutability Traits Specializations */
+//@{
+#define ADJLIST_PARAMS \
+    typename OEL, typename VL, typename D, typename VP, typename EP, \
+    typename GP, typename EL
+#define ADJLIST adjacency_list<OEL,VL,D,VP,EP,GP,EL>
+template <ADJLIST_PARAMS> class adjacency_list;
+template <ADJLIST_PARAMS>
+struct graph_mutability_traits<ADJLIST> {
+    typedef mutable_property_graph_tag category;
+};
+
+// Never remove vertices from adjacency lists with VL==vecS
+template <typename OEL, typename D, typename VP, typename EP, typename GP, typename EL>
+struct graph_mutability_traits< adjacency_list<OEL,vecS,D,VP,EP,GP,EL> > {
+    typedef add_only_property_graph_tag category;
+};
+#undef ADJLIST_PARAMS
+#undef ADJLIST
+
+template <typename VP, typename EP, typename GP> class directed_graph;
+template <typename VP, typename EP, typename GP>
+struct graph_mutability_traits< directed_graph<VP, EP, GP> > {
+    typedef mutable_property_graph_tag category;
+};
+
+template <typename VP, typename EP, typename GP> class undirected_graph;
+template <typename VP, typename EP, typename GP>
+struct graph_mutability_traits< undirected_graph<VP, EP, GP> > {
+    typedef mutable_property_graph_tag category;
+};
+
+#define ADJMAT_PARAMS \
+    typename D, typename VP, typename EP, typename GP, typename A
+#define ADJMAT adjacency_matrix<D,VP,EP,GP,A>
+template <ADJMAT_PARAMS> class adjacency_matrix;
+template <ADJMAT_PARAMS>
+struct graph_mutability_traits<ADJMAT> {
+    typedef mutable_edge_property_graph_tag category;
+};
+#undef ADJMAT_PARAMS
+#undef ADJMAT
+//@}
+
+} // namespace boost
+
+#endif
\ No newline at end of file