Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/boost/graph/adjacency_list.hpp @ 12

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

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