ceph/src/boost/libs/graph/include/boost/graph/detail/labeled_graph_traits.hpp

   1 // Copyright (C) 2009 Andrew Sutton
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP
   8 #define BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP
   9
  10 #include <boost/graph/graph_mutability_traits.hpp>
  11
  12 namespace boost {
  13
  14 // Extend the graph mutability traits (and metafunctions) to include options
  15 // for labeled graphs.
  16
  17 // NOTE: the label_vertex tag denotes the fact that you can basically assign
  18 // arbitrary labels to vertices without modifying the actual graph.
  19
  20 // TODO: We might also overlay the uniqueness/multiplicity of labels in this
  21 // hierarchy also. For now, we just assumed that labels are unique.
  22
  23 struct label_vertex_tag { };
  24 struct labeled_add_vertex_tag : virtual label_vertex_tag { };
  25 struct labeled_add_vertex_property_tag : virtual labeled_add_vertex_tag { };
  26 struct labeled_remove_vertex_tag { };
  27 struct labeled_add_edge_tag : virtual label_vertex_tag { };
  28 struct labeled_add_edge_property_tag : virtual labeled_add_edge_tag{ };
  29 struct labeled_remove_edge_tag { };
  30
  31 struct labeled_mutable_vertex_graph_tag
  32     : virtual labeled_add_vertex_tag, virtual labeled_remove_vertex_tag
  33 { };
  34 struct labeled_mutable_vertex_property_graph_tag
  35     : virtual labeled_add_vertex_property_tag, virtual labeled_remove_vertex_tag
  36 { };
  37 struct labeled_mutable_edge_graph_tag
  38     : virtual labeled_add_edge_tag, virtual labeled_remove_edge_tag
  39 { };
  40 struct labeled_mutable_edge_property_graph_tag
  41     : virtual labeled_add_edge_property_tag, virtual labeled_remove_edge_tag
  42 { };
  43
  44 struct labeled_graph_tag
  45     : virtual label_vertex_tag
  46 { };
  47 struct labeled_mutable_graph_tag
  48     : virtual labeled_mutable_vertex_graph_tag
  49     , virtual labeled_mutable_edge_graph_tag
  50 { };
  51 struct labeled_mutable_property_graph_tag
  52     : virtual labeled_mutable_vertex_property_graph_tag
  53     , virtual labeled_mutable_edge_property_graph_tag
  54 { };
  55 struct labeled_add_only_property_graph_tag
  56     : virtual labeled_add_vertex_property_tag
  57     , virtual labeled_mutable_edge_property_graph_tag
  58 { };
  59
  60 // Metafunctions
  61
  62 template <typename Graph>
  63 struct graph_has_add_vertex_by_label
  64     : mpl::bool_<
  65         is_convertible<
  66             typename graph_mutability_traits<Graph>::category,
  67             labeled_add_vertex_tag
  68         >::value
  69     >
  70 { };
  71
  72 template <typename Graph>
  73 struct graph_has_add_vertex_by_label_with_property
  74     : mpl::bool_<
  75         is_convertible<
  76             typename graph_mutability_traits<Graph>::category,
  77             labeled_add_vertex_property_tag
  78         >::value
  79     >
  80 { };
  81
  82 template <typename Graph>
  83 struct graph_has_remove_vertex_by_label
  84     : mpl::bool_<
  85         is_convertible<
  86             typename graph_mutability_traits<Graph>::category,
  87             labeled_remove_vertex_tag
  88         >::value
  89     >
  90 { };
  91
  92 template <typename Graph>
  93 struct graph_has_add_edge_by_label
  94     : mpl::bool_<
  95         is_convertible<
  96             typename graph_mutability_traits<Graph>::category,
  97             labeled_add_edge_tag
  98         >::value
  99     >
 100 { };
 101
 102 template <typename Graph>
 103 struct graph_has_add_edge_by_label_with_property
 104     : mpl::bool_<
 105         is_convertible<
 106             typename graph_mutability_traits<Graph>::category,
 107             labeled_add_edge_property_tag
 108         >::value
 109     >
 110 { };
 111
 112 template <typename Graph>
 113 struct graph_has_remove_edge_by_label
 114     : mpl::bool_<
 115         is_convertible<
 116             typename graph_mutability_traits<Graph>::category,
 117             labeled_remove_edge_tag
 118         >::value
 119     >
 120 { };
 121
 122 template <typename Graph>
 123 struct is_labeled_mutable_vertex_graph
 124     : mpl::and_<
 125         graph_has_add_vertex_by_label<Graph>,
 126         graph_has_remove_vertex_by_label<Graph>
 127     >
 128 { };
 129
 130 template <typename Graph>
 131 struct is_labeled_mutable_vertex_property_graph
 132     : mpl::and_<
 133         graph_has_add_vertex_by_label<Graph>,
 134         graph_has_remove_vertex_by_label<Graph>
 135     >
 136 { };
 137
 138 template <typename Graph>
 139 struct is_labeled_mutable_edge_graph
 140     : mpl::and_<
 141         graph_has_add_edge_by_label<Graph>,
 142         graph_has_remove_edge_by_label<Graph>
 143     >
 144 { };
 145
 146 template <typename Graph>
 147 struct is_labeled_mutable_edge_property_graph
 148     : mpl::and_<
 149         graph_has_add_edge_by_label<Graph>,
 150         graph_has_remove_edge_by_label<Graph>
 151     >
 152 { };
 153
 154 template <typename Graph>
 155 struct is_labeled_mutable_graph
 156     : mpl::and_<
 157         is_labeled_mutable_vertex_graph<Graph>,
 158         is_labeled_mutable_edge_graph<Graph>
 159     >
 160 { };
 161
 162 template <typename Graph>
 163 struct is_labeled_mutable_property_graph
 164     : mpl::and_<
 165         is_labeled_mutable_vertex_property_graph<Graph>,
 166         is_labeled_mutable_edge_property_graph<Graph>
 167     >
 168 { };
 169
 170 template <typename Graph>
 171 struct is_labeled_add_only_property_graph
 172     : mpl::bool_<
 173         is_convertible<
 174             typename graph_mutability_traits<Graph>::category,
 175             labeled_add_only_property_graph_tag
 176         >::value
 177     >
 178 { };
 179
 180 template <typename Graph>
 181 struct is_labeled_graph
 182     : mpl::bool_<
 183         is_convertible<
 184             typename graph_mutability_traits<Graph>::category,
 185             label_vertex_tag
 186         >::value
 187     >
 188 { };
 189
 190 template <typename> struct graph_mutability_traits;
 191
 192 namespace graph_detail {
 193     // The determine mutability metafunction computes a labeled mutability tag
 194     // based on the mutability of the given graph type. This is used by the
 195     // graph_mutability_traits specialization below.
 196     template <typename Graph>
 197     struct determine_mutability {
 198         typedef typename mpl::if_<
 199             is_add_only_property_graph<Graph>,
 200             labeled_add_only_property_graph_tag,
 201             typename mpl::if_<
 202                 is_mutable_property_graph<Graph>,
 203                 labeled_mutable_property_graph_tag,
 204                 typename mpl::if_<
 205                     is_mutable_graph<Graph>,
 206                     labeled_mutable_graph_tag,
 207                     typename mpl::if_<
 208                         is_mutable_edge_graph<Graph>,
 209                         labeled_graph_tag,
 210                         typename graph_mutability_traits<Graph>::category
 211                     >::type
 212                 >::type
 213             >::type
 214         >::type type;
 215     };
 216 } // namespace graph_detail
 217
 218 #define LABELED_GRAPH_PARAMS typename G, typename L, typename S
 219 #define LABELED_GRAPH labeled_graph<G,L,S>
 220
 221 // Specialize mutability traits for the labeled graph.
 222 // This specialization depends on the mutability of the underlying graph type.
 223 // If the underlying graph is fully mutable, this is also fully mutable.
 224 // Otherwise, it's different.
 225 template <LABELED_GRAPH_PARAMS>
 226 struct graph_mutability_traits< LABELED_GRAPH > {
 227     typedef typename graph_detail::determine_mutability<
 228         typename LABELED_GRAPH::graph_type
 229     >::type category;
 230 };
 231
 232 #undef LABELED_GRAPH_PARAMS
 233 #undef LABELED_GRAPH
 234
 235 } // namespace boost
 236
 237 #endif