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 | |
47 | namespace 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 | |
248 | namespace 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 |
439 | template <ADJLIST_PARAMS> |
440 | struct graph_mutability_traits<ADJLIST> { |
441 | typedef mutable_property_graph_tag category; |
442 | }; |
443 | |
444 | // Can't remove vertices from adjacency lists with VL==vecS |
445 | template <typename OEL, typename D, typename VP, typename EP, typename GP, typename EL> |
446 | struct 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 | |