ceph/src/boost/libs/graph/include/boost/graph/adjacency_list.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Copyright 2010 Thomas Claveirole
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10
  11 #ifndef BOOST_GRAPH_ADJACENCY_LIST_HPP
  12 #define BOOST_GRAPH_ADJACENCY_LIST_HPP
  13
  14
  15 #include <boost/config.hpp>
  16
  17 #include <vector>
  18 #include <list>
  19 #include <set>
  20
  21 #include <boost/unordered_set.hpp>
  22
  23 #include <boost/scoped_ptr.hpp>
  24
  25 #include <boost/graph/graph_traits.hpp>
  26 #include <boost/graph/graph_mutability_traits.hpp>
  27 #include <boost/graph/graph_selectors.hpp>
  28 #include <boost/property_map/property_map.hpp>
  29 #include <boost/mpl/if.hpp>
  30 #include <boost/mpl/and.hpp>
  31 #include <boost/mpl/not.hpp>
  32 #include <boost/mpl/bool.hpp>
  33 #include <boost/graph/detail/edge.hpp>
  34 #include <boost/type_traits/is_same.hpp>
  35 #include <boost/detail/workaround.hpp>
  36 #include <boost/graph/properties.hpp>
  37 #include <boost/graph/named_graph.hpp>
  38
  39 namespace boost {
  40
  41   //===========================================================================
  42   // Selectors for the VertexList and EdgeList template parameters of
  43   // adjacency_list, and the container_gen traits class which is used
  44   // to map the selectors to the container type used to implement the
  45   // graph.
  46
  47   struct vecS  { };
  48   struct listS { };
  49   struct setS { };
  50   struct mapS  { };
  51   struct multisetS { };
  52   struct multimapS { };
  53   struct hash_setS { };
  54   struct hash_mapS { };
  55   struct hash_multisetS { };
  56   struct hash_multimapS { };
  57
  58   template <class Selector, class ValueType>
  59   struct container_gen { };
  60
  61   template <class ValueType>
  62   struct container_gen<listS, ValueType> {
  63     typedef std::list<ValueType> type;
  64   };
  65
  66   template <class ValueType>
  67   struct container_gen<vecS, ValueType> {
  68     typedef std::vector<ValueType> type;
  69   };
  70
  71   template <class ValueType>
  72   struct container_gen<mapS, ValueType> {
  73     typedef std::set<ValueType> type;
  74   };
  75
  76   template <class ValueType>
  77   struct container_gen<setS, ValueType> {
  78     typedef std::set<ValueType> type;
  79   };
  80
  81   template <class ValueType>
  82   struct container_gen<multisetS, ValueType> {
  83     typedef std::multiset<ValueType> type;
  84   };
  85
  86   template <class ValueType>
  87   struct container_gen<multimapS, ValueType> {
  88     typedef std::multiset<ValueType> type;
  89   };
  90
  91   template <class ValueType>
  92   struct container_gen<hash_setS, ValueType> {
  93     typedef boost::unordered_set<ValueType> type;
  94   };
  95
  96   template <class ValueType>
  97   struct container_gen<hash_mapS, ValueType> {
  98     typedef boost::unordered_set<ValueType> type;
  99   };
 100
 101   template <class ValueType>
 102   struct container_gen<hash_multisetS, ValueType> {
 103     typedef boost::unordered_multiset<ValueType> type;
 104   };
 105
 106   template <class ValueType>
 107   struct container_gen<hash_multimapS, ValueType> {
 108     typedef boost::unordered_multiset<ValueType> type;
 109   };
 110
 111   template <class StorageSelector>
 112   struct parallel_edge_traits { };
 113
 114   template <>
 115   struct parallel_edge_traits<vecS> {
 116     typedef allow_parallel_edge_tag type; };
 117
 118   template <>
 119   struct parallel_edge_traits<listS> {
 120     typedef allow_parallel_edge_tag type; };
 121
 122   template <>
 123   struct parallel_edge_traits<setS> {
 124     typedef disallow_parallel_edge_tag type; };
 125
 126   template <>
 127   struct parallel_edge_traits<multisetS> {
 128     typedef allow_parallel_edge_tag type; };
 129
 130   template <>
 131   struct parallel_edge_traits<hash_setS> {
 132     typedef disallow_parallel_edge_tag type;
 133   };
 134
 135   // mapS is obsolete, replaced with setS
 136   template <>
 137   struct parallel_edge_traits<mapS> {
 138     typedef disallow_parallel_edge_tag type; };
 139
 140   template <>
 141   struct parallel_edge_traits<hash_mapS> {
 142     typedef disallow_parallel_edge_tag type;
 143   };
 144
 145   template <>
 146   struct parallel_edge_traits<hash_multisetS> {
 147     typedef allow_parallel_edge_tag type;
 148   };
 149
 150   template <>
 151   struct parallel_edge_traits<hash_multimapS> {
 152     typedef allow_parallel_edge_tag type;
 153   };
 154
 155   namespace detail {
 156     template <class Directed> struct is_random_access {
 157       enum { value = false};
 158       typedef mpl::false_ type;
 159     };
 160     template <>
 161     struct is_random_access<vecS> {
 162       enum { value = true };
 163       typedef mpl::true_ type;
 164     };
 165
 166   } // namespace detail
 167
 168   template <typename Selector> struct is_distributed_selector: mpl::false_ {};
 169
 170
 171   //===========================================================================
 172   // The adjacency_list_traits class, which provides a way to access
 173   // some of the associated types of an adjacency_list type without
 174   // having to first create the adjacency_list type. This is useful
 175   // when trying to create interior vertex or edge properties who's
 176   // value type is a vertex or edge descriptor.
 177
 178   template <class OutEdgeListS = vecS,
 179             class VertexListS = vecS,
 180             class DirectedS = directedS,
 181             class EdgeListS = listS>
 182   struct adjacency_list_traits
 183   {
 184     typedef typename detail::is_random_access<VertexListS>::type
 185       is_rand_access;
 186     typedef typename DirectedS::is_bidir_t is_bidir;
 187     typedef typename DirectedS::is_directed_t is_directed;
 188
 189     typedef typename mpl::if_<is_bidir,
 190       bidirectional_tag,
 191       typename mpl::if_<is_directed,
 192         directed_tag, undirected_tag
 193       >::type
 194     >::type directed_category;
 195
 196     typedef typename parallel_edge_traits<OutEdgeListS>::type
 197       edge_parallel_category;
 198
 199     typedef std::size_t vertices_size_type;
 200     typedef void* vertex_ptr;
 201     typedef typename mpl::if_<is_rand_access,
 202       vertices_size_type, vertex_ptr>::type vertex_descriptor;
 203     typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
 204       edge_descriptor;
 205
 206   private:
 207     // Logic to figure out the edges_size_type
 208     struct dummy {};
 209     typedef typename container_gen<EdgeListS, dummy>::type EdgeContainer;
 210     typedef typename DirectedS::is_bidir_t BidirectionalT;
 211     typedef typename DirectedS::is_directed_t DirectedT;
 212     typedef typename mpl::and_<DirectedT,
 213       typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
 214   public:
 215     typedef typename mpl::if_<on_edge_storage,
 216        std::size_t, typename EdgeContainer::size_type
 217     >::type edges_size_type;
 218
 219   };
 220
 221 } // namespace boost
 222
 223 #include <boost/graph/detail/adjacency_list.hpp>
 224
 225 namespace boost {
 226
 227   //===========================================================================
 228   // The adjacency_list class.
 229   //
 230
 231   template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer
 232             class VertexListS = vecS, // a Sequence or a RandomAccessContainer
 233             class DirectedS = directedS,
 234             class VertexProperty = no_property,
 235             class EdgeProperty = no_property,
 236             class GraphProperty = no_property,
 237             class EdgeListS = listS>
 238   class adjacency_list
 239     : public detail::adj_list_gen<
 240       adjacency_list<OutEdgeListS,VertexListS,DirectedS,
 241                      VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
 242       VertexListS, OutEdgeListS, DirectedS,
 243       VertexProperty, EdgeProperty,
 244       GraphProperty, EdgeListS>::type,
 245       // Support for named vertices
 246       public graph::maybe_named_graph<
 247         adjacency_list<OutEdgeListS,VertexListS,DirectedS,
 248                        VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
 249         typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS,
 250                                        EdgeListS>::vertex_descriptor,
 251         VertexProperty>
 252   {
 253       public:
 254     typedef GraphProperty graph_property_type;
 255     typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
 256
 257     typedef VertexProperty vertex_property_type;
 258     typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type vertex_bundled;
 259
 260     typedef EdgeProperty edge_property_type;
 261     typedef typename lookup_one_property<EdgeProperty, edge_bundle_t>::type edge_bundled;
 262
 263   private:
 264     typedef adjacency_list self;
 265     typedef typename detail::adj_list_gen<
 266       self, VertexListS, OutEdgeListS, DirectedS,
 267       vertex_property_type, edge_property_type, GraphProperty, EdgeListS
 268     >::type Base;
 269
 270   public:
 271     typedef typename Base::stored_vertex stored_vertex;
 272     typedef typename Base::vertices_size_type vertices_size_type;
 273     typedef typename Base::edges_size_type edges_size_type;
 274     typedef typename Base::degree_size_type degree_size_type;
 275     typedef typename Base::vertex_descriptor vertex_descriptor;
 276     typedef typename Base::edge_descriptor edge_descriptor;
 277     typedef OutEdgeListS out_edge_list_selector;
 278     typedef VertexListS vertex_list_selector;
 279     typedef DirectedS directed_selector;
 280     typedef EdgeListS edge_list_selector;
 281
 282
 283     adjacency_list(const GraphProperty& p = GraphProperty())
 284       : m_property(new graph_property_type(p))
 285     { }
 286
 287     adjacency_list(const adjacency_list& x)
 288       : Base(x), m_property(new graph_property_type(*x.m_property))
 289     { }
 290
 291     adjacency_list& operator=(const adjacency_list& x) {
 292       // TBD: probably should give the strong guarantee
 293       if (&x != this) {
 294         Base::operator=(x);
 295
 296         // Copy/swap the ptr since we can't just assign it...
 297         property_ptr p(new graph_property_type(*x.m_property));
 298         m_property.swap(p);
 299       }
 300       return *this;
 301     }
 302
 303     // Required by Mutable Graph
 304     adjacency_list(vertices_size_type num_vertices,
 305                           const GraphProperty& p = GraphProperty())
 306       : Base(num_vertices), m_property(new graph_property_type(p))
 307     { }
 308
 309     // Required by Iterator Constructible Graph
 310     template <class EdgeIterator>
 311     adjacency_list(EdgeIterator first, EdgeIterator last,
 312                           vertices_size_type n,
 313                           edges_size_type = 0,
 314                           const GraphProperty& p = GraphProperty())
 315       : Base(n, first, last), m_property(new graph_property_type(p))
 316     { }
 317
 318     template <class EdgeIterator, class EdgePropertyIterator>
 319     adjacency_list(EdgeIterator first, EdgeIterator last,
 320                           EdgePropertyIterator ep_iter,
 321                           vertices_size_type n,
 322                           edges_size_type = 0,
 323                           const GraphProperty& p = GraphProperty())
 324       : Base(n, first, last, ep_iter), m_property(new graph_property_type(p))
 325     { }
 326
 327     void swap(adjacency_list& x) {
 328       // Is there a more efficient way to do this?
 329       adjacency_list tmp(x);
 330       x = *this;
 331       *this = tmp;
 332     }
 333
 334     void clear()
 335     {
 336       this->clearing_graph();
 337       Base::clear();
 338     }
 339
 340 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 341     // Directly access a vertex or edge bundle
 342     vertex_bundled& operator[](vertex_descriptor v)
 343     { return get(vertex_bundle, *this)[v]; }
 344
 345     const vertex_bundled& operator[](vertex_descriptor v) const
 346     { return get(vertex_bundle, *this)[v]; }
 347
 348     edge_bundled& operator[](edge_descriptor e)
 349     { return get(edge_bundle, *this)[e]; }
 350
 351     const edge_bundled& operator[](edge_descriptor e) const
 352     { return get(edge_bundle, *this)[e]; }
 353
 354     graph_bundled& operator[](graph_bundle_t)
 355     { return get_property(*this); }
 356
 357     graph_bundled const& operator[](graph_bundle_t) const
 358     { return get_property(*this); }
 359 #endif
 360
 361     //  protected:  (would be protected if friends were more portable)
 362     typedef scoped_ptr<graph_property_type> property_ptr;
 363     property_ptr  m_property;
 364   };
 365
 366 #define ADJLIST_PARAMS \
 367     typename OEL, typename VL, typename D, typename VP, typename EP, \
 368     typename GP, typename EL
 369 #define ADJLIST adjacency_list<OEL,VL,D,VP,EP,GP,EL>
 370
 371   template<ADJLIST_PARAMS, typename Tag, typename Value>
 372   inline void set_property(ADJLIST& g, Tag tag, Value const& value) {
 373     get_property_value(*g.m_property, tag) = value;
 374   }
 375
 376   template<ADJLIST_PARAMS, typename Tag>
 377   inline typename graph_property<ADJLIST, Tag>::type&
 378   get_property(ADJLIST& g, Tag tag) {
 379     return get_property_value(*g.m_property, tag);
 380   }
 381
 382   template<ADJLIST_PARAMS, typename Tag>
 383   inline typename graph_property<ADJLIST, Tag>::type const&
 384   get_property(ADJLIST const& g, Tag tag) {
 385     return get_property_value(*g.m_property, tag);
 386   }
 387
 388   // dwa 09/25/00 - needed to be more explicit so reverse_graph would work.
 389   template <class Directed, class Vertex,
 390       class OutEdgeListS,
 391       class VertexListS,
 392       class DirectedS,
 393       class VertexProperty,
 394       class EdgeProperty,
 395       class GraphProperty, class EdgeListS>
 396   inline Vertex
 397   source(const detail::edge_base<Directed,Vertex>& e,
 398          const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
 399                  VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
 400   {
 401     return e.m_source;
 402   }
 403
 404   template <class Directed, class Vertex, class OutEdgeListS,
 405       class VertexListS, class DirectedS, class VertexProperty,
 406       class EdgeProperty, class GraphProperty, class EdgeListS>
 407   inline Vertex
 408   target(const detail::edge_base<Directed,Vertex>& e,
 409          const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
 410               VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
 411   {
 412     return e.m_target;
 413   }
 414
 415 // Mutability Traits
 416 template <ADJLIST_PARAMS>
 417 struct graph_mutability_traits<ADJLIST> {
 418     typedef mutable_property_graph_tag category;
 419 };
 420
 421 // Can't remove vertices from adjacency lists with VL==vecS
 422 template <typename OEL, typename D, typename VP, typename EP, typename GP, typename EL>
 423 struct graph_mutability_traits< adjacency_list<OEL,vecS,D,VP,EP,GP,EL> > {
 424     typedef add_only_property_graph_tag category;
 425 };
 426 #undef ADJLIST_PARAMS
 427 #undef ADJLIST
 428
 429
 430 } // namespace boost
 431
 432
 433 #endif // BOOST_GRAPH_ADJACENCY_LIST_HPP