boost/graph/adjacency_list.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   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_ADJACENCY_LIST_HPP
  11 #define BOOST_GRAPH_ADJACENCY_LIST_HPP
  12
  13
  14 #include <boost/config.hpp>
  15
  16 #include <vector>
  17 #include <list>
  18 #include <set>
  19
  20 // TODO: Deprecating this requires some cooperation from Boost.Config. It's not
  21 // a good idea to just refuse the inclusion because it could break otherwise
  22 // functioning code.
  23 #if !defined BOOST_NO_HASH
  24 #  ifdef BOOST_HASH_SET_HEADER
  25 #    include BOOST_HASH_SET_HEADER
  26 #  else
  27 #    include <hash_set>
  28 #  endif
  29 #endif
  30
  31 #if !defined BOOST_NO_SLIST
  32 #  ifdef BOOST_SLIST_HEADER
  33 #    include BOOST_SLIST_HEADER
  34 #  else
  35 #    include <slist>
  36 #  endif
  37 #endif
  38
  39 #include <boost/graph/graph_traits.hpp>
  40 #include <boost/graph/graph_selectors.hpp>
  41 #include <boost/property_map/property_map.hpp>
  42 #include <boost/mpl/if.hpp>
  43 #include <boost/mpl/and.hpp>
  44 #include <boost/mpl/not.hpp>
  45 #include <boost/mpl/bool.hpp>
  46 #include <boost/graph/detail/edge.hpp>
  47 #include <boost/type_traits/is_same.hpp>
  48 #include <boost/detail/workaround.hpp>
  49 #include <boost/graph/properties.hpp>
  50 #include <boost/graph/named_graph.hpp>
  51
  52 namespace boost {
  53
  54   //===========================================================================
  55   // Selectors for the VertexList and EdgeList template parameters of
  56   // adjacency_list, and the container_gen traits class which is used
  57   // to map the selectors to the container type used to implement the
  58   // graph.
  59   //
  60   // The main container_gen traits class uses partial specialization,
  61   // so we also include a workaround.
  62
  63 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  64
  65 #if !defined BOOST_NO_SLIST
  66   struct slistS {};
  67 #endif
  68
  69   struct vecS  { };
  70   struct listS { };
  71   struct setS { };
  72   struct mapS  { };
  73   struct multisetS { };
  74   struct multimapS { };
  75 #if !defined BOOST_NO_HASH
  76   struct hash_setS { };
  77   struct hash_mapS { };
  78   struct hash_multisetS { };
  79   struct hash_multimapS { };
  80 #endif
  81
  82   template <class Selector, class ValueType>
  83   struct container_gen { };
  84
  85   template <class ValueType>
  86   struct container_gen<listS, ValueType> {
  87     typedef std::list<ValueType> type;
  88   };
  89 #if !defined BOOST_NO_SLIST
  90   template <class ValueType>
  91   struct container_gen<slistS, ValueType> {
  92     typedef BOOST_STD_EXTENSION_NAMESPACE::slist<ValueType> type;
  93   };
  94 #endif
  95   template <class ValueType>
  96   struct container_gen<vecS, ValueType> {
  97     typedef std::vector<ValueType> type;
  98   };
  99
 100   template <class ValueType>
 101   struct container_gen<mapS, ValueType> {
 102     typedef std::set<ValueType> type;
 103   };
 104
 105   template <class ValueType>
 106   struct container_gen<setS, ValueType> {
 107     typedef std::set<ValueType> type;
 108   };
 109
 110   template <class ValueType>
 111   struct container_gen<multisetS, ValueType> {
 112     typedef std::multiset<ValueType> type;
 113   };
 114
 115   template <class ValueType>
 116   struct container_gen<multimapS, ValueType> {
 117     typedef std::multiset<ValueType> type;
 118   };
 119
 120 #if !defined BOOST_NO_HASH
 121   template <class ValueType>
 122   struct container_gen<hash_setS, ValueType> {
 123     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
 124   };
 125
 126   template <class ValueType>
 127   struct container_gen<hash_mapS, ValueType> {
 128     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
 129   };
 130
 131   template <class ValueType>
 132   struct container_gen<hash_multisetS, ValueType> {
 133     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<ValueType> type;
 134   };
 135
 136   template <class ValueType>
 137   struct container_gen<hash_multimapS, ValueType> {
 138     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<ValueType> type;
 139   };
 140 #endif
 141
 142 #else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 143
 144 #if !defined BOOST_NO_SLIST
 145   struct slistS {
 146     template <class T>
 147     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::slist<T> type; };
 148   };
 149 #endif
 150
 151   struct vecS  {
 152     template <class T>
 153     struct bind_ { typedef std::vector<T> type; };
 154   };
 155
 156   struct listS {
 157     template <class T>
 158     struct bind_ { typedef std::list<T> type; };
 159   };
 160
 161   struct setS  {
 162     template <class T>
 163     struct bind_ { typedef std::set<T, std::less<T> > type; };
 164   };
 165
 166
 167   struct mapS  {
 168     template <class T>
 169     struct bind_ { typedef std::set<T, std::less<T> > type; };
 170   };
 171
 172   struct multisetS  {
 173     template <class T>
 174     struct bind_ { typedef std::multiset<T, std::less<T> > type; };
 175   };
 176
 177   struct multimapS  {
 178     template <class T>
 179     struct bind_ { typedef std::multiset<T, std::less<T> > type; };
 180   };
 181
 182 #if !defined BOOST_NO_HASH
 183   struct hash_setS {
 184     template <class T>
 185     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
 186   };
 187
 188   struct hash_mapS {
 189     template <class T>
 190     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
 191   };
 192
 193   struct hash_multisetS {
 194     template <class T>
 195     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<T, std::less<T> > type; };
 196   };
 197
 198   struct hash_multimapS {
 199     template <class T>
 200     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_multiset<T, std::less<T> > type; };
 201   };
 202 #endif
 203
 204   template <class Selector> struct container_selector {
 205     typedef vecS type;
 206   };
 207
 208 #define BOOST_CONTAINER_SELECTOR(NAME) \
 209   template <> struct container_selector<NAME>  { \
 210     typedef NAME type; \
 211   }
 212
 213   BOOST_CONTAINER_SELECTOR(vecS);
 214   BOOST_CONTAINER_SELECTOR(listS);
 215   BOOST_CONTAINER_SELECTOR(mapS);
 216   BOOST_CONTAINER_SELECTOR(setS);
 217   BOOST_CONTAINER_SELECTOR(multisetS);
 218 #if !defined BOOST_NO_HASH
 219   BOOST_CONTAINER_SELECTOR(hash_mapS);
 220 #endif
 221 #if !defined BOOST_NO_SLIST
 222   BOOST_CONTAINER_SELECTOR(slistS);
 223 #endif
 224
 225   template <class Selector, class ValueType>
 226   struct container_gen {
 227     typedef typename container_selector<Selector>::type Select;
 228     typedef typename Select:: template bind_<ValueType>::type type;
 229   };
 230
 231 #endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 232
 233   template <class StorageSelector>
 234   struct parallel_edge_traits { };
 235
 236   template <>
 237   struct parallel_edge_traits<vecS> {
 238     typedef allow_parallel_edge_tag type; };
 239
 240   template <>
 241   struct parallel_edge_traits<listS> {
 242     typedef allow_parallel_edge_tag type; };
 243
 244 #if !defined BOOST_NO_SLIST
 245   template <>
 246   struct parallel_edge_traits<slistS> {
 247     typedef allow_parallel_edge_tag type; };
 248 #endif
 249
 250   template <>
 251   struct parallel_edge_traits<setS> {
 252     typedef disallow_parallel_edge_tag type; };
 253
 254   template <>
 255   struct parallel_edge_traits<multisetS> {
 256     typedef allow_parallel_edge_tag type; };
 257
 258 #if !defined BOOST_NO_HASH
 259   template <>
 260   struct parallel_edge_traits<hash_setS> {
 261     typedef disallow_parallel_edge_tag type;
 262   };
 263 #endif
 264
 265   // mapS is obsolete, replaced with setS
 266   template <>
 267   struct parallel_edge_traits<mapS> {
 268     typedef disallow_parallel_edge_tag type; };
 269
 270 #if !defined BOOST_NO_HASH
 271   template <>
 272   struct parallel_edge_traits<hash_mapS> {
 273     typedef disallow_parallel_edge_tag type;
 274   };
 275 #endif
 276
 277   namespace detail {
 278     template <class Directed> struct is_random_access {
 279       enum { value = false};
 280       typedef mpl::false_ type;
 281     };
 282     template <>
 283     struct is_random_access<vecS> {
 284       enum { value = true };
 285       typedef mpl::true_ type;
 286     };
 287
 288   } // namespace detail
 289
 290
 291
 292   //===========================================================================
 293   // The adjacency_list_traits class, which provides a way to access
 294   // some of the associated types of an adjacency_list type without
 295   // having to first create the adjacency_list type. This is useful
 296   // when trying to create interior vertex or edge properties who's
 297   // value type is a vertex or edge descriptor.
 298
 299   template <class OutEdgeListS = vecS,
 300             class VertexListS = vecS,
 301             class DirectedS = directedS,
 302             class EdgeListS = listS>
 303   struct adjacency_list_traits
 304   {
 305     typedef typename detail::is_random_access<VertexListS>::type
 306       is_rand_access;
 307     typedef typename DirectedS::is_bidir_t is_bidir;
 308     typedef typename DirectedS::is_directed_t is_directed;
 309
 310     typedef typename mpl::if_<is_bidir,
 311       bidirectional_tag,
 312       typename mpl::if_<is_directed,
 313         directed_tag, undirected_tag
 314       >::type
 315     >::type directed_category;
 316
 317     typedef typename parallel_edge_traits<OutEdgeListS>::type
 318       edge_parallel_category;
 319
 320     typedef std::size_t vertices_size_type;
 321     typedef void* vertex_ptr;
 322     typedef typename mpl::if_<is_rand_access,
 323       vertices_size_type, vertex_ptr>::type vertex_descriptor;
 324     typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
 325       edge_descriptor;
 326
 327   private:
 328     // Logic to figure out the edges_size_type
 329     struct dummy {};
 330     typedef typename container_gen<EdgeListS, dummy>::type EdgeContainer;
 331     typedef typename DirectedS::is_bidir_t BidirectionalT;
 332     typedef typename DirectedS::is_directed_t DirectedT;
 333     typedef typename mpl::and_<DirectedT,
 334       typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
 335   public:
 336     typedef typename mpl::if_<on_edge_storage,
 337        std::size_t, typename EdgeContainer::size_type
 338     >::type edges_size_type;
 339
 340   };
 341
 342 } // namespace boost
 343
 344 #include <boost/graph/detail/adjacency_list.hpp>
 345
 346 namespace boost {
 347
 348   //===========================================================================
 349   // The adjacency_list class.
 350   //
 351
 352   template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer
 353             class VertexListS = vecS, // a Sequence or a RandomAccessContainer
 354             class DirectedS = directedS,
 355             class VertexProperty = no_property,
 356             class EdgeProperty = no_property,
 357             class GraphProperty = no_property,
 358             class EdgeListS = listS>
 359   class adjacency_list
 360     : public detail::adj_list_gen<
 361       adjacency_list<OutEdgeListS,VertexListS,DirectedS,
 362                      VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
 363       VertexListS, OutEdgeListS, DirectedS,
 364 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
 365       typename detail::retag_property_list<vertex_bundle_t,
 366                                            VertexProperty>::type,
 367       typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type,
 368 #else
 369       VertexProperty, EdgeProperty,
 370 #endif
 371       GraphProperty, EdgeListS>::type,
 372       // Support for named vertices
 373       public graph::maybe_named_graph<
 374         adjacency_list<OutEdgeListS,VertexListS,DirectedS,
 375                        VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
 376         typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS,
 377                                        EdgeListS>::vertex_descriptor,
 378         VertexProperty>
 379   {
 380       public: // TODO Remove me
 381 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
 382     typedef typename detail::retag_property_list<vertex_bundle_t,
 383                                                  VertexProperty>::retagged
 384       maybe_vertex_bundled;
 385
 386      typedef typename detail::retag_property_list<edge_bundle_t,
 387                                                   EdgeProperty>::retagged
 388       maybe_edge_bundled;
 389 #endif
 390
 391   public:
 392 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
 393     typedef typename detail::retag_property_list<vertex_bundle_t,
 394                                                  VertexProperty>::type
 395       vertex_property_type;
 396     typedef typename detail::retag_property_list<edge_bundle_t,
 397                                                  EdgeProperty>::type
 398       edge_property_type;
 399
 400     // The types that are actually bundled
 401     typedef typename mpl::if_c<(is_same<maybe_vertex_bundled, no_property>::value),
 402                            no_vertex_bundle,
 403                            maybe_vertex_bundled>::type vertex_bundled;
 404     typedef typename mpl::if_c<(is_same<maybe_edge_bundled, no_property>::value),
 405                            no_edge_bundle,
 406                            maybe_edge_bundled>::type edge_bundled;
 407 #else
 408     typedef VertexProperty vertex_property_type;
 409     typedef EdgeProperty edge_property_type;
 410     typedef no_vertex_bundle vertex_bundled;
 411     typedef no_edge_bundle edge_bundled;
 412 #endif
 413
 414   private:
 415     typedef adjacency_list self;
 416     typedef typename detail::adj_list_gen<
 417       self, VertexListS, OutEdgeListS, DirectedS,
 418       vertex_property_type, edge_property_type, GraphProperty, EdgeListS
 419     >::type Base;
 420
 421   public:
 422     typedef typename Base::stored_vertex stored_vertex;
 423     typedef typename Base::vertices_size_type vertices_size_type;
 424     typedef typename Base::edges_size_type edges_size_type;
 425     typedef typename Base::degree_size_type degree_size_type;
 426     typedef typename Base::vertex_descriptor vertex_descriptor;
 427     typedef typename Base::edge_descriptor edge_descriptor;
 428     typedef OutEdgeListS out_edge_list_selector;
 429     typedef VertexListS vertex_list_selector;
 430     typedef DirectedS directed_selector;
 431     typedef EdgeListS edge_list_selector;
 432
 433     typedef GraphProperty graph_property_type;
 434
 435     inline adjacency_list(const GraphProperty& p = GraphProperty())
 436       : m_property(p) { }
 437
 438     inline adjacency_list(const adjacency_list& x)
 439       : Base(x), m_property(x.m_property) { }
 440
 441     inline adjacency_list& operator=(const adjacency_list& x) {
 442       // TBD: probably should give the strong guarantee
 443       if (&x != this) {
 444         Base::operator=(x);
 445         m_property = x.m_property;
 446       }
 447       return *this;
 448     }
 449
 450     // Required by Mutable Graph
 451     inline adjacency_list(vertices_size_type num_vertices,
 452                           const GraphProperty& p = GraphProperty())
 453       : Base(num_vertices), m_property(p) { }
 454
 455 #if !defined(BOOST_MSVC) || BOOST_MSVC >= 1300
 456     // Required by Iterator Constructible Graph
 457     template <class EdgeIterator>
 458     inline adjacency_list(EdgeIterator first, EdgeIterator last,
 459                           vertices_size_type n,
 460                           edges_size_type = 0,
 461                           const GraphProperty& p = GraphProperty())
 462       : Base(n, first, last), m_property(p) { }
 463
 464     template <class EdgeIterator, class EdgePropertyIterator>
 465     inline adjacency_list(EdgeIterator first, EdgeIterator last,
 466                           EdgePropertyIterator ep_iter,
 467                           vertices_size_type n,
 468                           edges_size_type = 0,
 469                           const GraphProperty& p = GraphProperty())
 470       : Base(n, first, last, ep_iter), m_property(p) { }
 471 #endif
 472
 473     void swap(adjacency_list& x) {
 474       // Is there a more efficient way to do this?
 475       adjacency_list tmp(x);
 476       x = *this;
 477       *this = tmp;
 478     }
 479
 480     void clear()
 481     {
 482       this->clearing_graph();
 483       Base::clear();
 484     }
 485
 486 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 487     // Directly access a vertex or edge bundle
 488     vertex_bundled& operator[](vertex_descriptor v)
 489     { return get(vertex_bundle, *this)[v]; }
 490
 491     const vertex_bundled& operator[](vertex_descriptor v) const
 492     { return get(vertex_bundle, *this)[v]; }
 493
 494     edge_bundled& operator[](edge_descriptor e)
 495     { return get(edge_bundle, *this)[e]; }
 496
 497     const edge_bundled& operator[](edge_descriptor e) const
 498     { return get(edge_bundle, *this)[e]; }
 499 #endif
 500
 501     //  protected:  (would be protected if friends were more portable)
 502     GraphProperty m_property;
 503   };
 504
 505   template <class OEL, class VL, class DirS, class VP,class EP, class GP,
 506             class EL, class Tag, class Value>
 507   inline void
 508   set_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag,
 509                const Value& value) {
 510     get_property_value(g.m_property, Tag()) = value;;
 511   }
 512
 513   template <class OEL, class VL, class DirS, class VP, class EP, class GP,
 514             class Tag, class EL>
 515   inline
 516   typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
 517   get_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
 518     return get_property_value(g.m_property, Tag());
 519   }
 520
 521   template <class OEL, class VL, class DirS, class VP, class EP, class GP,
 522             class Tag, class EL>
 523   inline
 524   const
 525   typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
 526   get_property(const adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
 527     return get_property_value(g.m_property, Tag());
 528   }
 529
 530   // dwa 09/25/00 - needed to be more explicit so reverse_graph would work.
 531   template <class Directed, class Vertex,
 532       class OutEdgeListS,
 533       class VertexListS,
 534       class DirectedS,
 535       class VertexProperty,
 536       class EdgeProperty,
 537       class GraphProperty, class EdgeListS>
 538   inline Vertex
 539   source(const detail::edge_base<Directed,Vertex>& e,
 540          const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
 541                  VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
 542   {
 543     return e.m_source;
 544   }
 545
 546   template <class Directed, class Vertex, class OutEdgeListS,
 547       class VertexListS, class DirectedS, class VertexProperty,
 548       class EdgeProperty, class GraphProperty, class EdgeListS>
 549   inline Vertex
 550   target(const detail::edge_base<Directed,Vertex>& e,
 551          const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
 552               VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
 553   {
 554     return e.m_target;
 555   }
 556
 557   // Support for bundled properties
 558 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 559   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
 560            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
 561   inline
 562   typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
 563                                        GraphProperty, EdgeListS>, T Bundle::*>::type
 564   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
 565                                     GraphProperty, EdgeListS>& g)
 566   {
 567     typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
 568                                                  EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::type
 569       result_type;
 570     return result_type(&g, p);
 571   }
 572
 573   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
 574            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
 575   inline
 576   typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
 577                                        GraphProperty, EdgeListS>, T Bundle::*>::const_type
 578   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
 579                                     GraphProperty, EdgeListS> const & g)
 580   {
 581     typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
 582                                                  EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::const_type
 583       result_type;
 584     return result_type(&g, p);
 585   }
 586
 587   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
 588            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
 589            typename Key>
 590   inline T
 591   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
 592                                     GraphProperty, EdgeListS> const & g, const Key& key)
 593   {
 594     return get(get(p, g), key);
 595   }
 596
 597   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
 598            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
 599            typename Key>
 600   inline void
 601   put(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
 602                                     GraphProperty, EdgeListS>& g, const Key& key, const T& value)
 603   {
 604     put(get(p, g), key, value);
 605   }
 606
 607 #endif
 608
 609
 610 } // namespace boost
 611
 612
 613 #endif // BOOST_GRAPH_ADJACENCY_LIST_HPP