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