ceph/src/boost/boost/graph/graph_archetypes.hpp

   1 //=======================================================================
   2 // Copyright 2002 Indiana University.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #ifndef BOOST_GRAPH_ARCHETYPES_HPP
  11 #define BOOST_GRAPH_ARCHETYPES_HPP
  12
  13 #include <boost/property_map/property_map.hpp>
  14 #include <boost/concept_archetype.hpp>
  15 #include <boost/graph/graph_traits.hpp>
  16 #include <boost/graph/properties.hpp>
  17
  18 namespace boost
  19 { // should use a different namespace for this
  20
  21 namespace detail
  22 {
  23     struct null_graph_archetype : public null_archetype<>
  24     {
  25         struct traversal_category
  26         {
  27         };
  28     };
  29 }
  30
  31 //===========================================================================
  32 template < typename Vertex, typename Directed, typename ParallelCategory,
  33     typename Base = detail::null_graph_archetype >
  34 struct incidence_graph_archetype : public Base
  35 {
  36     typedef typename Base::traversal_category base_trav_cat;
  37     struct traversal_category : public incidence_graph_tag, public base_trav_cat
  38     {
  39     };
  40 #if 0
  41     typedef immutable_graph_tag mutability_category;
  42 #endif
  43     typedef Vertex vertex_descriptor;
  44     typedef unsigned int degree_size_type;
  45     typedef unsigned int vertices_size_type;
  46     typedef unsigned int edges_size_type;
  47     struct edge_descriptor
  48     {
  49         edge_descriptor() {}
  50         edge_descriptor(const detail::dummy_constructor&) {}
  51         bool operator==(const edge_descriptor&) const { return false; }
  52         bool operator!=(const edge_descriptor&) const { return false; }
  53     };
  54     typedef input_iterator_archetype< edge_descriptor > out_edge_iterator;
  55
  56     typedef Directed directed_category;
  57     typedef ParallelCategory edge_parallel_category;
  58
  59     typedef void adjacency_iterator;
  60     typedef void in_edge_iterator;
  61     typedef void vertex_iterator;
  62     typedef void edge_iterator;
  63
  64     static vertex_descriptor null_vertex() { return vertex_descriptor(); }
  65 };
  66 template < typename V, typename D, typename P, typename B >
  67 V source(
  68     const typename incidence_graph_archetype< V, D, P, B >::edge_descriptor&,
  69     const incidence_graph_archetype< V, D, P, B >&)
  70 {
  71     return V(static_object< detail::dummy_constructor >::get());
  72 }
  73 template < typename V, typename D, typename P, typename B >
  74 V target(
  75     const typename incidence_graph_archetype< V, D, P, B >::edge_descriptor&,
  76     const incidence_graph_archetype< V, D, P, B >&)
  77 {
  78     return V(static_object< detail::dummy_constructor >::get());
  79 }
  80
  81 template < typename V, typename D, typename P, typename B >
  82 std::pair< typename incidence_graph_archetype< V, D, P, B >::out_edge_iterator,
  83     typename incidence_graph_archetype< V, D, P, B >::out_edge_iterator >
  84 out_edges(const V&, const incidence_graph_archetype< V, D, P, B >&)
  85 {
  86     typedef typename incidence_graph_archetype< V, D, P, B >::out_edge_iterator
  87         Iter;
  88     return std::make_pair(Iter(), Iter());
  89 }
  90
  91 template < typename V, typename D, typename P, typename B >
  92 typename incidence_graph_archetype< V, D, P, B >::degree_size_type out_degree(
  93     const V&, const incidence_graph_archetype< V, D, P, B >&)
  94 {
  95     return 0;
  96 }
  97
  98 //===========================================================================
  99 template < typename Vertex, typename Directed, typename ParallelCategory,
 100     typename Base = detail::null_graph_archetype >
 101 struct adjacency_graph_archetype : public Base
 102 {
 103     typedef typename Base::traversal_category base_trav_cat;
 104     struct traversal_category : public adjacency_graph_tag, public base_trav_cat
 105     {
 106     };
 107     typedef Vertex vertex_descriptor;
 108     typedef unsigned int degree_size_type;
 109     typedef unsigned int vertices_size_type;
 110     typedef unsigned int edges_size_type;
 111     typedef void edge_descriptor;
 112     typedef input_iterator_archetype< Vertex > adjacency_iterator;
 113
 114     typedef Directed directed_category;
 115     typedef ParallelCategory edge_parallel_category;
 116
 117     typedef void in_edge_iterator;
 118     typedef void out_edge_iterator;
 119     typedef void vertex_iterator;
 120     typedef void edge_iterator;
 121
 122     static vertex_descriptor null_vertex() { return vertex_descriptor(); }
 123 };
 124
 125 template < typename V, typename D, typename P, typename B >
 126 std::pair< typename adjacency_graph_archetype< V, D, P, B >::adjacency_iterator,
 127     typename adjacency_graph_archetype< V, D, P, B >::adjacency_iterator >
 128 adjacent_vertices(const V&, const adjacency_graph_archetype< V, D, P, B >&)
 129 {
 130     typedef typename adjacency_graph_archetype< V, D, P, B >::adjacency_iterator
 131         Iter;
 132     return std::make_pair(Iter(), Iter());
 133 }
 134
 135 template < typename V, typename D, typename P, typename B >
 136 typename adjacency_graph_archetype< V, D, P, B >::degree_size_type out_degree(
 137     const V&, const adjacency_graph_archetype< V, D, P, B >&)
 138 {
 139     return 0;
 140 }
 141
 142 //===========================================================================
 143 template < typename Vertex, typename Directed, typename ParallelCategory,
 144     typename Base = detail::null_graph_archetype >
 145 struct vertex_list_graph_archetype : public Base
 146 {
 147     typedef incidence_graph_archetype< Vertex, Directed, ParallelCategory >
 148         Incidence;
 149     typedef adjacency_graph_archetype< Vertex, Directed, ParallelCategory >
 150         Adjacency;
 151
 152     typedef typename Base::traversal_category base_trav_cat;
 153     struct traversal_category : public vertex_list_graph_tag,
 154                                 public base_trav_cat
 155     {
 156     };
 157 #if 0
 158     typedef immutable_graph_tag mutability_category;
 159 #endif
 160     typedef Vertex vertex_descriptor;
 161     typedef unsigned int degree_size_type;
 162     typedef typename Incidence::edge_descriptor edge_descriptor;
 163     typedef typename Incidence::out_edge_iterator out_edge_iterator;
 164     typedef typename Adjacency::adjacency_iterator adjacency_iterator;
 165
 166     typedef input_iterator_archetype< Vertex > vertex_iterator;
 167     typedef unsigned int vertices_size_type;
 168     typedef unsigned int edges_size_type;
 169
 170     typedef Directed directed_category;
 171     typedef ParallelCategory edge_parallel_category;
 172
 173     typedef void in_edge_iterator;
 174     typedef void edge_iterator;
 175
 176     static vertex_descriptor null_vertex() { return vertex_descriptor(); }
 177 };
 178
 179 template < typename V, typename D, typename P, typename B >
 180 std::pair< typename vertex_list_graph_archetype< V, D, P, B >::vertex_iterator,
 181     typename vertex_list_graph_archetype< V, D, P, B >::vertex_iterator >
 182 vertices(const vertex_list_graph_archetype< V, D, P, B >&)
 183 {
 184     typedef typename vertex_list_graph_archetype< V, D, P, B >::vertex_iterator
 185         Iter;
 186     return std::make_pair(Iter(), Iter());
 187 }
 188
 189 template < typename V, typename D, typename P, typename B >
 190 typename vertex_list_graph_archetype< V, D, P, B >::vertices_size_type
 191 num_vertices(const vertex_list_graph_archetype< V, D, P, B >&)
 192 {
 193     return 0;
 194 }
 195
 196 // ambiguously inherited from incidence graph and adjacency graph
 197 template < typename V, typename D, typename P, typename B >
 198 typename vertex_list_graph_archetype< V, D, P, B >::degree_size_type out_degree(
 199     const V&, const vertex_list_graph_archetype< V, D, P, B >&)
 200 {
 201     return 0;
 202 }
 203
 204 //===========================================================================
 205
 206 struct property_graph_archetype_tag
 207 {
 208 };
 209
 210 template < typename GraphArchetype, typename Property, typename ValueArch >
 211 struct property_graph_archetype : public GraphArchetype
 212 {
 213     typedef property_graph_archetype_tag graph_tag;
 214     typedef ValueArch vertex_property_type;
 215     typedef ValueArch edge_property_type;
 216 };
 217
 218 struct choose_edge_property_map_archetype
 219 {
 220     template < typename Graph, typename Property, typename Tag > struct bind_
 221     {
 222         typedef mutable_lvalue_property_map_archetype<
 223             typename Graph::edge_descriptor, Property >
 224             type;
 225         typedef lvalue_property_map_archetype< typename Graph::edge_descriptor,
 226             Property >
 227             const_type;
 228     };
 229 };
 230 template <> struct edge_property_selector< property_graph_archetype_tag >
 231 {
 232     typedef choose_edge_property_map_archetype type;
 233 };
 234
 235 struct choose_vertex_property_map_archetype
 236 {
 237     template < typename Graph, typename Property, typename Tag > struct bind_
 238     {
 239         typedef mutable_lvalue_property_map_archetype<
 240             typename Graph::vertex_descriptor, Property >
 241             type;
 242         typedef lvalue_property_map_archetype<
 243             typename Graph::vertex_descriptor, Property >
 244             const_type;
 245     };
 246 };
 247
 248 template <> struct vertex_property_selector< property_graph_archetype_tag >
 249 {
 250     typedef choose_vertex_property_map_archetype type;
 251 };
 252
 253 template < typename G, typename P, typename V >
 254 typename property_map< property_graph_archetype< G, P, V >, P >::type get(
 255     P, property_graph_archetype< G, P, V >&)
 256 {
 257     typename property_map< property_graph_archetype< G, P, V >, P >::type pmap;
 258     return pmap;
 259 }
 260
 261 template < typename G, typename P, typename V >
 262 typename property_map< property_graph_archetype< G, P, V >, P >::const_type get(
 263     P, const property_graph_archetype< G, P, V >&)
 264 {
 265     typename property_map< property_graph_archetype< G, P, V >, P >::const_type
 266         pmap;
 267     return pmap;
 268 }
 269
 270 template < typename G, typename P, typename K, typename V >
 271 typename property_traits< typename property_map<
 272     property_graph_archetype< G, P, V >, P >::const_type >::value_type
 273 get(P p, const property_graph_archetype< G, P, V >& g, K k)
 274 {
 275     return get(get(p, g), k);
 276 }
 277
 278 template < typename G, typename P, typename V, typename Key >
 279 void put(
 280     P p, property_graph_archetype< G, P, V >& g, const Key& key, const V& value)
 281 {
 282     typedef typename boost::property_map< property_graph_archetype< G, P, V >,
 283         P >::type Map;
 284     Map pmap = get(p, g);
 285     put(pmap, key, value);
 286 }
 287
 288 struct color_value_archetype
 289 {
 290     color_value_archetype() {}
 291     color_value_archetype(detail::dummy_constructor) {}
 292     bool operator==(const color_value_archetype&) const { return true; }
 293     bool operator!=(const color_value_archetype&) const { return true; }
 294 };
 295 template <> struct color_traits< color_value_archetype >
 296 {
 297     static color_value_archetype white()
 298     {
 299         return color_value_archetype(
 300             static_object< detail::dummy_constructor >::get());
 301     }
 302     static color_value_archetype gray()
 303     {
 304         return color_value_archetype(
 305             static_object< detail::dummy_constructor >::get());
 306     }
 307     static color_value_archetype black()
 308     {
 309         return color_value_archetype(
 310             static_object< detail::dummy_constructor >::get());
 311     }
 312 };
 313
 314 template < typename T > class buffer_archetype
 315 {
 316 public:
 317     void push(const T&) {}
 318     void pop() {}
 319     T& top() { return static_object< T >::get(); }
 320     const T& top() const { return static_object< T >::get(); }
 321     bool empty() const { return true; }
 322 };
 323
 324 } // namespace boost
 325
 326 #endif // BOOST_GRAPH_ARCHETYPES_HPP