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

source code of boost/boost/graph/adjacency_list.hpp