Line data Source code
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 0 : adjacency_list(const GraphProperty& p = GraphProperty())
284 0 : : m_property(new graph_property_type(p))
285 0 : { }
286 :
287 : adjacency_list(const adjacency_list& x)
288 : : Base(x), m_property(new graph_property_type(*x.m_property))
289 : { }
290 :
291 0 : adjacency_list& operator=(const adjacency_list& x) {
292 : // TBD: probably should give the strong guarantee
293 0 : if (&x != this) {
294 0 : Base::operator=(x);
295 :
296 : // Copy/swap the ptr since we can't just assign it...
297 0 : property_ptr p(new graph_property_type(*x.m_property));
298 0 : m_property.swap(p);
299 : }
300 0 : return *this;
301 : }
302 :
303 : // Required by Mutable Graph
304 0 : adjacency_list(vertices_size_type num_vertices,
305 : const GraphProperty& p = GraphProperty())
306 0 : : Base(num_vertices), m_property(new graph_property_type(p))
307 0 : { }
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 0 : void clear()
335 : {
336 0 : this->clearing_graph();
337 0 : Base::clear();
338 : }
339 :
340 : #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
341 : // Directly access a vertex or edge bundle
342 0 : vertex_bundled& operator[](vertex_descriptor v)
343 0 : { return get(vertex_bundle, *this)[v]; }
344 :
345 0 : const vertex_bundled& operator[](vertex_descriptor v) const
346 0 : { return get(vertex_bundle, *this)[v]; }
347 :
348 0 : edge_bundled& operator[](edge_descriptor e)
349 0 : { 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 0 : 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 0 : 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
|
