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