williamr@2
|
1 |
//=======================================================================
|
williamr@2
|
2 |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
williamr@2
|
3 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
williamr@2
|
4 |
//
|
williamr@2
|
5 |
// Distributed under the Boost Software License, Version 1.0. (See
|
williamr@2
|
6 |
// accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
7 |
// http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
8 |
//=======================================================================
|
williamr@2
|
9 |
|
williamr@4
|
10 |
#ifndef BOOST_GRAPH_ADJACENCY_LIST_HPP
|
williamr@4
|
11 |
#define BOOST_GRAPH_ADJACENCY_LIST_HPP
|
williamr@2
|
12 |
|
williamr@4
|
13 |
|
williamr@2
|
14 |
#include <boost/config.hpp>
|
williamr@4
|
15 |
|
williamr@4
|
16 |
#include <vector>
|
williamr@4
|
17 |
#include <list>
|
williamr@4
|
18 |
#include <set>
|
williamr@4
|
19 |
|
williamr@4
|
20 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
21 |
# ifdef BOOST_HASH_SET_HEADER
|
williamr@4
|
22 |
# include BOOST_HASH_SET_HEADER
|
williamr@4
|
23 |
# else
|
williamr@4
|
24 |
# include <hash_set>
|
williamr@4
|
25 |
# endif
|
williamr@4
|
26 |
#endif
|
williamr@4
|
27 |
|
williamr@4
|
28 |
#if !defined BOOST_NO_SLIST
|
williamr@4
|
29 |
# ifdef BOOST_SLIST_HEADER
|
williamr@4
|
30 |
# include BOOST_SLIST_HEADER
|
williamr@4
|
31 |
# else
|
williamr@4
|
32 |
# include <slist>
|
williamr@4
|
33 |
# endif
|
williamr@4
|
34 |
#endif
|
williamr@4
|
35 |
|
williamr@4
|
36 |
#include <boost/graph/graph_traits.hpp>
|
williamr@4
|
37 |
#include <boost/graph/graph_selectors.hpp>
|
williamr@4
|
38 |
#include <boost/property_map.hpp>
|
williamr@4
|
39 |
#include <boost/pending/ct_if.hpp>
|
williamr@4
|
40 |
#include <boost/graph/detail/edge.hpp>
|
williamr@4
|
41 |
#include <boost/type_traits/is_same.hpp>
|
williamr@2
|
42 |
#include <boost/detail/workaround.hpp>
|
williamr@2
|
43 |
#include <boost/graph/properties.hpp>
|
williamr@2
|
44 |
|
williamr@2
|
45 |
namespace boost {
|
williamr@2
|
46 |
|
williamr@4
|
47 |
//===========================================================================
|
williamr@4
|
48 |
// Selectors for the VertexList and EdgeList template parameters of
|
williamr@4
|
49 |
// adjacency_list, and the container_gen traits class which is used
|
williamr@4
|
50 |
// to map the selectors to the container type used to implement the
|
williamr@4
|
51 |
// graph.
|
williamr@4
|
52 |
//
|
williamr@4
|
53 |
// The main container_gen traits class uses partial specialization,
|
williamr@4
|
54 |
// so we also include a workaround.
|
williamr@4
|
55 |
|
williamr@4
|
56 |
#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
williamr@4
|
57 |
|
williamr@4
|
58 |
#if !defined BOOST_NO_SLIST
|
williamr@4
|
59 |
struct slistS {};
|
williamr@4
|
60 |
#endif
|
williamr@4
|
61 |
|
williamr@4
|
62 |
struct vecS { };
|
williamr@4
|
63 |
struct listS { };
|
williamr@4
|
64 |
struct setS { };
|
williamr@4
|
65 |
struct multisetS { };
|
williamr@4
|
66 |
struct mapS { };
|
williamr@4
|
67 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
68 |
struct hash_mapS { };
|
williamr@4
|
69 |
struct hash_setS { };
|
williamr@4
|
70 |
#endif
|
williamr@4
|
71 |
|
williamr@4
|
72 |
template <class Selector, class ValueType>
|
williamr@4
|
73 |
struct container_gen { };
|
williamr@4
|
74 |
|
williamr@4
|
75 |
template <class ValueType>
|
williamr@4
|
76 |
struct container_gen<listS, ValueType> {
|
williamr@4
|
77 |
typedef std::list<ValueType> type;
|
williamr@4
|
78 |
};
|
williamr@4
|
79 |
#if !defined BOOST_NO_SLIST
|
williamr@4
|
80 |
template <class ValueType>
|
williamr@4
|
81 |
struct container_gen<slistS, ValueType> {
|
williamr@4
|
82 |
typedef BOOST_STD_EXTENSION_NAMESPACE::slist<ValueType> type;
|
williamr@4
|
83 |
};
|
williamr@4
|
84 |
#endif
|
williamr@4
|
85 |
template <class ValueType>
|
williamr@4
|
86 |
struct container_gen<vecS, ValueType> {
|
williamr@4
|
87 |
typedef std::vector<ValueType> type;
|
williamr@4
|
88 |
};
|
williamr@4
|
89 |
|
williamr@4
|
90 |
template <class ValueType>
|
williamr@4
|
91 |
struct container_gen<mapS, ValueType> {
|
williamr@4
|
92 |
typedef std::set<ValueType> type;
|
williamr@4
|
93 |
};
|
williamr@4
|
94 |
|
williamr@4
|
95 |
template <class ValueType>
|
williamr@4
|
96 |
struct container_gen<setS, ValueType> {
|
williamr@4
|
97 |
typedef std::set<ValueType> type;
|
williamr@4
|
98 |
};
|
williamr@4
|
99 |
|
williamr@4
|
100 |
template <class ValueType>
|
williamr@4
|
101 |
struct container_gen<multisetS, ValueType> {
|
williamr@4
|
102 |
typedef std::multiset<ValueType> type;
|
williamr@4
|
103 |
};
|
williamr@4
|
104 |
|
williamr@4
|
105 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
106 |
template <class ValueType>
|
williamr@4
|
107 |
struct container_gen<hash_mapS, ValueType> {
|
williamr@4
|
108 |
typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
|
williamr@4
|
109 |
};
|
williamr@4
|
110 |
|
williamr@4
|
111 |
template <class ValueType>
|
williamr@4
|
112 |
struct container_gen<hash_setS, ValueType> {
|
williamr@4
|
113 |
typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
|
williamr@4
|
114 |
};
|
williamr@4
|
115 |
#endif
|
williamr@4
|
116 |
|
williamr@4
|
117 |
#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
williamr@4
|
118 |
|
williamr@4
|
119 |
#if !defined BOOST_NO_SLIST
|
williamr@4
|
120 |
struct slistS {
|
williamr@4
|
121 |
template <class T>
|
williamr@4
|
122 |
struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::slist<T> type; };
|
williamr@4
|
123 |
};
|
williamr@4
|
124 |
#endif
|
williamr@4
|
125 |
|
williamr@4
|
126 |
struct vecS {
|
williamr@4
|
127 |
template <class T>
|
williamr@4
|
128 |
struct bind_ { typedef std::vector<T> type; };
|
williamr@4
|
129 |
};
|
williamr@4
|
130 |
|
williamr@4
|
131 |
struct listS {
|
williamr@4
|
132 |
template <class T>
|
williamr@4
|
133 |
struct bind_ { typedef std::list<T> type; };
|
williamr@4
|
134 |
};
|
williamr@4
|
135 |
|
williamr@4
|
136 |
struct setS {
|
williamr@4
|
137 |
template <class T>
|
williamr@4
|
138 |
struct bind_ { typedef std::set<T, std::less<T> > type; };
|
williamr@4
|
139 |
};
|
williamr@4
|
140 |
|
williamr@4
|
141 |
struct multisetS {
|
williamr@4
|
142 |
template <class T>
|
williamr@4
|
143 |
struct bind_ { typedef std::multiset<T, std::less<T> > type; };
|
williamr@4
|
144 |
};
|
williamr@4
|
145 |
|
williamr@4
|
146 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
147 |
struct hash_setS {
|
williamr@4
|
148 |
template <class T>
|
williamr@4
|
149 |
struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
|
williamr@4
|
150 |
};
|
williamr@4
|
151 |
#endif
|
williamr@4
|
152 |
|
williamr@4
|
153 |
struct mapS {
|
williamr@4
|
154 |
template <class T>
|
williamr@4
|
155 |
struct bind_ { typedef std::set<T, std::less<T> > type; };
|
williamr@4
|
156 |
};
|
williamr@4
|
157 |
|
williamr@4
|
158 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
159 |
struct hash_mapS {
|
williamr@4
|
160 |
template <class T>
|
williamr@4
|
161 |
struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
|
williamr@4
|
162 |
};
|
williamr@4
|
163 |
#endif
|
williamr@4
|
164 |
|
williamr@4
|
165 |
template <class Selector> struct container_selector {
|
williamr@4
|
166 |
typedef vecS type;
|
williamr@4
|
167 |
};
|
williamr@4
|
168 |
|
williamr@4
|
169 |
#define BOOST_CONTAINER_SELECTOR(NAME) \
|
williamr@4
|
170 |
template <> struct container_selector<NAME> { \
|
williamr@4
|
171 |
typedef NAME type; \
|
williamr@4
|
172 |
}
|
williamr@4
|
173 |
|
williamr@4
|
174 |
BOOST_CONTAINER_SELECTOR(vecS);
|
williamr@4
|
175 |
BOOST_CONTAINER_SELECTOR(listS);
|
williamr@4
|
176 |
BOOST_CONTAINER_SELECTOR(mapS);
|
williamr@4
|
177 |
BOOST_CONTAINER_SELECTOR(setS);
|
williamr@4
|
178 |
BOOST_CONTAINER_SELECTOR(multisetS);
|
williamr@4
|
179 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
180 |
BOOST_CONTAINER_SELECTOR(hash_mapS);
|
williamr@4
|
181 |
#endif
|
williamr@4
|
182 |
#if !defined BOOST_NO_SLIST
|
williamr@4
|
183 |
BOOST_CONTAINER_SELECTOR(slistS);
|
williamr@4
|
184 |
#endif
|
williamr@4
|
185 |
|
williamr@4
|
186 |
template <class Selector, class ValueType>
|
williamr@4
|
187 |
struct container_gen {
|
williamr@4
|
188 |
typedef typename container_selector<Selector>::type Select;
|
williamr@4
|
189 |
typedef typename Select:: template bind_<ValueType>::type type;
|
williamr@4
|
190 |
};
|
williamr@4
|
191 |
|
williamr@4
|
192 |
#endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
williamr@4
|
193 |
|
williamr@4
|
194 |
template <class StorageSelector>
|
williamr@4
|
195 |
struct parallel_edge_traits { };
|
williamr@4
|
196 |
|
williamr@4
|
197 |
template <>
|
williamr@4
|
198 |
struct parallel_edge_traits<vecS> {
|
williamr@4
|
199 |
typedef allow_parallel_edge_tag type; };
|
williamr@4
|
200 |
|
williamr@4
|
201 |
template <>
|
williamr@4
|
202 |
struct parallel_edge_traits<listS> {
|
williamr@4
|
203 |
typedef allow_parallel_edge_tag type; };
|
williamr@4
|
204 |
|
williamr@4
|
205 |
#if !defined BOOST_NO_SLIST
|
williamr@4
|
206 |
template <>
|
williamr@4
|
207 |
struct parallel_edge_traits<slistS> {
|
williamr@4
|
208 |
typedef allow_parallel_edge_tag type; };
|
williamr@4
|
209 |
#endif
|
williamr@4
|
210 |
|
williamr@4
|
211 |
template <>
|
williamr@4
|
212 |
struct parallel_edge_traits<setS> {
|
williamr@4
|
213 |
typedef disallow_parallel_edge_tag type; };
|
williamr@4
|
214 |
|
williamr@4
|
215 |
template <>
|
williamr@4
|
216 |
struct parallel_edge_traits<multisetS> {
|
williamr@4
|
217 |
typedef allow_parallel_edge_tag type; };
|
williamr@4
|
218 |
|
williamr@4
|
219 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
220 |
template <>
|
williamr@4
|
221 |
struct parallel_edge_traits<hash_setS> {
|
williamr@4
|
222 |
typedef disallow_parallel_edge_tag type;
|
williamr@4
|
223 |
};
|
williamr@4
|
224 |
#endif
|
williamr@4
|
225 |
|
williamr@4
|
226 |
// mapS is obsolete, replaced with setS
|
williamr@4
|
227 |
template <>
|
williamr@4
|
228 |
struct parallel_edge_traits<mapS> {
|
williamr@4
|
229 |
typedef disallow_parallel_edge_tag type; };
|
williamr@4
|
230 |
|
williamr@4
|
231 |
#if !defined BOOST_NO_HASH
|
williamr@4
|
232 |
template <>
|
williamr@4
|
233 |
struct parallel_edge_traits<hash_mapS> {
|
williamr@4
|
234 |
typedef disallow_parallel_edge_tag type;
|
williamr@4
|
235 |
};
|
williamr@4
|
236 |
#endif
|
williamr@4
|
237 |
|
williamr@2
|
238 |
namespace detail {
|
williamr@4
|
239 |
template <class Directed> struct is_random_access {
|
williamr@4
|
240 |
enum { value = false};
|
williamr@4
|
241 |
typedef false_type type;
|
williamr@2
|
242 |
};
|
williamr@2
|
243 |
template <>
|
williamr@4
|
244 |
struct is_random_access<vecS> {
|
williamr@4
|
245 |
enum { value = true };
|
williamr@4
|
246 |
typedef true_type type;
|
williamr@2
|
247 |
};
|
williamr@2
|
248 |
|
williamr@2
|
249 |
} // namespace detail
|
williamr@2
|
250 |
|
williamr@2
|
251 |
|
williamr@2
|
252 |
|
williamr@4
|
253 |
//===========================================================================
|
williamr@4
|
254 |
// The adjacency_list_traits class, which provides a way to access
|
williamr@4
|
255 |
// some of the associated types of an adjacency_list type without
|
williamr@4
|
256 |
// having to first create the adjacency_list type. This is useful
|
williamr@4
|
257 |
// when trying to create interior vertex or edge properties who's
|
williamr@4
|
258 |
// value type is a vertex or edge descriptor.
|
williamr@2
|
259 |
|
williamr@4
|
260 |
template <class OutEdgeListS = vecS,
|
williamr@4
|
261 |
class VertexListS = vecS,
|
williamr@4
|
262 |
class DirectedS = directedS>
|
williamr@4
|
263 |
struct adjacency_list_traits
|
williamr@4
|
264 |
{
|
williamr@4
|
265 |
typedef typename detail::is_random_access<VertexListS>::type
|
williamr@4
|
266 |
is_rand_access;
|
williamr@4
|
267 |
typedef typename DirectedS::is_bidir_t is_bidir;
|
williamr@4
|
268 |
typedef typename DirectedS::is_directed_t is_directed;
|
williamr@2
|
269 |
|
williamr@4
|
270 |
typedef typename boost::ct_if_t<is_bidir,
|
williamr@4
|
271 |
bidirectional_tag,
|
williamr@4
|
272 |
typename boost::ct_if_t<is_directed,
|
williamr@4
|
273 |
directed_tag, undirected_tag
|
williamr@4
|
274 |
>::type
|
williamr@4
|
275 |
>::type directed_category;
|
williamr@2
|
276 |
|
williamr@4
|
277 |
typedef typename parallel_edge_traits<OutEdgeListS>::type
|
williamr@4
|
278 |
edge_parallel_category;
|
williamr@2
|
279 |
|
williamr@4
|
280 |
typedef void* vertex_ptr;
|
williamr@4
|
281 |
typedef typename boost::ct_if_t<is_rand_access,
|
williamr@4
|
282 |
std::size_t, vertex_ptr>::type vertex_descriptor;
|
williamr@4
|
283 |
typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
|
williamr@4
|
284 |
edge_descriptor;
|
williamr@2
|
285 |
};
|
williamr@2
|
286 |
|
williamr@2
|
287 |
} // namespace boost
|
williamr@2
|
288 |
|
williamr@4
|
289 |
#include <boost/graph/detail/adjacency_list.hpp>
|
williamr@2
|
290 |
|
williamr@4
|
291 |
namespace boost {
|
williamr@4
|
292 |
|
williamr@4
|
293 |
//===========================================================================
|
williamr@4
|
294 |
// The adjacency_list class.
|
williamr@4
|
295 |
//
|
williamr@4
|
296 |
|
williamr@4
|
297 |
template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer
|
williamr@4
|
298 |
class VertexListS = vecS, // a Sequence or a RandomAccessContainer
|
williamr@4
|
299 |
class DirectedS = directedS,
|
williamr@4
|
300 |
class VertexProperty = no_property,
|
williamr@4
|
301 |
class EdgeProperty = no_property,
|
williamr@4
|
302 |
class GraphProperty = no_property,
|
williamr@4
|
303 |
class EdgeListS = listS>
|
williamr@4
|
304 |
class adjacency_list
|
williamr@4
|
305 |
: public detail::adj_list_gen<
|
williamr@4
|
306 |
adjacency_list<OutEdgeListS,VertexListS,DirectedS,
|
williamr@4
|
307 |
VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
|
williamr@4
|
308 |
VertexListS, OutEdgeListS, DirectedS,
|
williamr@4
|
309 |
#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
|
williamr@4
|
310 |
typename detail::retag_property_list<vertex_bundle_t,
|
williamr@4
|
311 |
VertexProperty>::type,
|
williamr@4
|
312 |
typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type,
|
williamr@4
|
313 |
#else
|
williamr@4
|
314 |
VertexProperty, EdgeProperty,
|
williamr@4
|
315 |
#endif
|
williamr@4
|
316 |
GraphProperty, EdgeListS>::type
|
williamr@2
|
317 |
{
|
williamr@4
|
318 |
#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
|
williamr@4
|
319 |
typedef typename detail::retag_property_list<vertex_bundle_t,
|
williamr@4
|
320 |
VertexProperty>::retagged
|
williamr@4
|
321 |
maybe_vertex_bundled;
|
williamr@2
|
322 |
|
williamr@4
|
323 |
typedef typename detail::retag_property_list<edge_bundle_t,
|
williamr@4
|
324 |
EdgeProperty>::retagged
|
williamr@4
|
325 |
maybe_edge_bundled;
|
williamr@4
|
326 |
#endif
|
williamr@4
|
327 |
|
williamr@4
|
328 |
public:
|
williamr@4
|
329 |
#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
|
williamr@4
|
330 |
typedef typename detail::retag_property_list<vertex_bundle_t,
|
williamr@4
|
331 |
VertexProperty>::type
|
williamr@4
|
332 |
vertex_property_type;
|
williamr@4
|
333 |
typedef typename detail::retag_property_list<edge_bundle_t,
|
williamr@4
|
334 |
EdgeProperty>::type
|
williamr@4
|
335 |
edge_property_type;
|
williamr@4
|
336 |
|
williamr@4
|
337 |
// The types that are actually bundled
|
williamr@4
|
338 |
typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
|
williamr@4
|
339 |
no_vertex_bundle,
|
williamr@4
|
340 |
maybe_vertex_bundled>::type vertex_bundled;
|
williamr@4
|
341 |
typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
|
williamr@4
|
342 |
no_edge_bundle,
|
williamr@4
|
343 |
maybe_edge_bundled>::type edge_bundled;
|
williamr@4
|
344 |
#else
|
williamr@4
|
345 |
typedef VertexProperty vertex_property_type;
|
williamr@4
|
346 |
typedef EdgeProperty edge_property_type;
|
williamr@4
|
347 |
typedef no_vertex_bundle vertex_bundled;
|
williamr@4
|
348 |
typedef no_edge_bundle edge_bundled;
|
williamr@4
|
349 |
#endif
|
williamr@4
|
350 |
|
williamr@4
|
351 |
private:
|
williamr@4
|
352 |
typedef adjacency_list self;
|
williamr@4
|
353 |
typedef typename detail::adj_list_gen<
|
williamr@4
|
354 |
self, VertexListS, OutEdgeListS, DirectedS,
|
williamr@4
|
355 |
vertex_property_type, edge_property_type, GraphProperty, EdgeListS
|
williamr@4
|
356 |
>::type Base;
|
williamr@4
|
357 |
|
williamr@4
|
358 |
public:
|
williamr@4
|
359 |
typedef typename Base::stored_vertex stored_vertex;
|
williamr@4
|
360 |
typedef typename Base::vertices_size_type vertices_size_type;
|
williamr@4
|
361 |
typedef typename Base::edges_size_type edges_size_type;
|
williamr@4
|
362 |
typedef typename Base::degree_size_type degree_size_type;
|
williamr@4
|
363 |
typedef typename Base::vertex_descriptor vertex_descriptor;
|
williamr@4
|
364 |
typedef typename Base::edge_descriptor edge_descriptor;
|
williamr@4
|
365 |
typedef OutEdgeListS out_edge_list_selector;
|
williamr@4
|
366 |
typedef VertexListS vertex_list_selector;
|
williamr@4
|
367 |
typedef DirectedS directed_selector;
|
williamr@4
|
368 |
typedef EdgeListS edge_list_selector;
|
williamr@4
|
369 |
|
williamr@4
|
370 |
typedef GraphProperty graph_property_type;
|
williamr@4
|
371 |
|
williamr@4
|
372 |
inline adjacency_list(const GraphProperty& p = GraphProperty())
|
williamr@4
|
373 |
: m_property(p) { }
|
williamr@4
|
374 |
|
williamr@4
|
375 |
inline adjacency_list(const adjacency_list& x)
|
williamr@4
|
376 |
: Base(x), m_property(x.m_property) { }
|
williamr@4
|
377 |
|
williamr@4
|
378 |
inline adjacency_list& operator=(const adjacency_list& x) {
|
williamr@4
|
379 |
// TBD: probably should give the strong guarantee
|
williamr@4
|
380 |
if (&x != this) {
|
williamr@4
|
381 |
Base::operator=(x);
|
williamr@4
|
382 |
m_property = x.m_property;
|
williamr@4
|
383 |
}
|
williamr@4
|
384 |
return *this;
|
williamr@2
|
385 |
}
|
williamr@4
|
386 |
|
williamr@4
|
387 |
// Required by Mutable Graph
|
williamr@4
|
388 |
inline adjacency_list(vertices_size_type num_vertices,
|
williamr@4
|
389 |
const GraphProperty& p = GraphProperty())
|
williamr@4
|
390 |
: Base(num_vertices), m_property(p) { }
|
williamr@4
|
391 |
|
williamr@4
|
392 |
#if !defined(BOOST_MSVC) || BOOST_MSVC >= 1300
|
williamr@4
|
393 |
// Required by Iterator Constructible Graph
|
williamr@4
|
394 |
template <class EdgeIterator>
|
williamr@4
|
395 |
inline adjacency_list(EdgeIterator first, EdgeIterator last,
|
williamr@4
|
396 |
vertices_size_type n,
|
williamr@4
|
397 |
edges_size_type = 0,
|
williamr@4
|
398 |
const GraphProperty& p = GraphProperty())
|
williamr@4
|
399 |
: Base(n, first, last), m_property(p) { }
|
williamr@4
|
400 |
|
williamr@4
|
401 |
template <class EdgeIterator, class EdgePropertyIterator>
|
williamr@4
|
402 |
inline adjacency_list(EdgeIterator first, EdgeIterator last,
|
williamr@4
|
403 |
EdgePropertyIterator ep_iter,
|
williamr@4
|
404 |
vertices_size_type n,
|
williamr@4
|
405 |
edges_size_type = 0,
|
williamr@4
|
406 |
const GraphProperty& p = GraphProperty())
|
williamr@4
|
407 |
: Base(n, first, last, ep_iter), m_property(p) { }
|
williamr@4
|
408 |
#endif
|
williamr@4
|
409 |
|
williamr@4
|
410 |
void swap(adjacency_list& x) {
|
williamr@4
|
411 |
// Is there a more efficient way to do this?
|
williamr@4
|
412 |
adjacency_list tmp(x);
|
williamr@4
|
413 |
x = *this;
|
williamr@4
|
414 |
*this = tmp;
|
williamr@4
|
415 |
}
|
williamr@4
|
416 |
|
williamr@4
|
417 |
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
williamr@4
|
418 |
// Directly access a vertex or edge bundle
|
williamr@4
|
419 |
vertex_bundled& operator[](vertex_descriptor v)
|
williamr@4
|
420 |
{ return get(vertex_bundle, *this)[v]; }
|
williamr@4
|
421 |
|
williamr@4
|
422 |
const vertex_bundled& operator[](vertex_descriptor v) const
|
williamr@4
|
423 |
{ return get(vertex_bundle, *this)[v]; }
|
williamr@4
|
424 |
|
williamr@4
|
425 |
edge_bundled& operator[](edge_descriptor e)
|
williamr@4
|
426 |
{ return get(edge_bundle, *this)[e]; }
|
williamr@4
|
427 |
|
williamr@4
|
428 |
const edge_bundled& operator[](edge_descriptor e) const
|
williamr@4
|
429 |
{ return get(edge_bundle, *this)[e]; }
|
williamr@4
|
430 |
#endif
|
williamr@4
|
431 |
|
williamr@4
|
432 |
// protected: (would be protected if friends were more portable)
|
williamr@4
|
433 |
GraphProperty m_property;
|
williamr@2
|
434 |
};
|
williamr@2
|
435 |
|
williamr@4
|
436 |
template <class OEL, class VL, class DirS, class VP,class EP, class GP,
|
williamr@4
|
437 |
class EL, class Tag, class Value>
|
williamr@4
|
438 |
inline void
|
williamr@4
|
439 |
set_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag,
|
williamr@4
|
440 |
const Value& value) {
|
williamr@4
|
441 |
get_property_value(g.m_property, Tag()) = value;;
|
williamr@4
|
442 |
}
|
williamr@4
|
443 |
|
williamr@4
|
444 |
template <class OEL, class VL, class DirS, class VP, class EP, class GP,
|
williamr@4
|
445 |
class Tag, class EL>
|
williamr@4
|
446 |
inline
|
williamr@4
|
447 |
typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
|
williamr@4
|
448 |
get_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
|
williamr@4
|
449 |
return get_property_value(g.m_property, Tag());
|
williamr@4
|
450 |
}
|
williamr@4
|
451 |
|
williamr@4
|
452 |
template <class OEL, class VL, class DirS, class VP, class EP, class GP,
|
williamr@4
|
453 |
class Tag, class EL>
|
williamr@4
|
454 |
inline
|
williamr@4
|
455 |
const
|
williamr@4
|
456 |
typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
|
williamr@4
|
457 |
get_property(const adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
|
williamr@4
|
458 |
return get_property_value(g.m_property, Tag());
|
williamr@4
|
459 |
}
|
williamr@4
|
460 |
|
williamr@4
|
461 |
// dwa 09/25/00 - needed to be more explicit so reverse_graph would work.
|
williamr@4
|
462 |
template <class Directed, class Vertex,
|
williamr@4
|
463 |
class OutEdgeListS,
|
williamr@4
|
464 |
class VertexListS,
|
williamr@4
|
465 |
class DirectedS,
|
williamr@4
|
466 |
class VertexProperty,
|
williamr@4
|
467 |
class EdgeProperty,
|
williamr@4
|
468 |
class GraphProperty, class EdgeListS>
|
williamr@4
|
469 |
inline Vertex
|
williamr@4
|
470 |
source(const detail::edge_base<Directed,Vertex>& e,
|
williamr@4
|
471 |
const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
|
williamr@4
|
472 |
VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
|
williamr@2
|
473 |
{
|
williamr@4
|
474 |
return e.m_source;
|
williamr@4
|
475 |
}
|
williamr@2
|
476 |
|
williamr@4
|
477 |
template <class Directed, class Vertex, class OutEdgeListS,
|
williamr@4
|
478 |
class VertexListS, class DirectedS, class VertexProperty,
|
williamr@4
|
479 |
class EdgeProperty, class GraphProperty, class EdgeListS>
|
williamr@4
|
480 |
inline Vertex
|
williamr@4
|
481 |
target(const detail::edge_base<Directed,Vertex>& e,
|
williamr@4
|
482 |
const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
|
williamr@4
|
483 |
VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
|
williamr@2
|
484 |
{
|
williamr@4
|
485 |
return e.m_target;
|
williamr@4
|
486 |
}
|
williamr@2
|
487 |
|
williamr@4
|
488 |
// Support for bundled properties
|
williamr@4
|
489 |
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
williamr@4
|
490 |
template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
williamr@4
|
491 |
typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
|
williamr@4
|
492 |
inline
|
williamr@4
|
493 |
typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
williamr@4
|
494 |
GraphProperty, EdgeListS>, T Bundle::*>::type
|
williamr@4
|
495 |
get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
williamr@4
|
496 |
GraphProperty, EdgeListS>& g)
|
williamr@4
|
497 |
{
|
williamr@4
|
498 |
typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
|
williamr@4
|
499 |
EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::type
|
williamr@4
|
500 |
result_type;
|
williamr@4
|
501 |
return result_type(&g, p);
|
williamr@4
|
502 |
}
|
williamr@4
|
503 |
|
williamr@4
|
504 |
template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
williamr@4
|
505 |
typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
|
williamr@4
|
506 |
inline
|
williamr@4
|
507 |
typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
williamr@4
|
508 |
GraphProperty, EdgeListS>, T Bundle::*>::const_type
|
williamr@4
|
509 |
get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
williamr@4
|
510 |
GraphProperty, EdgeListS> const & g)
|
williamr@4
|
511 |
{
|
williamr@4
|
512 |
typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
|
williamr@4
|
513 |
EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::const_type
|
williamr@4
|
514 |
result_type;
|
williamr@4
|
515 |
return result_type(&g, p);
|
williamr@4
|
516 |
}
|
williamr@4
|
517 |
|
williamr@4
|
518 |
template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
williamr@4
|
519 |
typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
|
williamr@4
|
520 |
typename Key>
|
williamr@4
|
521 |
inline T
|
williamr@4
|
522 |
get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
williamr@4
|
523 |
GraphProperty, EdgeListS> const & g, const Key& key)
|
williamr@4
|
524 |
{
|
williamr@4
|
525 |
return get(get(p, g), key);
|
williamr@4
|
526 |
}
|
williamr@4
|
527 |
|
williamr@4
|
528 |
template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
williamr@4
|
529 |
typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
|
williamr@4
|
530 |
typename Key>
|
williamr@4
|
531 |
inline void
|
williamr@4
|
532 |
put(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
williamr@4
|
533 |
GraphProperty, EdgeListS>& g, const Key& key, const T& value)
|
williamr@4
|
534 |
{
|
williamr@4
|
535 |
put(get(p, g), key, value);
|
williamr@4
|
536 |
}
|
williamr@4
|
537 |
|
williamr@2
|
538 |
#endif
|
williamr@2
|
539 |
|
williamr@2
|
540 |
|
williamr@4
|
541 |
} // namespace boost
|
williamr@2
|
542 |
|
williamr@2
|
543 |
|
williamr@4
|
544 |
#endif // BOOST_GRAPH_ADJACENCY_LIST_HPP
|