Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/boost/graph/adjacency_list.hpp @ 33

Last change on this file since 33 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 17.6 KB
Line 
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
45namespace 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
291namespace 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
Note: See TracBrowser for help on using the repository browser.