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 | |
38 | namespace 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 | |
47 | struct vecS |
48 | { |
49 | }; |
50 | struct listS |
51 | { |
52 | }; |
53 | struct setS |
54 | { |
55 | }; |
56 | struct mapS |
57 | { |
58 | }; |
59 | struct multisetS |
60 | { |
61 | }; |
62 | struct multimapS |
63 | { |
64 | }; |
65 | struct hash_setS |
66 | { |
67 | }; |
68 | struct hash_mapS |
69 | { |
70 | }; |
71 | struct hash_multisetS |
72 | { |
73 | }; |
74 | struct hash_multimapS |
75 | { |
76 | }; |
77 | |
78 | template < class Selector, class ValueType > struct container_gen |
79 | { |
80 | }; |
81 | |
82 | template < class ValueType > struct container_gen< listS, ValueType > |
83 | { |
84 | typedef std::list< ValueType > type; |
85 | }; |
86 | |
87 | template < class ValueType > struct container_gen< vecS, ValueType > |
88 | { |
89 | typedef std::vector< ValueType > type; |
90 | }; |
91 | |
92 | template < class ValueType > struct container_gen< mapS, ValueType > |
93 | { |
94 | typedef std::set< ValueType > type; |
95 | }; |
96 | |
97 | template < class ValueType > struct container_gen< setS, ValueType > |
98 | { |
99 | typedef std::set< ValueType > type; |
100 | }; |
101 | |
102 | template < class ValueType > struct container_gen< multisetS, ValueType > |
103 | { |
104 | typedef std::multiset< ValueType > type; |
105 | }; |
106 | |
107 | template < class ValueType > struct container_gen< multimapS, ValueType > |
108 | { |
109 | typedef std::multiset< ValueType > type; |
110 | }; |
111 | |
112 | template < class ValueType > struct container_gen< hash_setS, ValueType > |
113 | { |
114 | typedef boost::unordered_set< ValueType > type; |
115 | }; |
116 | |
117 | template < class ValueType > struct container_gen< hash_mapS, ValueType > |
118 | { |
119 | typedef boost::unordered_set< ValueType > type; |
120 | }; |
121 | |
122 | template < class ValueType > struct container_gen< hash_multisetS, ValueType > |
123 | { |
124 | typedef boost::unordered_multiset< ValueType > type; |
125 | }; |
126 | |
127 | template < class ValueType > struct container_gen< hash_multimapS, ValueType > |
128 | { |
129 | typedef boost::unordered_multiset< ValueType > type; |
130 | }; |
131 | |
132 | template < class StorageSelector > struct parallel_edge_traits |
133 | { |
134 | }; |
135 | |
136 | template <> struct parallel_edge_traits< vecS > |
137 | { |
138 | typedef allow_parallel_edge_tag type; |
139 | }; |
140 | |
141 | template <> struct parallel_edge_traits< listS > |
142 | { |
143 | typedef allow_parallel_edge_tag type; |
144 | }; |
145 | |
146 | template <> struct parallel_edge_traits< setS > |
147 | { |
148 | typedef disallow_parallel_edge_tag type; |
149 | }; |
150 | |
151 | template <> struct parallel_edge_traits< multisetS > |
152 | { |
153 | typedef allow_parallel_edge_tag type; |
154 | }; |
155 | |
156 | template <> struct parallel_edge_traits< hash_setS > |
157 | { |
158 | typedef disallow_parallel_edge_tag type; |
159 | }; |
160 | |
161 | // mapS is obsolete, replaced with setS |
162 | template <> struct parallel_edge_traits< mapS > |
163 | { |
164 | typedef disallow_parallel_edge_tag type; |
165 | }; |
166 | |
167 | template <> struct parallel_edge_traits< hash_mapS > |
168 | { |
169 | typedef disallow_parallel_edge_tag type; |
170 | }; |
171 | |
172 | template <> struct parallel_edge_traits< hash_multisetS > |
173 | { |
174 | typedef allow_parallel_edge_tag type; |
175 | }; |
176 | |
177 | template <> struct parallel_edge_traits< hash_multimapS > |
178 | { |
179 | typedef allow_parallel_edge_tag type; |
180 | }; |
181 | |
182 | namespace 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 | |
203 | template < 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 | |
214 | template < class OutEdgeListS = vecS, class VertexListS = vecS, |
215 | class DirectedS = directedS, class EdgeListS = listS > |
216 | struct 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 | |
237 | private: |
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 | |
248 | public: |
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 | |
257 | namespace boost |
258 | { |
259 | |
260 | //=========================================================================== |
261 | // The adjacency_list class. |
262 | // |
263 | |
264 | template < 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 > |
269 | class 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 | { |
283 | public: |
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 | |
297 | private: |
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 | |
303 | public: |
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 | |
416 | template < ADJLIST_PARAMS, typename Tag, typename Value > |
417 | inline void set_property(ADJLIST& g, Tag tag, Value const& value) |
418 | { |
419 | get_property_value(*g.m_property, tag) = value; |
420 | } |
421 | |
422 | template < ADJLIST_PARAMS, typename Tag > |
423 | inline 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 | |
429 | template < ADJLIST_PARAMS, typename Tag > |
430 | inline 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. |
437 | template < class Directed, class Vertex, class OutEdgeListS, class VertexListS, |
438 | class DirectedS, class VertexProperty, class EdgeProperty, |
439 | class GraphProperty, class EdgeListS > |
440 | inline 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 | |
447 | template < class Directed, class Vertex, class OutEdgeListS, class VertexListS, |
448 | class DirectedS, class VertexProperty, class EdgeProperty, |
449 | class GraphProperty, class EdgeListS > |
450 | inline 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 |
458 | template < 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 |
464 | template < typename OEL, typename D, typename VP, typename EP, typename GP, |
465 | typename EL > |
466 | struct 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 | |