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 #if !defined BOOST_NO_HASH

    21 #  ifdef BOOST_HASH_SET_HEADER

    22 #    include BOOST_HASH_SET_HEADER

    23 #  else

    24 #    include <hash_set>

    25 #  endif

    26 #endif

    27 

    28 #if !defined BOOST_NO_SLIST

    29 #  ifdef BOOST_SLIST_HEADER

    30 #    include BOOST_SLIST_HEADER

    31 #  else

    32 #    include <slist>

    33 #  endif

    34 #endif

    35 

    36 #include <boost/graph/graph_traits.hpp>

    37 #include <boost/graph/graph_selectors.hpp>

    38 #include <boost/property_map.hpp>

    39 #include <boost/pending/ct_if.hpp>

    40 #include <boost/graph/detail/edge.hpp>

    41 #include <boost/type_traits/is_same.hpp>

    42 #include <boost/detail/workaround.hpp>

    43 #include <boost/graph/properties.hpp>

    44 

    45 namespace boost {

    46 

    47   //===========================================================================

    48   // Selectors for the VertexList and EdgeList template parameters of

    49   // adjacency_list, and the container_gen traits class which is used

    50   // to map the selectors to the container type used to implement the

    51   // graph.

    52   //

    53   // The main container_gen traits class uses partial specialization,

    54   // so we also include a workaround.

    55 

    56 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    57 

    58 #if !defined BOOST_NO_SLIST

    59   struct slistS {};  

    60 #endif

    61 

    62   struct vecS  { };

    63   struct listS { };

    64   struct setS { };

    65   struct multisetS { };

    66   struct mapS  { };

    67 #if !defined BOOST_NO_HASH

    68   struct hash_mapS { };

    69   struct hash_setS { };

    70 #endif

    71 

    72   template <class Selector, class ValueType>

    73   struct container_gen { };

    74 

    75   template <class ValueType>

    76   struct container_gen<listS, ValueType> {

    77     typedef std::list<ValueType> type;

    78   };

    79 #if !defined BOOST_NO_SLIST

    80   template <class ValueType>

    81   struct container_gen<slistS, ValueType> {

    82     typedef BOOST_STD_EXTENSION_NAMESPACE::slist<ValueType> type;

    83   };

    84 #endif

    85   template <class ValueType>

    86   struct container_gen<vecS, ValueType> {

    87     typedef std::vector<ValueType> type;

    88   };

    89 

    90   template <class ValueType>

    91   struct container_gen<mapS, ValueType> {

    92     typedef std::set<ValueType> type;

    93   };

    94 

    95   template <class ValueType>

    96   struct container_gen<setS, ValueType> {

    97     typedef std::set<ValueType> type;

    98   };

    99 

   100   template <class ValueType>

   101   struct container_gen<multisetS, ValueType> {

   102     typedef std::multiset<ValueType> type;

   103   };

   104 

   105 #if !defined BOOST_NO_HASH

   106   template <class ValueType>

   107   struct container_gen<hash_mapS, ValueType> {

   108     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;

   109   };

   110 

   111   template <class ValueType>

   112   struct container_gen<hash_setS, ValueType> {

   113     typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;

   114   };

   115 #endif

   116 

   117 #else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   118 

   119 #if !defined BOOST_NO_SLIST

   120   struct slistS {

   121     template <class T>

   122     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::slist<T> type; };

   123   };

   124 #endif

   125 

   126   struct vecS  {

   127     template <class T>

   128     struct bind_ { typedef std::vector<T> type; };

   129   };

   130 

   131   struct listS { 

   132     template <class T>

   133     struct bind_ { typedef std::list<T> type; };

   134   };

   135 

   136   struct setS  { 

   137     template <class T>

   138     struct bind_ { typedef std::set<T, std::less<T> > type; };

   139   };

   140 

   141   struct multisetS  { 

   142     template <class T>

   143     struct bind_ { typedef std::multiset<T, std::less<T> > type; };

   144   };

   145 

   146 #if !defined BOOST_NO_HASH

   147   struct hash_setS { 

   148     template <class T>

   149     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };

   150   };

   151 #endif

   152 

   153   struct mapS  { 

   154     template <class T>

   155     struct bind_ { typedef std::set<T, std::less<T> > type; };

   156   };

   157 

   158 #if !defined BOOST_NO_HASH

   159   struct hash_mapS { 

   160     template <class T>

   161     struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };

   162   };

   163 #endif

   164 

   165   template <class Selector> struct container_selector {

   166     typedef vecS type;

   167   };

   168 

   169 #define BOOST_CONTAINER_SELECTOR(NAME) \

   170   template <> struct container_selector<NAME>  { \

   171     typedef NAME type; \

   172   }

   173 

   174   BOOST_CONTAINER_SELECTOR(vecS);

   175   BOOST_CONTAINER_SELECTOR(listS);

   176   BOOST_CONTAINER_SELECTOR(mapS);

   177   BOOST_CONTAINER_SELECTOR(setS);

   178   BOOST_CONTAINER_SELECTOR(multisetS);

   179 #if !defined BOOST_NO_HASH

   180   BOOST_CONTAINER_SELECTOR(hash_mapS);

   181 #endif

   182 #if !defined BOOST_NO_SLIST

   183   BOOST_CONTAINER_SELECTOR(slistS);

   184 #endif

   185 

   186   template <class Selector, class ValueType>

   187   struct container_gen {

   188     typedef typename container_selector<Selector>::type Select;

   189     typedef typename Select:: template bind_<ValueType>::type type;

   190   };

   191 

   192 #endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   193 

   194   template <class StorageSelector>

   195   struct parallel_edge_traits { };

   196 

   197   template <>

   198   struct parallel_edge_traits<vecS> { 

   199     typedef allow_parallel_edge_tag type; };

   200 

   201   template <>

   202   struct parallel_edge_traits<listS> { 

   203     typedef allow_parallel_edge_tag type; };

   204 

   205 #if !defined BOOST_NO_SLIST

   206   template <>

   207   struct parallel_edge_traits<slistS> { 

   208     typedef allow_parallel_edge_tag type; };

   209 #endif

   210 

   211   template <>

   212   struct parallel_edge_traits<setS> { 

   213     typedef disallow_parallel_edge_tag type; };

   214 

   215   template <>

   216   struct parallel_edge_traits<multisetS> { 

   217     typedef allow_parallel_edge_tag type; };

   218 

   219 #if !defined BOOST_NO_HASH

   220   template <>

   221   struct parallel_edge_traits<hash_setS> {

   222     typedef disallow_parallel_edge_tag type; 

   223   };

   224 #endif

   225 

   226   // mapS is obsolete, replaced with setS

   227   template <>

   228   struct parallel_edge_traits<mapS> { 

   229     typedef disallow_parallel_edge_tag type; };

   230 

   231 #if !defined BOOST_NO_HASH

   232   template <>

   233   struct parallel_edge_traits<hash_mapS> {

   234     typedef disallow_parallel_edge_tag type; 

   235   };

   236 #endif

   237 

   238   namespace detail {

   239     template <class Directed> struct is_random_access { 

   240       enum { value = false};

   241       typedef false_type type;

   242     };

   243     template <>

   244     struct is_random_access<vecS> { 

   245       enum { value = true }; 

   246       typedef true_type type;

   247     };

   248 

   249   } // namespace detail

   250 

   251 

   252 

   253   //===========================================================================

   254   // The adjacency_list_traits class, which provides a way to access

   255   // some of the associated types of an adjacency_list type without

   256   // having to first create the adjacency_list type. This is useful

   257   // when trying to create interior vertex or edge properties who's

   258   // value type is a vertex or edge descriptor.

   259 

   260   template <class OutEdgeListS = vecS,

   261             class VertexListS = vecS,

   262             class DirectedS = directedS>

   263   struct adjacency_list_traits

   264   {

   265     typedef typename detail::is_random_access<VertexListS>::type

   266       is_rand_access;

   267     typedef typename DirectedS::is_bidir_t is_bidir;

   268     typedef typename DirectedS::is_directed_t is_directed;

   269 

   270     typedef typename boost::ct_if_t<is_bidir,

   271       bidirectional_tag,

   272       typename boost::ct_if_t<is_directed,

   273         directed_tag, undirected_tag

   274       >::type

   275     >::type directed_category;

   276 

   277     typedef typename parallel_edge_traits<OutEdgeListS>::type

   278       edge_parallel_category;

   279 

   280     typedef void* vertex_ptr;

   281     typedef typename boost::ct_if_t<is_rand_access,

   282       std::size_t, vertex_ptr>::type vertex_descriptor;

   283     typedef detail::edge_desc_impl<directed_category, vertex_descriptor>

   284       edge_descriptor;

   285   };

   286 

   287 } // namespace boost

   288 

   289 #include <boost/graph/detail/adjacency_list.hpp>

   290 

   291 namespace boost {

   292 

   293   //===========================================================================

   294   // The adjacency_list class.

   295   //

   296 

   297   template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer

   298             class VertexListS = vecS, // a Sequence or a RandomAccessContainer

   299             class DirectedS = directedS,

   300             class VertexProperty = no_property,

   301             class EdgeProperty = no_property,

   302             class GraphProperty = no_property,

   303             class EdgeListS = listS>

   304   class adjacency_list

   305     : public detail::adj_list_gen<

   306       adjacency_list<OutEdgeListS,VertexListS,DirectedS,

   307                      VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,

   308       VertexListS, OutEdgeListS, DirectedS, 

   309 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)

   310       typename detail::retag_property_list<vertex_bundle_t,

   311                                            VertexProperty>::type,

   312       typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type,

   313 #else

   314       VertexProperty, EdgeProperty,

   315 #endif

   316       GraphProperty, EdgeListS>::type

   317   {

   318 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)

   319     typedef typename detail::retag_property_list<vertex_bundle_t,

   320                                                  VertexProperty>::retagged

   321       maybe_vertex_bundled;

   322 

   323      typedef typename detail::retag_property_list<edge_bundle_t,

   324                                                   EdgeProperty>::retagged

   325       maybe_edge_bundled;

   326 #endif

   327 

   328   public:

   329 #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)

   330     typedef typename detail::retag_property_list<vertex_bundle_t,

   331                                                  VertexProperty>::type

   332       vertex_property_type;

   333     typedef typename detail::retag_property_list<edge_bundle_t,

   334                                                  EdgeProperty>::type

   335       edge_property_type;

   336 

   337     // The types that are actually bundled

   338     typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),

   339                            no_vertex_bundle,

   340                            maybe_vertex_bundled>::type vertex_bundled;

   341     typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),

   342                            no_edge_bundle,

   343                            maybe_edge_bundled>::type edge_bundled;

   344 #else

   345     typedef VertexProperty vertex_property_type;

   346     typedef EdgeProperty edge_property_type;

   347     typedef no_vertex_bundle vertex_bundled;

   348     typedef no_edge_bundle edge_bundled;

   349 #endif

   350 

   351   private:

   352     typedef adjacency_list self;

   353     typedef typename detail::adj_list_gen<

   354       self, VertexListS, OutEdgeListS, DirectedS, 

   355       vertex_property_type, edge_property_type, GraphProperty, EdgeListS

   356     >::type Base;

   357 

   358   public:

   359     typedef typename Base::stored_vertex stored_vertex;

   360     typedef typename Base::vertices_size_type vertices_size_type;

   361     typedef typename Base::edges_size_type edges_size_type;

   362     typedef typename Base::degree_size_type degree_size_type;

   363     typedef typename Base::vertex_descriptor vertex_descriptor;

   364     typedef typename Base::edge_descriptor edge_descriptor;

   365     typedef OutEdgeListS out_edge_list_selector;

   366     typedef VertexListS vertex_list_selector;

   367     typedef DirectedS directed_selector;

   368     typedef EdgeListS edge_list_selector;

   369 

   370     typedef GraphProperty graph_property_type;

   371 

   372     inline adjacency_list(const GraphProperty& p = GraphProperty()) 

   373       : m_property(p) { }

   374 

   375     inline adjacency_list(const adjacency_list& x)

   376       : Base(x), m_property(x.m_property) { }

   377 

   378     inline adjacency_list& operator=(const adjacency_list& x) {

   379       // TBD: probably should give the strong guarantee

   380       if (&x != this) {

   381         Base::operator=(x);

   382         m_property = x.m_property;

   383       }

   384       return *this;

   385     }

   386 

   387     // Required by Mutable Graph

   388     inline adjacency_list(vertices_size_type num_vertices, 

   389                           const GraphProperty& p = GraphProperty())

   390       : Base(num_vertices), m_property(p) { }

   391 

   392 #if !defined(BOOST_MSVC) || BOOST_MSVC >= 1300

   393     // Required by Iterator Constructible Graph

   394     template <class EdgeIterator>

   395     inline adjacency_list(EdgeIterator first, EdgeIterator last,

   396                           vertices_size_type n,

   397                           edges_size_type = 0,

   398                           const GraphProperty& p = GraphProperty())

   399       : Base(n, first, last), m_property(p) { }

   400 

   401     template <class EdgeIterator, class EdgePropertyIterator>

   402     inline adjacency_list(EdgeIterator first, EdgeIterator last,

   403                           EdgePropertyIterator ep_iter,

   404                           vertices_size_type n,

   405                           edges_size_type = 0,

   406                           const GraphProperty& p = GraphProperty())

   407       : Base(n, first, last, ep_iter), m_property(p) { }

   408 #endif

   409 

   410     void swap(adjacency_list& x) {

   411       // Is there a more efficient way to do this?

   412       adjacency_list tmp(x);

   413       x = *this;

   414       *this = tmp;

   415     }

   416 

   417 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   418     // Directly access a vertex or edge bundle

   419     vertex_bundled& operator[](vertex_descriptor v)

   420     { return get(vertex_bundle, *this)[v]; }

   421 

   422     const vertex_bundled& operator[](vertex_descriptor v) const

   423     { return get(vertex_bundle, *this)[v]; }

   424 

   425     edge_bundled& operator[](edge_descriptor e)

   426     { return get(edge_bundle, *this)[e]; }

   427 

   428     const edge_bundled& operator[](edge_descriptor e) const

   429     { return get(edge_bundle, *this)[e]; }

   430 #endif

   431 

   432     //  protected:  (would be protected if friends were more portable)

   433     GraphProperty m_property;

   434   };

   435 

   436   template <class OEL, class VL, class DirS, class VP,class EP, class GP,

   437             class EL, class Tag, class Value>

   438   inline void

   439   set_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag,

   440                const Value& value) {

   441     get_property_value(g.m_property, Tag()) = value;;

   442   }

   443 

   444   template <class OEL, class VL, class DirS, class VP, class EP, class GP,

   445             class Tag, class EL>

   446   inline

   447   typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&

   448   get_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {

   449     return get_property_value(g.m_property, Tag());

   450   }

   451 

   452   template <class OEL, class VL, class DirS, class VP, class EP, class GP,

   453             class Tag, class EL>

   454   inline

   455   const

   456   typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&

   457   get_property(const adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {

   458     return get_property_value(g.m_property, Tag());

   459   }

   460 

   461   // dwa 09/25/00 - needed to be more explicit so reverse_graph would work.

   462   template <class Directed, class Vertex,

   463       class OutEdgeListS,

   464       class VertexListS,

   465       class DirectedS,

   466       class VertexProperty,

   467       class EdgeProperty,

   468       class GraphProperty, class EdgeListS>

   469   inline Vertex

   470   source(const detail::edge_base<Directed,Vertex>& e,

   471          const adjacency_list<OutEdgeListS, VertexListS, DirectedS,

   472                  VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)

   473   {

   474     return e.m_source;

   475   }

   476 

   477   template <class Directed, class Vertex, class OutEdgeListS,

   478       class VertexListS, class DirectedS, class VertexProperty,

   479       class EdgeProperty, class GraphProperty, class EdgeListS>

   480   inline Vertex

   481   target(const detail::edge_base<Directed,Vertex>& e,

   482          const adjacency_list<OutEdgeListS, VertexListS, DirectedS,

   483               VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)

   484   {

   485     return e.m_target;

   486   }

   487 

   488   // Support for bundled properties

   489 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   490   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,

   491            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>

   492   inline

   493   typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,

   494                                        GraphProperty, EdgeListS>, T Bundle::*>::type

   495   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,

   496                                     GraphProperty, EdgeListS>& g)

   497   {

   498     typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, 

   499                                                  EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::type

   500       result_type;

   501     return result_type(&g, p);

   502   }

   503   

   504   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,

   505            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>

   506   inline

   507   typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,

   508                                        GraphProperty, EdgeListS>, T Bundle::*>::const_type

   509   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,

   510                                     GraphProperty, EdgeListS> const & g)

   511   {

   512     typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, 

   513                                                  EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::const_type

   514       result_type;

   515     return result_type(&g, p);

   516   }

   517 

   518   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,

   519            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,

   520            typename Key>

   521   inline T

   522   get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,

   523                                     GraphProperty, EdgeListS> const & g, const Key& key)

   524   {

   525     return get(get(p, g), key);

   526   }

   527 

   528   template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,

   529            typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,

   530            typename Key>

   531   inline void

   532   put(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,

   533                                     GraphProperty, EdgeListS>& g, const Key& key, const T& value)

   534   {

   535     put(get(p, g), key, value);

   536   }

   537 

   538 #endif

   539 

   540 

   541 } // namespace boost

   542 

   543 

   544 #endif // BOOST_GRAPH_ADJACENCY_LIST_HPP