1 | // -*- c++ -*-
|
---|
2 | //=======================================================================
|
---|
3 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
---|
4 | // Copyright 2010 Thomas Claveirole
|
---|
5 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
|
---|
6 | //
|
---|
7 | // Distributed under the Boost Software License, Version 1.0. (See
|
---|
8 | // accompanying file LICENSE_1_0.txt or copy at
|
---|
9 | // http://www.boost.org/LICENSE_1_0.txt)
|
---|
10 | //=======================================================================
|
---|
11 |
|
---|
12 | #ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
|
---|
13 | #define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
|
---|
14 |
|
---|
15 | #include <map> // for vertex_map in copy_impl
|
---|
16 | #include <boost/config.hpp>
|
---|
17 | #include <boost/detail/workaround.hpp>
|
---|
18 | #include <boost/operators.hpp>
|
---|
19 | #include <boost/property_map/property_map.hpp>
|
---|
20 | #include <boost/pending/container_traits.hpp>
|
---|
21 | #include <boost/range/irange.hpp>
|
---|
22 | #include <boost/graph/graph_traits.hpp>
|
---|
23 | #include <memory>
|
---|
24 | #include <algorithm>
|
---|
25 | #include <boost/limits.hpp>
|
---|
26 |
|
---|
27 | #include <boost/iterator/iterator_adaptor.hpp>
|
---|
28 |
|
---|
29 | #include <boost/mpl/if.hpp>
|
---|
30 | #include <boost/mpl/not.hpp>
|
---|
31 | #include <boost/mpl/and.hpp>
|
---|
32 | #include <boost/graph/graph_concepts.hpp>
|
---|
33 | #include <boost/pending/container_traits.hpp>
|
---|
34 | #include <boost/graph/detail/adj_list_edge_iterator.hpp>
|
---|
35 | #include <boost/graph/properties.hpp>
|
---|
36 | #include <boost/pending/property.hpp>
|
---|
37 | #include <boost/graph/adjacency_iterator.hpp>
|
---|
38 | #include <boost/static_assert.hpp>
|
---|
39 | #include <boost/assert.hpp>
|
---|
40 |
|
---|
41 | #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES
|
---|
42 | #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (x)
|
---|
43 | #else
|
---|
44 | #include <utility>
|
---|
45 | #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (std::move((x)))
|
---|
46 | #endif
|
---|
47 |
|
---|
48 | /*
|
---|
49 | Outline for this file:
|
---|
50 |
|
---|
51 | out_edge_iterator and in_edge_iterator implementation
|
---|
52 | edge_iterator for undirected graph
|
---|
53 | stored edge types (these object live in the out-edge/in-edge lists)
|
---|
54 | directed edges helper class
|
---|
55 | directed graph helper class
|
---|
56 | undirected graph helper class
|
---|
57 | bidirectional graph helper class
|
---|
58 | bidirectional graph helper class (without edge properties)
|
---|
59 | bidirectional graph helper class (with edge properties)
|
---|
60 | adjacency_list helper class
|
---|
61 | adj_list_impl class
|
---|
62 | vec_adj_list_impl class
|
---|
63 | adj_list_gen class
|
---|
64 | vertex property map
|
---|
65 | edge property map
|
---|
66 |
|
---|
67 |
|
---|
68 | Note: it would be nice to merge some of the undirected and
|
---|
69 | bidirectional code... it is awful similar.
|
---|
70 | */
|
---|
71 |
|
---|
72 |
|
---|
73 | namespace boost {
|
---|
74 |
|
---|
75 | namespace detail {
|
---|
76 |
|
---|
77 | template <typename DirectedS>
|
---|
78 | struct directed_category_traits {
|
---|
79 | typedef directed_tag directed_category;
|
---|
80 | };
|
---|
81 |
|
---|
82 | template <>
|
---|
83 | struct directed_category_traits<directedS> {
|
---|
84 | typedef directed_tag directed_category;
|
---|
85 | };
|
---|
86 | template <>
|
---|
87 | struct directed_category_traits<undirectedS> {
|
---|
88 | typedef undirected_tag directed_category;
|
---|
89 | };
|
---|
90 | template <>
|
---|
91 | struct directed_category_traits<bidirectionalS> {
|
---|
92 | typedef bidirectional_tag directed_category;
|
---|
93 | };
|
---|
94 |
|
---|
95 | template <class Vertex>
|
---|
96 | struct target_is {
|
---|
97 | target_is(const Vertex& v) : m_target(v) { }
|
---|
98 | template <class StoredEdge>
|
---|
99 | bool operator()(const StoredEdge& e) const {
|
---|
100 | return e.get_target() == m_target;
|
---|
101 | }
|
---|
102 | Vertex m_target;
|
---|
103 | };
|
---|
104 |
|
---|
105 | // O(E/V)
|
---|
106 | template <class EdgeList, class vertex_descriptor>
|
---|
107 | void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
|
---|
108 | allow_parallel_edge_tag)
|
---|
109 | {
|
---|
110 | boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
|
---|
111 | }
|
---|
112 | // O(log(E/V))
|
---|
113 | template <class EdgeList, class vertex_descriptor>
|
---|
114 | void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
|
---|
115 | disallow_parallel_edge_tag)
|
---|
116 | {
|
---|
117 | typedef typename EdgeList::value_type StoredEdge;
|
---|
118 | el.erase(StoredEdge(v));
|
---|
119 | }
|
---|
120 |
|
---|
121 | //=========================================================================
|
---|
122 | // Out-Edge and In-Edge Iterator Implementation
|
---|
123 |
|
---|
124 | template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
|
---|
125 | struct out_edge_iter
|
---|
126 | : iterator_adaptor<
|
---|
127 | out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
---|
128 | , BaseIter
|
---|
129 | , EdgeDescriptor
|
---|
130 | , use_default
|
---|
131 | , EdgeDescriptor
|
---|
132 | , Difference
|
---|
133 | >
|
---|
134 | {
|
---|
135 | typedef iterator_adaptor<
|
---|
136 | out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
---|
137 | , BaseIter
|
---|
138 | , EdgeDescriptor
|
---|
139 | , use_default
|
---|
140 | , EdgeDescriptor
|
---|
141 | , Difference
|
---|
142 | > super_t;
|
---|
143 |
|
---|
144 | inline out_edge_iter() { }
|
---|
145 | inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
|
---|
146 | : super_t(i), m_src(src) { }
|
---|
147 |
|
---|
148 | inline EdgeDescriptor
|
---|
149 | dereference() const
|
---|
150 | {
|
---|
151 | return EdgeDescriptor(m_src, (*this->base()).get_target(),
|
---|
152 | &(*this->base()).get_property());
|
---|
153 | }
|
---|
154 | VertexDescriptor m_src;
|
---|
155 | };
|
---|
156 |
|
---|
157 | template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
|
---|
158 | struct in_edge_iter
|
---|
159 | : iterator_adaptor<
|
---|
160 | in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
---|
161 | , BaseIter
|
---|
162 | , EdgeDescriptor
|
---|
163 | , use_default
|
---|
164 | , EdgeDescriptor
|
---|
165 | , Difference
|
---|
166 | >
|
---|
167 | {
|
---|
168 | typedef iterator_adaptor<
|
---|
169 | in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
---|
170 | , BaseIter
|
---|
171 | , EdgeDescriptor
|
---|
172 | , use_default
|
---|
173 | , EdgeDescriptor
|
---|
174 | , Difference
|
---|
175 | > super_t;
|
---|
176 |
|
---|
177 | inline in_edge_iter() { }
|
---|
178 | inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
|
---|
179 | : super_t(i), m_src(src) { }
|
---|
180 |
|
---|
181 | inline EdgeDescriptor
|
---|
182 | dereference() const
|
---|
183 | {
|
---|
184 | return EdgeDescriptor((*this->base()).get_target(), m_src,
|
---|
185 | &this->base()->get_property());
|
---|
186 | }
|
---|
187 | VertexDescriptor m_src;
|
---|
188 | };
|
---|
189 |
|
---|
190 | //=========================================================================
|
---|
191 | // Undirected Edge Iterator Implementation
|
---|
192 |
|
---|
193 | template <class EdgeIter, class EdgeDescriptor, class Difference>
|
---|
194 | struct undirected_edge_iter
|
---|
195 | : iterator_adaptor<
|
---|
196 | undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
|
---|
197 | , EdgeIter
|
---|
198 | , EdgeDescriptor
|
---|
199 | , use_default
|
---|
200 | , EdgeDescriptor
|
---|
201 | , Difference
|
---|
202 | >
|
---|
203 | {
|
---|
204 | typedef iterator_adaptor<
|
---|
205 | undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
|
---|
206 | , EdgeIter
|
---|
207 | , EdgeDescriptor
|
---|
208 | , use_default
|
---|
209 | , EdgeDescriptor
|
---|
210 | , Difference
|
---|
211 | > super_t;
|
---|
212 |
|
---|
213 | undirected_edge_iter() {}
|
---|
214 |
|
---|
215 | explicit undirected_edge_iter(EdgeIter i)
|
---|
216 | : super_t(i) {}
|
---|
217 |
|
---|
218 | inline EdgeDescriptor
|
---|
219 | dereference() const {
|
---|
220 | return EdgeDescriptor(
|
---|
221 | (*this->base()).m_source
|
---|
222 | , (*this->base()).m_target
|
---|
223 | , &this->base()->get_property());
|
---|
224 | }
|
---|
225 | };
|
---|
226 |
|
---|
227 | //=========================================================================
|
---|
228 | // Edge Storage Types (stored in the out-edge/in-edge lists)
|
---|
229 |
|
---|
230 | template <class Vertex>
|
---|
231 | class stored_edge
|
---|
232 | : public boost::equality_comparable1< stored_edge<Vertex>,
|
---|
233 | boost::less_than_comparable1< stored_edge<Vertex> > >
|
---|
234 | {
|
---|
235 | public:
|
---|
236 | typedef no_property property_type;
|
---|
237 | inline stored_edge() { }
|
---|
238 | inline stored_edge(Vertex target, const no_property& = no_property())
|
---|
239 | : m_target(target) { }
|
---|
240 | // Need to write this explicitly so stored_edge_property can
|
---|
241 | // invoke Base::operator= (at least, for SGI MIPSPro compiler)
|
---|
242 | inline stored_edge& operator=(const stored_edge& x) {
|
---|
243 | m_target = x.m_target;
|
---|
244 | return *this;
|
---|
245 | }
|
---|
246 | inline Vertex& get_target() const { return m_target; }
|
---|
247 | inline const no_property& get_property() const { return s_prop; }
|
---|
248 | inline bool operator==(const stored_edge& x) const
|
---|
249 | { return m_target == x.get_target(); }
|
---|
250 | inline bool operator<(const stored_edge& x) const
|
---|
251 | { return m_target < x.get_target(); }
|
---|
252 | //protected: need to add hash<> as a friend
|
---|
253 | static no_property s_prop;
|
---|
254 | // Sometimes target not used as key in the set, and in that case
|
---|
255 | // it is ok to change the target.
|
---|
256 | mutable Vertex m_target;
|
---|
257 | };
|
---|
258 | template <class Vertex>
|
---|
259 | no_property stored_edge<Vertex>::s_prop;
|
---|
260 |
|
---|
261 | #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || defined(BOOST_NO_CXX11_DEFAULTED_FUNCTIONS)
|
---|
262 | template <class Vertex, class Property>
|
---|
263 | class stored_edge_property : public stored_edge<Vertex> {
|
---|
264 | typedef stored_edge_property self;
|
---|
265 | typedef stored_edge<Vertex> Base;
|
---|
266 | public:
|
---|
267 | typedef Property property_type;
|
---|
268 | inline stored_edge_property() { }
|
---|
269 | inline stored_edge_property(Vertex target,
|
---|
270 | const Property& p = Property())
|
---|
271 | : stored_edge<Vertex>(target), m_property(new Property(p)) { }
|
---|
272 | stored_edge_property(const self& x)
|
---|
273 | : Base(x), m_property(const_cast<self&>(x).m_property) { }
|
---|
274 | self& operator=(const self& x) {
|
---|
275 | Base::operator=(x);
|
---|
276 | m_property = const_cast<self&>(x).m_property;
|
---|
277 | return *this;
|
---|
278 | }
|
---|
279 | inline Property& get_property() { return *m_property; }
|
---|
280 | inline const Property& get_property() const { return *m_property; }
|
---|
281 | protected:
|
---|
282 | // Holding the property by-value causes edge-descriptor
|
---|
283 | // invalidation for add_edge() with EdgeList=vecS. Instead we
|
---|
284 | // hold a pointer to the property. std::auto_ptr is not
|
---|
285 | // a perfect fit for the job, but it is darn close.
|
---|
286 | std::auto_ptr<Property> m_property;
|
---|
287 | };
|
---|
288 | #else
|
---|
289 | template <class Vertex, class Property>
|
---|
290 | class stored_edge_property : public stored_edge<Vertex> {
|
---|
291 | typedef stored_edge_property self;
|
---|
292 | typedef stored_edge<Vertex> Base;
|
---|
293 | public:
|
---|
294 | typedef Property property_type;
|
---|
295 | inline stored_edge_property() { }
|
---|
296 | inline stored_edge_property(Vertex target,
|
---|
297 | const Property& p = Property())
|
---|
298 | : stored_edge<Vertex>(target), m_property(new Property(p)) { }
|
---|
299 | #if defined(BOOST_MSVC) || (defined(BOOST_GCC) && (BOOST_GCC / 100) < 406)
|
---|
300 | stored_edge_property(self&& x) : Base(static_cast< Base const& >(x)) {
|
---|
301 | m_property.swap(x.m_property);
|
---|
302 | }
|
---|
303 | stored_edge_property(self const& x) : Base(static_cast< Base const& >(x)) {
|
---|
304 | m_property.swap(const_cast<self&>(x).m_property);
|
---|
305 | }
|
---|
306 | self& operator=(self&& x) {
|
---|
307 | Base::operator=(static_cast< Base const& >(x));
|
---|
308 | m_property = std::move(x.m_property);
|
---|
309 | return *this;
|
---|
310 | }
|
---|
311 | self& operator=(self const& x) {
|
---|
312 | Base::operator=(static_cast< Base const& >(x));
|
---|
313 | m_property = std::move(const_cast<self&>(x).m_property);
|
---|
314 | return *this;
|
---|
315 | }
|
---|
316 | #else
|
---|
317 | stored_edge_property(self&& x) = default;
|
---|
318 | self& operator=(self&& x) = default;
|
---|
319 | #endif
|
---|
320 | inline Property& get_property() { return *m_property; }
|
---|
321 | inline const Property& get_property() const { return *m_property; }
|
---|
322 | protected:
|
---|
323 | std::unique_ptr<Property> m_property;
|
---|
324 | };
|
---|
325 | #endif
|
---|
326 |
|
---|
327 |
|
---|
328 | template <class Vertex, class Iter, class Property>
|
---|
329 | class stored_edge_iter
|
---|
330 | : public stored_edge<Vertex>
|
---|
331 | {
|
---|
332 | public:
|
---|
333 | typedef Property property_type;
|
---|
334 | inline stored_edge_iter() { }
|
---|
335 | inline stored_edge_iter(Vertex v)
|
---|
336 | : stored_edge<Vertex>(v) { }
|
---|
337 | inline stored_edge_iter(Vertex v, Iter i, void* = 0)
|
---|
338 | : stored_edge<Vertex>(v), m_iter(i) { }
|
---|
339 | inline Property& get_property() { return m_iter->get_property(); }
|
---|
340 | inline const Property& get_property() const {
|
---|
341 | return m_iter->get_property();
|
---|
342 | }
|
---|
343 | inline Iter get_iter() const { return m_iter; }
|
---|
344 | protected:
|
---|
345 | Iter m_iter;
|
---|
346 | };
|
---|
347 |
|
---|
348 | // For when the EdgeList is a std::vector.
|
---|
349 | // Want to make the iterator stable, so use an offset
|
---|
350 | // instead of an iterator into a std::vector
|
---|
351 | template <class Vertex, class EdgeVec, class Property>
|
---|
352 | class stored_ra_edge_iter
|
---|
353 | : public stored_edge<Vertex>
|
---|
354 | {
|
---|
355 | typedef typename EdgeVec::iterator Iter;
|
---|
356 | public:
|
---|
357 | typedef Property property_type;
|
---|
358 | inline stored_ra_edge_iter() { }
|
---|
359 | inline explicit stored_ra_edge_iter(Vertex v) // Only used for comparisons
|
---|
360 | : stored_edge<Vertex>(v), m_i(0), m_vec(0){ }
|
---|
361 | inline stored_ra_edge_iter(Vertex v, Iter i, EdgeVec* edge_vec)
|
---|
362 | : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
|
---|
363 | inline Property& get_property() { BOOST_ASSERT ((m_vec != 0)); return (*m_vec)[m_i].get_property(); }
|
---|
364 | inline const Property& get_property() const {
|
---|
365 | BOOST_ASSERT ((m_vec != 0));
|
---|
366 | return (*m_vec)[m_i].get_property();
|
---|
367 | }
|
---|
368 | inline Iter get_iter() const { BOOST_ASSERT ((m_vec != 0)); return m_vec->begin() + m_i; }
|
---|
369 | protected:
|
---|
370 | std::size_t m_i;
|
---|
371 | EdgeVec* m_vec;
|
---|
372 | };
|
---|
373 |
|
---|
374 | } // namespace detail
|
---|
375 |
|
---|
376 | template <class Tag, class Vertex, class Property>
|
---|
377 | const typename property_value<Property,Tag>::type&
|
---|
378 | get(Tag property_tag,
|
---|
379 | const detail::stored_edge_property<Vertex, Property>& e)
|
---|
380 | {
|
---|
381 | return get_property_value(e.get_property(), property_tag);
|
---|
382 | }
|
---|
383 |
|
---|
384 | template <class Tag, class Vertex, class Iter, class Property>
|
---|
385 | const typename property_value<Property,Tag>::type&
|
---|
386 | get(Tag property_tag,
|
---|
387 | const detail::stored_edge_iter<Vertex, Iter, Property>& e)
|
---|
388 | {
|
---|
389 | return get_property_value(e.get_property(), property_tag);
|
---|
390 | }
|
---|
391 |
|
---|
392 | template <class Tag, class Vertex, class EdgeVec, class Property>
|
---|
393 | const typename property_value<Property,Tag>::type&
|
---|
394 | get(Tag property_tag,
|
---|
395 | const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
|
---|
396 | {
|
---|
397 | return get_property_value(e.get_property(), property_tag);
|
---|
398 | }
|
---|
399 |
|
---|
400 | //=========================================================================
|
---|
401 | // Directed Edges Helper Class
|
---|
402 |
|
---|
403 | namespace detail {
|
---|
404 |
|
---|
405 | // O(E/V)
|
---|
406 | template <class edge_descriptor, class EdgeList, class StoredProperty>
|
---|
407 | inline void
|
---|
408 | remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
|
---|
409 | StoredProperty& p)
|
---|
410 | {
|
---|
411 | for (typename EdgeList::iterator i = el.begin();
|
---|
412 | i != el.end(); ++i)
|
---|
413 | if (&(*i).get_property() == &p) {
|
---|
414 | el.erase(i);
|
---|
415 | return;
|
---|
416 | }
|
---|
417 | }
|
---|
418 |
|
---|
419 | template <class incidence_iterator, class EdgeList, class Predicate>
|
---|
420 | inline void
|
---|
421 | remove_directed_edge_if_dispatch(incidence_iterator first,
|
---|
422 | incidence_iterator last,
|
---|
423 | EdgeList& el, Predicate pred,
|
---|
424 | boost::allow_parallel_edge_tag)
|
---|
425 | {
|
---|
426 | // remove_if
|
---|
427 | while (first != last && !pred(*first))
|
---|
428 | ++first;
|
---|
429 | incidence_iterator i = first;
|
---|
430 | if (first != last)
|
---|
431 | for (++i; i != last; ++i)
|
---|
432 | if (!pred(*i)) {
|
---|
433 | *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base());
|
---|
434 | ++first;
|
---|
435 | }
|
---|
436 | el.erase(first.base(), el.end());
|
---|
437 | }
|
---|
438 | template <class incidence_iterator, class EdgeList, class Predicate>
|
---|
439 | inline void
|
---|
440 | remove_directed_edge_if_dispatch(incidence_iterator first,
|
---|
441 | incidence_iterator last,
|
---|
442 | EdgeList& el,
|
---|
443 | Predicate pred,
|
---|
444 | boost::disallow_parallel_edge_tag)
|
---|
445 | {
|
---|
446 | for (incidence_iterator next = first;
|
---|
447 | first != last; first = next) {
|
---|
448 | ++next;
|
---|
449 | if (pred(*first))
|
---|
450 | el.erase( first.base() );
|
---|
451 | }
|
---|
452 | }
|
---|
453 |
|
---|
454 | template <class PropT, class Graph, class incidence_iterator,
|
---|
455 | class EdgeList, class Predicate>
|
---|
456 | inline void
|
---|
457 | undirected_remove_out_edge_if_dispatch(Graph& g,
|
---|
458 | incidence_iterator first,
|
---|
459 | incidence_iterator last,
|
---|
460 | EdgeList& el, Predicate pred,
|
---|
461 | boost::allow_parallel_edge_tag)
|
---|
462 | {
|
---|
463 | typedef typename Graph::global_edgelist_selector EdgeListS;
|
---|
464 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
465 |
|
---|
466 | // remove_if
|
---|
467 | while (first != last && !pred(*first))
|
---|
468 | ++first;
|
---|
469 | incidence_iterator i = first;
|
---|
470 | bool self_loop_removed = false;
|
---|
471 | if (first != last)
|
---|
472 | for (; i != last; ++i) {
|
---|
473 | if (self_loop_removed) {
|
---|
474 | /* With self loops, the descriptor will show up
|
---|
475 | * twice. The first time it will be removed, and now it
|
---|
476 | * will be skipped.
|
---|
477 | */
|
---|
478 | self_loop_removed = false;
|
---|
479 | }
|
---|
480 | else if (!pred(*i)) {
|
---|
481 | *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base());
|
---|
482 | ++first;
|
---|
483 | } else {
|
---|
484 | if (source(*i, g) == target(*i, g)) self_loop_removed = true;
|
---|
485 | else {
|
---|
486 | // Remove the edge from the target
|
---|
487 | detail::remove_directed_edge_dispatch
|
---|
488 | (*i,
|
---|
489 | g.out_edge_list(target(*i, g)),
|
---|
490 | *(PropT*)(*i).get_property());
|
---|
491 | }
|
---|
492 |
|
---|
493 | // Erase the edge property
|
---|
494 | g.m_edges.erase( (*i.base()).get_iter() );
|
---|
495 | }
|
---|
496 | }
|
---|
497 | el.erase(first.base(), el.end());
|
---|
498 | }
|
---|
499 | template <class PropT, class Graph, class incidence_iterator,
|
---|
500 | class EdgeList, class Predicate>
|
---|
501 | inline void
|
---|
502 | undirected_remove_out_edge_if_dispatch(Graph& g,
|
---|
503 | incidence_iterator first,
|
---|
504 | incidence_iterator last,
|
---|
505 | EdgeList& el,
|
---|
506 | Predicate pred,
|
---|
507 | boost::disallow_parallel_edge_tag)
|
---|
508 | {
|
---|
509 | typedef typename Graph::global_edgelist_selector EdgeListS;
|
---|
510 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
511 |
|
---|
512 | for (incidence_iterator next = first;
|
---|
513 | first != last; first = next) {
|
---|
514 | ++next;
|
---|
515 | if (pred(*first)) {
|
---|
516 | if (source(*first, g) != target(*first, g)) {
|
---|
517 | // Remove the edge from the target
|
---|
518 | detail::remove_directed_edge_dispatch
|
---|
519 | (*first,
|
---|
520 | g.out_edge_list(target(*first, g)),
|
---|
521 | *(PropT*)(*first).get_property());
|
---|
522 | }
|
---|
523 |
|
---|
524 | // Erase the edge property
|
---|
525 | g.m_edges.erase( (*first.base()).get_iter() );
|
---|
526 |
|
---|
527 | // Erase the edge in the source
|
---|
528 | el.erase( first.base() );
|
---|
529 | }
|
---|
530 | }
|
---|
531 | }
|
---|
532 |
|
---|
533 | // O(E/V)
|
---|
534 | template <class edge_descriptor, class EdgeList, class StoredProperty>
|
---|
535 | inline void
|
---|
536 | remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
|
---|
537 | no_property&)
|
---|
538 | {
|
---|
539 | for (typename EdgeList::iterator i = el.begin();
|
---|
540 | i != el.end(); ++i)
|
---|
541 | if ((*i).get_target() == e.m_target) {
|
---|
542 | el.erase(i);
|
---|
543 | return;
|
---|
544 | }
|
---|
545 | }
|
---|
546 |
|
---|
547 | } // namespace detail
|
---|
548 |
|
---|
549 | template <class Config>
|
---|
550 | struct directed_edges_helper {
|
---|
551 |
|
---|
552 | // Placement of these overloaded remove_edge() functions
|
---|
553 | // inside the class avoids a VC++ bug.
|
---|
554 |
|
---|
555 | // O(E/V)
|
---|
556 | inline void
|
---|
557 | remove_edge(typename Config::edge_descriptor e)
|
---|
558 | {
|
---|
559 | typedef typename Config::graph_type graph_type;
|
---|
560 | graph_type& g = static_cast<graph_type&>(*this);
|
---|
561 | typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
|
---|
562 | typedef typename Config::OutEdgeList::value_type::property_type PType;
|
---|
563 | detail::remove_directed_edge_dispatch(e, el,
|
---|
564 | *(PType*)e.get_property());
|
---|
565 | }
|
---|
566 |
|
---|
567 | // O(1)
|
---|
568 | inline void
|
---|
569 | remove_edge(typename Config::out_edge_iterator iter)
|
---|
570 | {
|
---|
571 | typedef typename Config::graph_type graph_type;
|
---|
572 | graph_type& g = static_cast<graph_type&>(*this);
|
---|
573 | typename Config::edge_descriptor e = *iter;
|
---|
574 | typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
|
---|
575 | el.erase(iter.base());
|
---|
576 | }
|
---|
577 |
|
---|
578 | };
|
---|
579 |
|
---|
580 | // O(1)
|
---|
581 | template <class Config>
|
---|
582 | inline std::pair<typename Config::edge_iterator,
|
---|
583 | typename Config::edge_iterator>
|
---|
584 | edges(const directed_edges_helper<Config>& g_)
|
---|
585 | {
|
---|
586 | typedef typename Config::graph_type graph_type;
|
---|
587 | typedef typename Config::edge_iterator edge_iterator;
|
---|
588 | const graph_type& cg = static_cast<const graph_type&>(g_);
|
---|
589 | graph_type& g = const_cast<graph_type&>(cg);
|
---|
590 | return std::make_pair( edge_iterator(g.vertex_set().begin(),
|
---|
591 | g.vertex_set().begin(),
|
---|
592 | g.vertex_set().end(), g),
|
---|
593 | edge_iterator(g.vertex_set().begin(),
|
---|
594 | g.vertex_set().end(),
|
---|
595 | g.vertex_set().end(), g) );
|
---|
596 | }
|
---|
597 |
|
---|
598 | //=========================================================================
|
---|
599 | // Directed Graph Helper Class
|
---|
600 |
|
---|
601 | struct adj_list_dir_traversal_tag :
|
---|
602 | public virtual vertex_list_graph_tag,
|
---|
603 | public virtual incidence_graph_tag,
|
---|
604 | public virtual adjacency_graph_tag,
|
---|
605 | public virtual edge_list_graph_tag { };
|
---|
606 |
|
---|
607 | template <class Config>
|
---|
608 | struct directed_graph_helper
|
---|
609 | : public directed_edges_helper<Config> {
|
---|
610 | typedef typename Config::edge_descriptor edge_descriptor;
|
---|
611 | typedef adj_list_dir_traversal_tag traversal_category;
|
---|
612 | };
|
---|
613 |
|
---|
614 | // O(E/V)
|
---|
615 | template <class Config>
|
---|
616 | inline void
|
---|
617 | remove_edge(typename Config::vertex_descriptor u,
|
---|
618 | typename Config::vertex_descriptor v,
|
---|
619 | directed_graph_helper<Config>& g_)
|
---|
620 | {
|
---|
621 | typedef typename Config::graph_type graph_type;
|
---|
622 | typedef typename Config::edge_parallel_category Cat;
|
---|
623 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
624 | detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
|
---|
625 | }
|
---|
626 |
|
---|
627 | template <class Config, class Predicate>
|
---|
628 | inline void
|
---|
629 | remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
---|
630 | directed_graph_helper<Config>& g_)
|
---|
631 | {
|
---|
632 | typedef typename Config::graph_type graph_type;
|
---|
633 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
634 | typename Config::out_edge_iterator first, last;
|
---|
635 | boost::tie(first, last) = out_edges(u, g);
|
---|
636 | typedef typename Config::edge_parallel_category edge_parallel_category;
|
---|
637 | detail::remove_directed_edge_if_dispatch
|
---|
638 | (first, last, g.out_edge_list(u), pred, edge_parallel_category());
|
---|
639 | }
|
---|
640 |
|
---|
641 | template <class Config, class Predicate>
|
---|
642 | inline void
|
---|
643 | remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
|
---|
644 | {
|
---|
645 | typedef typename Config::graph_type graph_type;
|
---|
646 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
647 |
|
---|
648 | typename Config::vertex_iterator vi, vi_end;
|
---|
649 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
|
---|
650 | remove_out_edge_if(*vi, pred, g);
|
---|
651 | }
|
---|
652 |
|
---|
653 | template <class EdgeOrIter, class Config>
|
---|
654 | inline void
|
---|
655 | remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
|
---|
656 | {
|
---|
657 | g_.remove_edge(e_or_iter);
|
---|
658 | }
|
---|
659 |
|
---|
660 | // O(V + E) for allow_parallel_edges
|
---|
661 | // O(V * log(E/V)) for disallow_parallel_edges
|
---|
662 | template <class Config>
|
---|
663 | inline void
|
---|
664 | clear_vertex(typename Config::vertex_descriptor u,
|
---|
665 | directed_graph_helper<Config>& g_)
|
---|
666 | {
|
---|
667 | typedef typename Config::graph_type graph_type;
|
---|
668 | typedef typename Config::edge_parallel_category Cat;
|
---|
669 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
670 | typename Config::vertex_iterator vi, viend;
|
---|
671 | for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
|
---|
672 | detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
|
---|
673 | g.out_edge_list(u).clear();
|
---|
674 | // clear() should be a req of Sequence and AssociativeContainer,
|
---|
675 | // or maybe just Container
|
---|
676 | }
|
---|
677 |
|
---|
678 | template <class Config>
|
---|
679 | inline void
|
---|
680 | clear_out_edges(typename Config::vertex_descriptor u,
|
---|
681 | directed_graph_helper<Config>& g_)
|
---|
682 | {
|
---|
683 | typedef typename Config::graph_type graph_type;
|
---|
684 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
685 | g.out_edge_list(u).clear();
|
---|
686 | // clear() should be a req of Sequence and AssociativeContainer,
|
---|
687 | // or maybe just Container
|
---|
688 | }
|
---|
689 |
|
---|
690 | // O(V), could do better...
|
---|
691 | template <class Config>
|
---|
692 | inline typename Config::edges_size_type
|
---|
693 | num_edges(const directed_graph_helper<Config>& g_)
|
---|
694 | {
|
---|
695 | typedef typename Config::graph_type graph_type;
|
---|
696 | const graph_type& g = static_cast<const graph_type&>(g_);
|
---|
697 | typename Config::edges_size_type num_e = 0;
|
---|
698 | typename Config::vertex_iterator vi, vi_end;
|
---|
699 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
|
---|
700 | num_e += out_degree(*vi, g);
|
---|
701 | return num_e;
|
---|
702 | }
|
---|
703 | // O(1) for allow_parallel_edge_tag
|
---|
704 | // O(log(E/V)) for disallow_parallel_edge_tag
|
---|
705 | template <class Config>
|
---|
706 | inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
|
---|
707 | add_edge(typename Config::vertex_descriptor u,
|
---|
708 | typename Config::vertex_descriptor v,
|
---|
709 | const typename Config::edge_property_type& p,
|
---|
710 | directed_graph_helper<Config>& g_)
|
---|
711 | {
|
---|
712 | typedef typename Config::edge_descriptor edge_descriptor;
|
---|
713 | typedef typename Config::graph_type graph_type;
|
---|
714 | typedef typename Config::StoredEdge StoredEdge;
|
---|
715 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
716 | typename Config::OutEdgeList::iterator i;
|
---|
717 | bool inserted;
|
---|
718 | boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
|
---|
719 | StoredEdge(v, p));
|
---|
720 | return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
|
---|
721 | inserted);
|
---|
722 | }
|
---|
723 | // Did not use default argument here because that
|
---|
724 | // causes Visual C++ to get confused.
|
---|
725 | template <class Config>
|
---|
726 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
727 | add_edge(typename Config::vertex_descriptor u,
|
---|
728 | typename Config::vertex_descriptor v,
|
---|
729 | directed_graph_helper<Config>& g_)
|
---|
730 | {
|
---|
731 | typename Config::edge_property_type p;
|
---|
732 | return add_edge(u, v, p, g_);
|
---|
733 | }
|
---|
734 | //=========================================================================
|
---|
735 | // Undirected Graph Helper Class
|
---|
736 |
|
---|
737 | template <class Config>
|
---|
738 | struct undirected_graph_helper;
|
---|
739 |
|
---|
740 | struct undir_adj_list_traversal_tag :
|
---|
741 | public virtual vertex_list_graph_tag,
|
---|
742 | public virtual incidence_graph_tag,
|
---|
743 | public virtual adjacency_graph_tag,
|
---|
744 | public virtual edge_list_graph_tag,
|
---|
745 | public virtual bidirectional_graph_tag { };
|
---|
746 |
|
---|
747 | namespace detail {
|
---|
748 |
|
---|
749 | // using class with specialization for dispatch is a VC++ workaround.
|
---|
750 | template <class StoredProperty>
|
---|
751 | struct remove_undirected_edge_dispatch {
|
---|
752 |
|
---|
753 | // O(E/V)
|
---|
754 | template <class edge_descriptor, class Config>
|
---|
755 | static void
|
---|
756 | apply(edge_descriptor e,
|
---|
757 | undirected_graph_helper<Config>& g_,
|
---|
758 | StoredProperty& p)
|
---|
759 | {
|
---|
760 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
761 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
762 |
|
---|
763 | typedef typename Config::graph_type graph_type;
|
---|
764 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
765 |
|
---|
766 | typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
|
---|
767 | typename Config::OutEdgeList::iterator out_i = out_el.begin();
|
---|
768 | typename Config::EdgeIter edge_iter_to_erase;
|
---|
769 | for (; out_i != out_el.end(); ++out_i)
|
---|
770 | if (&(*out_i).get_property() == &p) {
|
---|
771 | edge_iter_to_erase = (*out_i).get_iter();
|
---|
772 | out_el.erase(out_i);
|
---|
773 | break;
|
---|
774 | }
|
---|
775 | typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
|
---|
776 | typename Config::OutEdgeList::iterator in_i = in_el.begin();
|
---|
777 | for (; in_i != in_el.end(); ++in_i)
|
---|
778 | if (&(*in_i).get_property() == &p) {
|
---|
779 | in_el.erase(in_i);
|
---|
780 | break;
|
---|
781 | }
|
---|
782 | g.m_edges.erase(edge_iter_to_erase);
|
---|
783 | }
|
---|
784 | };
|
---|
785 |
|
---|
786 | template <>
|
---|
787 | struct remove_undirected_edge_dispatch<no_property> {
|
---|
788 | // O(E/V)
|
---|
789 | template <class edge_descriptor, class Config>
|
---|
790 | static void
|
---|
791 | apply(edge_descriptor e,
|
---|
792 | undirected_graph_helper<Config>& g_,
|
---|
793 | no_property&)
|
---|
794 | {
|
---|
795 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
796 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
797 |
|
---|
798 | typedef typename Config::graph_type graph_type;
|
---|
799 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
800 | no_property* p = (no_property*)e.get_property();
|
---|
801 | typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
|
---|
802 | typename Config::OutEdgeList::iterator out_i = out_el.begin();
|
---|
803 | typename Config::EdgeIter edge_iter_to_erase;
|
---|
804 | for (; out_i != out_el.end(); ++out_i)
|
---|
805 | if (&(*out_i).get_property() == p) {
|
---|
806 | edge_iter_to_erase = (*out_i).get_iter();
|
---|
807 | out_el.erase(out_i);
|
---|
808 | break;
|
---|
809 | }
|
---|
810 | typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
|
---|
811 | typename Config::OutEdgeList::iterator in_i = in_el.begin();
|
---|
812 | for (; in_i != in_el.end(); ++in_i)
|
---|
813 | if (&(*in_i).get_property() == p) {
|
---|
814 | in_el.erase(in_i);
|
---|
815 | break;
|
---|
816 | }
|
---|
817 | g.m_edges.erase(edge_iter_to_erase);
|
---|
818 | }
|
---|
819 | };
|
---|
820 |
|
---|
821 | // O(E/V)
|
---|
822 | template <class Graph, class EdgeList, class Vertex>
|
---|
823 | inline void
|
---|
824 | remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
|
---|
825 | boost::allow_parallel_edge_tag cat)
|
---|
826 | {
|
---|
827 | typedef typename Graph::global_edgelist_selector EdgeListS;
|
---|
828 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
829 |
|
---|
830 | typename EdgeList::iterator i = el.begin(), end = el.end();
|
---|
831 | for (; i != end; ++i) {
|
---|
832 | if ((*i).get_target() == v) {
|
---|
833 | // NOTE: Wihtout this skip, this loop will double-delete properties
|
---|
834 | // of loop edges. This solution is based on the observation that
|
---|
835 | // the incidence edges of a vertex with a loop are adjacent in the
|
---|
836 | // out edge list. This *may* actually hold for multisets also.
|
---|
837 | bool skip = (boost::next(i) != end && i->get_iter() == boost::next(i)->get_iter());
|
---|
838 | g.m_edges.erase((*i).get_iter());
|
---|
839 | if (skip) ++i;
|
---|
840 | }
|
---|
841 | }
|
---|
842 | detail::erase_from_incidence_list(el, v, cat);
|
---|
843 | }
|
---|
844 | // O(log(E/V))
|
---|
845 | template <class Graph, class EdgeList, class Vertex>
|
---|
846 | inline void
|
---|
847 | remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
|
---|
848 | boost::disallow_parallel_edge_tag)
|
---|
849 | {
|
---|
850 | typedef typename Graph::global_edgelist_selector EdgeListS;
|
---|
851 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
852 |
|
---|
853 | typedef typename EdgeList::value_type StoredEdge;
|
---|
854 | typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
|
---|
855 | if (i != end) {
|
---|
856 | g.m_edges.erase((*i).get_iter());
|
---|
857 | el.erase(i);
|
---|
858 | }
|
---|
859 | }
|
---|
860 |
|
---|
861 | } // namespace detail
|
---|
862 |
|
---|
863 | template <class Vertex, class EdgeProperty>
|
---|
864 | struct list_edge // short name due to VC++ truncation and linker problems
|
---|
865 | : public boost::detail::edge_base<boost::undirected_tag, Vertex>
|
---|
866 | {
|
---|
867 | typedef EdgeProperty property_type;
|
---|
868 | typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
|
---|
869 | list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
|
---|
870 | : Base(u, v), m_property(p) { }
|
---|
871 | EdgeProperty& get_property() { return m_property; }
|
---|
872 | const EdgeProperty& get_property() const { return m_property; }
|
---|
873 | // the following methods should never be used, but are needed
|
---|
874 | // to make SGI MIPSpro C++ happy
|
---|
875 | list_edge() { }
|
---|
876 | bool operator==(const list_edge&) const { return false; }
|
---|
877 | bool operator<(const list_edge&) const { return false; }
|
---|
878 | EdgeProperty m_property;
|
---|
879 | };
|
---|
880 |
|
---|
881 | template <class Config>
|
---|
882 | struct undirected_graph_helper {
|
---|
883 |
|
---|
884 | typedef undir_adj_list_traversal_tag traversal_category;
|
---|
885 |
|
---|
886 | // Placement of these overloaded remove_edge() functions
|
---|
887 | // inside the class avoids a VC++ bug.
|
---|
888 |
|
---|
889 | // O(E/V)
|
---|
890 | inline void
|
---|
891 | remove_edge(typename Config::edge_descriptor e)
|
---|
892 | {
|
---|
893 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
894 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
895 |
|
---|
896 | typedef typename Config::OutEdgeList::value_type::property_type PType;
|
---|
897 | detail::remove_undirected_edge_dispatch<PType>::apply
|
---|
898 | (e, *this, *(PType*)e.get_property());
|
---|
899 | }
|
---|
900 | // O(E/V)
|
---|
901 | inline void
|
---|
902 | remove_edge(typename Config::out_edge_iterator iter)
|
---|
903 | {
|
---|
904 | this->remove_edge(*iter);
|
---|
905 | }
|
---|
906 | };
|
---|
907 |
|
---|
908 | // Had to make these non-members to avoid accidental instantiation
|
---|
909 | // on SGI MIPSpro C++
|
---|
910 | template <class C>
|
---|
911 | inline typename C::InEdgeList&
|
---|
912 | in_edge_list(undirected_graph_helper<C>&,
|
---|
913 | typename C::vertex_descriptor v)
|
---|
914 | {
|
---|
915 | typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
---|
916 | return sv->m_out_edges;
|
---|
917 | }
|
---|
918 | template <class C>
|
---|
919 | inline const typename C::InEdgeList&
|
---|
920 | in_edge_list(const undirected_graph_helper<C>&,
|
---|
921 | typename C::vertex_descriptor v) {
|
---|
922 | typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
---|
923 | return sv->m_out_edges;
|
---|
924 | }
|
---|
925 |
|
---|
926 | // O(E/V)
|
---|
927 | template <class EdgeOrIter, class Config>
|
---|
928 | inline void
|
---|
929 | remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
|
---|
930 | {
|
---|
931 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
932 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
933 |
|
---|
934 | g_.remove_edge(e);
|
---|
935 | }
|
---|
936 |
|
---|
937 | // O(E/V) or O(log(E/V))
|
---|
938 | template <class Config>
|
---|
939 | void
|
---|
940 | remove_edge(typename Config::vertex_descriptor u,
|
---|
941 | typename Config::vertex_descriptor v,
|
---|
942 | undirected_graph_helper<Config>& g_)
|
---|
943 | {
|
---|
944 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
945 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
946 |
|
---|
947 | typedef typename Config::graph_type graph_type;
|
---|
948 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
949 | typedef typename Config::edge_parallel_category Cat;
|
---|
950 | detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
|
---|
951 | detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
|
---|
952 | }
|
---|
953 |
|
---|
954 | template <class Config, class Predicate>
|
---|
955 | void
|
---|
956 | remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
---|
957 | undirected_graph_helper<Config>& g_)
|
---|
958 | {
|
---|
959 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
960 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
961 |
|
---|
962 | typedef typename Config::graph_type graph_type;
|
---|
963 | typedef typename Config::OutEdgeList::value_type::property_type PropT;
|
---|
964 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
965 | typename Config::out_edge_iterator first, last;
|
---|
966 | boost::tie(first, last) = out_edges(u, g);
|
---|
967 | typedef typename Config::edge_parallel_category Cat;
|
---|
968 | detail::undirected_remove_out_edge_if_dispatch<PropT>
|
---|
969 | (g, first, last, g.out_edge_list(u), pred, Cat());
|
---|
970 | }
|
---|
971 | template <class Config, class Predicate>
|
---|
972 | void
|
---|
973 | remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
---|
974 | undirected_graph_helper<Config>& g_)
|
---|
975 | {
|
---|
976 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
977 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
978 |
|
---|
979 | remove_out_edge_if(u, pred, g_);
|
---|
980 | }
|
---|
981 |
|
---|
982 | // O(E/V * E) or O(log(E/V) * E)
|
---|
983 | template <class Predicate, class Config>
|
---|
984 | void
|
---|
985 | remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
|
---|
986 | {
|
---|
987 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
988 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
989 |
|
---|
990 | typedef typename Config::graph_type graph_type;
|
---|
991 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
992 | typename Config::edge_iterator ei, ei_end, next;
|
---|
993 | boost::tie(ei, ei_end) = edges(g);
|
---|
994 | for (next = ei; ei != ei_end; ei = next) {
|
---|
995 | ++next;
|
---|
996 | if (pred(*ei))
|
---|
997 | remove_edge(*ei, g);
|
---|
998 | }
|
---|
999 | }
|
---|
1000 |
|
---|
1001 | // O(1)
|
---|
1002 | template <class Config>
|
---|
1003 | inline std::pair<typename Config::edge_iterator,
|
---|
1004 | typename Config::edge_iterator>
|
---|
1005 | edges(const undirected_graph_helper<Config>& g_)
|
---|
1006 | {
|
---|
1007 | typedef typename Config::graph_type graph_type;
|
---|
1008 | typedef typename Config::edge_iterator edge_iterator;
|
---|
1009 | const graph_type& cg = static_cast<const graph_type&>(g_);
|
---|
1010 | graph_type& g = const_cast<graph_type&>(cg);
|
---|
1011 | return std::make_pair( edge_iterator(g.m_edges.begin()),
|
---|
1012 | edge_iterator(g.m_edges.end()) );
|
---|
1013 | }
|
---|
1014 | // O(1)
|
---|
1015 | template <class Config>
|
---|
1016 | inline typename Config::edges_size_type
|
---|
1017 | num_edges(const undirected_graph_helper<Config>& g_)
|
---|
1018 | {
|
---|
1019 | typedef typename Config::graph_type graph_type;
|
---|
1020 | const graph_type& g = static_cast<const graph_type&>(g_);
|
---|
1021 | return g.m_edges.size();
|
---|
1022 | }
|
---|
1023 | // O(E/V * E/V)
|
---|
1024 | template <class Config>
|
---|
1025 | inline void
|
---|
1026 | clear_vertex(typename Config::vertex_descriptor u,
|
---|
1027 | undirected_graph_helper<Config>& g_)
|
---|
1028 | {
|
---|
1029 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1030 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1031 |
|
---|
1032 | typedef typename Config::graph_type graph_type;
|
---|
1033 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1034 | while (true) {
|
---|
1035 | typename Config::out_edge_iterator ei, ei_end;
|
---|
1036 | boost::tie(ei, ei_end) = out_edges(u, g);
|
---|
1037 | if (ei == ei_end) break;
|
---|
1038 | remove_edge(*ei, g);
|
---|
1039 | }
|
---|
1040 | }
|
---|
1041 | // O(1) for allow_parallel_edge_tag
|
---|
1042 | // O(log(E/V)) for disallow_parallel_edge_tag
|
---|
1043 | template <class Config>
|
---|
1044 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
1045 | add_edge(typename Config::vertex_descriptor u,
|
---|
1046 | typename Config::vertex_descriptor v,
|
---|
1047 | const typename Config::edge_property_type& p,
|
---|
1048 | undirected_graph_helper<Config>& g_)
|
---|
1049 | {
|
---|
1050 | typedef typename Config::StoredEdge StoredEdge;
|
---|
1051 | typedef typename Config::edge_descriptor edge_descriptor;
|
---|
1052 | typedef typename Config::graph_type graph_type;
|
---|
1053 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1054 |
|
---|
1055 | bool inserted;
|
---|
1056 | typename Config::EdgeContainer::value_type e(u, v, p);
|
---|
1057 | typename Config::EdgeContainer::iterator p_iter
|
---|
1058 | = graph_detail::push(g.m_edges, e).first;
|
---|
1059 |
|
---|
1060 | typename Config::OutEdgeList::iterator i;
|
---|
1061 | boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
|
---|
1062 | StoredEdge(v, p_iter, &g.m_edges));
|
---|
1063 | if (inserted) {
|
---|
1064 | boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
|
---|
1065 | return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
|
---|
1066 | true);
|
---|
1067 | } else {
|
---|
1068 | g.m_edges.erase(p_iter);
|
---|
1069 | return std::make_pair
|
---|
1070 | (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
|
---|
1071 | }
|
---|
1072 | }
|
---|
1073 | template <class Config>
|
---|
1074 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
1075 | add_edge(typename Config::vertex_descriptor u,
|
---|
1076 | typename Config::vertex_descriptor v,
|
---|
1077 | undirected_graph_helper<Config>& g_)
|
---|
1078 | {
|
---|
1079 | typename Config::edge_property_type p;
|
---|
1080 | return add_edge(u, v, p, g_);
|
---|
1081 | }
|
---|
1082 |
|
---|
1083 | // O(1)
|
---|
1084 | template <class Config>
|
---|
1085 | inline typename Config::degree_size_type
|
---|
1086 | degree(typename Config::vertex_descriptor u,
|
---|
1087 | const undirected_graph_helper<Config>& g_)
|
---|
1088 | {
|
---|
1089 | typedef typename Config::graph_type Graph;
|
---|
1090 | const Graph& g = static_cast<const Graph&>(g_);
|
---|
1091 | return out_degree(u, g);
|
---|
1092 | }
|
---|
1093 |
|
---|
1094 | template <class Config>
|
---|
1095 | inline std::pair<typename Config::in_edge_iterator,
|
---|
1096 | typename Config::in_edge_iterator>
|
---|
1097 | in_edges(typename Config::vertex_descriptor u,
|
---|
1098 | const undirected_graph_helper<Config>& g_)
|
---|
1099 | {
|
---|
1100 | typedef typename Config::graph_type Graph;
|
---|
1101 | const Graph& cg = static_cast<const Graph&>(g_);
|
---|
1102 | Graph& g = const_cast<Graph&>(cg);
|
---|
1103 | typedef typename Config::in_edge_iterator in_edge_iterator;
|
---|
1104 | return
|
---|
1105 | std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
|
---|
1106 | in_edge_iterator(g.out_edge_list(u).end(), u));
|
---|
1107 | }
|
---|
1108 |
|
---|
1109 | template <class Config>
|
---|
1110 | inline typename Config::degree_size_type
|
---|
1111 | in_degree(typename Config::vertex_descriptor u,
|
---|
1112 | const undirected_graph_helper<Config>& g_)
|
---|
1113 | { return degree(u, g_); }
|
---|
1114 |
|
---|
1115 | //=========================================================================
|
---|
1116 | // Bidirectional Graph Helper Class
|
---|
1117 |
|
---|
1118 | struct bidir_adj_list_traversal_tag :
|
---|
1119 | public virtual vertex_list_graph_tag,
|
---|
1120 | public virtual incidence_graph_tag,
|
---|
1121 | public virtual adjacency_graph_tag,
|
---|
1122 | public virtual edge_list_graph_tag,
|
---|
1123 | public virtual bidirectional_graph_tag { };
|
---|
1124 |
|
---|
1125 | template <class Config>
|
---|
1126 | struct bidirectional_graph_helper
|
---|
1127 | : public directed_edges_helper<Config> {
|
---|
1128 | typedef bidir_adj_list_traversal_tag traversal_category;
|
---|
1129 | };
|
---|
1130 |
|
---|
1131 | // Had to make these non-members to avoid accidental instantiation
|
---|
1132 | // on SGI MIPSpro C++
|
---|
1133 | template <class C>
|
---|
1134 | inline typename C::InEdgeList&
|
---|
1135 | in_edge_list(bidirectional_graph_helper<C>&,
|
---|
1136 | typename C::vertex_descriptor v)
|
---|
1137 | {
|
---|
1138 | typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
---|
1139 | return sv->m_in_edges;
|
---|
1140 | }
|
---|
1141 | template <class C>
|
---|
1142 | inline const typename C::InEdgeList&
|
---|
1143 | in_edge_list(const bidirectional_graph_helper<C>&,
|
---|
1144 | typename C::vertex_descriptor v) {
|
---|
1145 | typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
---|
1146 | return sv->m_in_edges;
|
---|
1147 | }
|
---|
1148 |
|
---|
1149 | template <class Predicate, class Config>
|
---|
1150 | inline void
|
---|
1151 | remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
|
---|
1152 | {
|
---|
1153 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1154 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1155 |
|
---|
1156 | typedef typename Config::graph_type graph_type;
|
---|
1157 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1158 | typename Config::edge_iterator ei, ei_end, next;
|
---|
1159 | boost::tie(ei, ei_end) = edges(g);
|
---|
1160 | for (next = ei; ei != ei_end; ei = next) {
|
---|
1161 | ++next;
|
---|
1162 | if (pred(*ei))
|
---|
1163 | remove_edge(*ei, g);
|
---|
1164 | }
|
---|
1165 | }
|
---|
1166 |
|
---|
1167 | template <class Config>
|
---|
1168 | inline std::pair<typename Config::in_edge_iterator,
|
---|
1169 | typename Config::in_edge_iterator>
|
---|
1170 | in_edges(typename Config::vertex_descriptor u,
|
---|
1171 | const bidirectional_graph_helper<Config>& g_)
|
---|
1172 | {
|
---|
1173 | typedef typename Config::graph_type graph_type;
|
---|
1174 | const graph_type& cg = static_cast<const graph_type&>(g_);
|
---|
1175 | graph_type& g = const_cast<graph_type&>(cg);
|
---|
1176 | typedef typename Config::in_edge_iterator in_edge_iterator;
|
---|
1177 | return
|
---|
1178 | std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
|
---|
1179 | in_edge_iterator(in_edge_list(g, u).end(), u));
|
---|
1180 | }
|
---|
1181 |
|
---|
1182 | // O(1)
|
---|
1183 | template <class Config>
|
---|
1184 | inline std::pair<typename Config::edge_iterator,
|
---|
1185 | typename Config::edge_iterator>
|
---|
1186 | edges(const bidirectional_graph_helper<Config>& g_)
|
---|
1187 | {
|
---|
1188 | typedef typename Config::graph_type graph_type;
|
---|
1189 | typedef typename Config::edge_iterator edge_iterator;
|
---|
1190 | const graph_type& cg = static_cast<const graph_type&>(g_);
|
---|
1191 | graph_type& g = const_cast<graph_type&>(cg);
|
---|
1192 | return std::make_pair( edge_iterator(g.m_edges.begin()),
|
---|
1193 | edge_iterator(g.m_edges.end()) );
|
---|
1194 | }
|
---|
1195 |
|
---|
1196 | //=========================================================================
|
---|
1197 | // Bidirectional Graph Helper Class (with edge properties)
|
---|
1198 |
|
---|
1199 |
|
---|
1200 | template <class Config>
|
---|
1201 | struct bidirectional_graph_helper_with_property
|
---|
1202 | : public bidirectional_graph_helper<Config>
|
---|
1203 | {
|
---|
1204 | typedef typename Config::graph_type graph_type;
|
---|
1205 | typedef typename Config::out_edge_iterator out_edge_iterator;
|
---|
1206 |
|
---|
1207 | std::pair<out_edge_iterator, out_edge_iterator>
|
---|
1208 | get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
---|
1209 | const graph_type& g,
|
---|
1210 | void*)
|
---|
1211 | { return out_edges(source(e, g), g); }
|
---|
1212 |
|
---|
1213 | std::pair<out_edge_iterator, out_edge_iterator>
|
---|
1214 | get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
---|
1215 | const graph_type& g,
|
---|
1216 | setS*)
|
---|
1217 | { return edge_range(source(e, g), target(e, g), g); }
|
---|
1218 |
|
---|
1219 | std::pair<out_edge_iterator, out_edge_iterator>
|
---|
1220 | get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
---|
1221 | const graph_type& g,
|
---|
1222 | multisetS*)
|
---|
1223 | { return edge_range(source(e, g), target(e, g), g); }
|
---|
1224 |
|
---|
1225 | std::pair<out_edge_iterator, out_edge_iterator>
|
---|
1226 | get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
---|
1227 | const graph_type& g,
|
---|
1228 | hash_setS*)
|
---|
1229 | { return edge_range(source(e, g), target(e, g), g); }
|
---|
1230 |
|
---|
1231 | // Placement of these overloaded remove_edge() functions
|
---|
1232 | // inside the class avoids a VC++ bug.
|
---|
1233 |
|
---|
1234 | // O(E/V) or O(log(E/V))
|
---|
1235 | void
|
---|
1236 | remove_edge(typename Config::edge_descriptor e)
|
---|
1237 | {
|
---|
1238 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1239 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1240 |
|
---|
1241 | graph_type& g = static_cast<graph_type&>(*this);
|
---|
1242 |
|
---|
1243 | typedef typename Config::edgelist_selector OutEdgeListS;
|
---|
1244 |
|
---|
1245 | std::pair<out_edge_iterator, out_edge_iterator> rng =
|
---|
1246 | get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
|
---|
1247 | rng.first = std::find(rng.first, rng.second, e);
|
---|
1248 | BOOST_ASSERT(rng.first != rng.second);
|
---|
1249 | remove_edge(rng.first);
|
---|
1250 | }
|
---|
1251 |
|
---|
1252 | inline void
|
---|
1253 | remove_edge(typename Config::out_edge_iterator iter)
|
---|
1254 | {
|
---|
1255 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1256 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1257 |
|
---|
1258 | typedef typename Config::graph_type graph_type;
|
---|
1259 | graph_type& g = static_cast<graph_type&>(*this);
|
---|
1260 | typename Config::edge_descriptor e = *iter;
|
---|
1261 | typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
|
---|
1262 | typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
|
---|
1263 | typedef typename Config::OutEdgeList::value_type::property_type PType;
|
---|
1264 | PType& p = *(PType*)e.get_property();
|
---|
1265 | detail::remove_directed_edge_dispatch(*iter, iel, p);
|
---|
1266 | g.m_edges.erase(iter.base()->get_iter());
|
---|
1267 | oel.erase(iter.base());
|
---|
1268 | }
|
---|
1269 | };
|
---|
1270 |
|
---|
1271 | // O(E/V) for allow_parallel_edge_tag
|
---|
1272 | // O(log(E/V)) for disallow_parallel_edge_tag
|
---|
1273 | template <class Config>
|
---|
1274 | inline void
|
---|
1275 | remove_edge(typename Config::vertex_descriptor u,
|
---|
1276 | typename Config::vertex_descriptor v,
|
---|
1277 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1278 | {
|
---|
1279 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1280 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1281 |
|
---|
1282 | typedef typename Config::graph_type graph_type;
|
---|
1283 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1284 | typedef typename Config::edge_parallel_category Cat;
|
---|
1285 | detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
|
---|
1286 | detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
|
---|
1287 | }
|
---|
1288 |
|
---|
1289 | // O(E/V) or O(log(E/V))
|
---|
1290 | template <class EdgeOrIter, class Config>
|
---|
1291 | inline void
|
---|
1292 | remove_edge(EdgeOrIter e,
|
---|
1293 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1294 | {
|
---|
1295 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1296 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1297 |
|
---|
1298 | g_.remove_edge(e);
|
---|
1299 | }
|
---|
1300 |
|
---|
1301 | template <class Config, class Predicate>
|
---|
1302 | inline void
|
---|
1303 | remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
---|
1304 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1305 | {
|
---|
1306 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1307 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1308 |
|
---|
1309 | typedef typename Config::graph_type graph_type;
|
---|
1310 | typedef typename Config::OutEdgeList::value_type::property_type PropT;
|
---|
1311 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1312 |
|
---|
1313 | typedef typename Config::EdgeIter EdgeIter;
|
---|
1314 | typedef std::vector<EdgeIter> Garbage;
|
---|
1315 | Garbage garbage;
|
---|
1316 |
|
---|
1317 | // First remove the edges from the targets' in-edge lists and
|
---|
1318 | // from the graph's edge set list.
|
---|
1319 | typename Config::out_edge_iterator out_i, out_end;
|
---|
1320 | for (boost::tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
|
---|
1321 | if (pred(*out_i)) {
|
---|
1322 | detail::remove_directed_edge_dispatch
|
---|
1323 | (*out_i, in_edge_list(g, target(*out_i, g)),
|
---|
1324 | *(PropT*)(*out_i).get_property());
|
---|
1325 | // Put in garbage to delete later. Will need the properties
|
---|
1326 | // for the remove_if of the out-edges.
|
---|
1327 | garbage.push_back((*out_i.base()).get_iter());
|
---|
1328 | }
|
---|
1329 |
|
---|
1330 | // Now remove the edges from this out-edge list.
|
---|
1331 | typename Config::out_edge_iterator first, last;
|
---|
1332 | boost::tie(first, last) = out_edges(u, g);
|
---|
1333 | typedef typename Config::edge_parallel_category Cat;
|
---|
1334 | detail::remove_directed_edge_if_dispatch
|
---|
1335 | (first, last, g.out_edge_list(u), pred, Cat());
|
---|
1336 |
|
---|
1337 | // Now delete the edge properties from the g.m_edges list
|
---|
1338 | for (typename Garbage::iterator i = garbage.begin();
|
---|
1339 | i != garbage.end(); ++i)
|
---|
1340 | g.m_edges.erase(*i);
|
---|
1341 | }
|
---|
1342 | template <class Config, class Predicate>
|
---|
1343 | inline void
|
---|
1344 | remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
|
---|
1345 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1346 | {
|
---|
1347 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1348 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1349 |
|
---|
1350 | typedef typename Config::graph_type graph_type;
|
---|
1351 | typedef typename Config::OutEdgeList::value_type::property_type PropT;
|
---|
1352 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1353 |
|
---|
1354 | typedef typename Config::EdgeIter EdgeIter;
|
---|
1355 | typedef std::vector<EdgeIter> Garbage;
|
---|
1356 | Garbage garbage;
|
---|
1357 |
|
---|
1358 | // First remove the edges from the sources' out-edge lists and
|
---|
1359 | // from the graph's edge set list.
|
---|
1360 | typename Config::in_edge_iterator in_i, in_end;
|
---|
1361 | for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
|
---|
1362 | if (pred(*in_i)) {
|
---|
1363 | typename Config::vertex_descriptor u = source(*in_i, g);
|
---|
1364 | detail::remove_directed_edge_dispatch
|
---|
1365 | (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
|
---|
1366 | // Put in garbage to delete later. Will need the properties
|
---|
1367 | // for the remove_if of the out-edges.
|
---|
1368 | garbage.push_back((*in_i.base()).get_iter());
|
---|
1369 | }
|
---|
1370 | // Now remove the edges from this in-edge list.
|
---|
1371 | typename Config::in_edge_iterator first, last;
|
---|
1372 | boost::tie(first, last) = in_edges(v, g);
|
---|
1373 | typedef typename Config::edge_parallel_category Cat;
|
---|
1374 | detail::remove_directed_edge_if_dispatch
|
---|
1375 | (first, last, in_edge_list(g, v), pred, Cat());
|
---|
1376 |
|
---|
1377 | // Now delete the edge properties from the g.m_edges list
|
---|
1378 | for (typename Garbage::iterator i = garbage.begin();
|
---|
1379 | i != garbage.end(); ++i)
|
---|
1380 | g.m_edges.erase(*i);
|
---|
1381 | }
|
---|
1382 |
|
---|
1383 | // O(1)
|
---|
1384 | template <class Config>
|
---|
1385 | inline typename Config::edges_size_type
|
---|
1386 | num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1387 | {
|
---|
1388 | typedef typename Config::graph_type graph_type;
|
---|
1389 | const graph_type& g = static_cast<const graph_type&>(g_);
|
---|
1390 | return g.m_edges.size();
|
---|
1391 | }
|
---|
1392 | // O(E/V * E/V) for allow_parallel_edge_tag
|
---|
1393 | // O(E/V * log(E/V)) for disallow_parallel_edge_tag
|
---|
1394 | template <class Config>
|
---|
1395 | inline void
|
---|
1396 | clear_vertex(typename Config::vertex_descriptor u,
|
---|
1397 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1398 | {
|
---|
1399 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1400 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1401 |
|
---|
1402 | typedef typename Config::graph_type graph_type;
|
---|
1403 | typedef typename Config::edge_parallel_category Cat;
|
---|
1404 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1405 | typename Config::OutEdgeList& el = g.out_edge_list(u);
|
---|
1406 | typename Config::OutEdgeList::iterator
|
---|
1407 | ei = el.begin(), ei_end = el.end();
|
---|
1408 | for (; ei != ei_end; ++ei) {
|
---|
1409 | detail::erase_from_incidence_list
|
---|
1410 | (in_edge_list(g, (*ei).get_target()), u, Cat());
|
---|
1411 | g.m_edges.erase((*ei).get_iter());
|
---|
1412 | }
|
---|
1413 | typename Config::InEdgeList& in_el = in_edge_list(g, u);
|
---|
1414 | typename Config::InEdgeList::iterator
|
---|
1415 | in_ei = in_el.begin(), in_ei_end = in_el.end();
|
---|
1416 | for (; in_ei != in_ei_end; ++in_ei) {
|
---|
1417 | detail::erase_from_incidence_list
|
---|
1418 | (g.out_edge_list((*in_ei).get_target()), u, Cat());
|
---|
1419 | g.m_edges.erase((*in_ei).get_iter());
|
---|
1420 | }
|
---|
1421 | g.out_edge_list(u).clear();
|
---|
1422 | in_edge_list(g, u).clear();
|
---|
1423 | }
|
---|
1424 |
|
---|
1425 | template <class Config>
|
---|
1426 | inline void
|
---|
1427 | clear_out_edges(typename Config::vertex_descriptor u,
|
---|
1428 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1429 | {
|
---|
1430 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1431 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1432 |
|
---|
1433 | typedef typename Config::graph_type graph_type;
|
---|
1434 | typedef typename Config::edge_parallel_category Cat;
|
---|
1435 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1436 | typename Config::OutEdgeList& el = g.out_edge_list(u);
|
---|
1437 | typename Config::OutEdgeList::iterator
|
---|
1438 | ei = el.begin(), ei_end = el.end();
|
---|
1439 | for (; ei != ei_end; ++ei) {
|
---|
1440 | detail::erase_from_incidence_list
|
---|
1441 | (in_edge_list(g, (*ei).get_target()), u, Cat());
|
---|
1442 | g.m_edges.erase((*ei).get_iter());
|
---|
1443 | }
|
---|
1444 | g.out_edge_list(u).clear();
|
---|
1445 | }
|
---|
1446 |
|
---|
1447 | template <class Config>
|
---|
1448 | inline void
|
---|
1449 | clear_in_edges(typename Config::vertex_descriptor u,
|
---|
1450 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1451 | {
|
---|
1452 | typedef typename Config::global_edgelist_selector EdgeListS;
|
---|
1453 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1454 |
|
---|
1455 | typedef typename Config::graph_type graph_type;
|
---|
1456 | typedef typename Config::edge_parallel_category Cat;
|
---|
1457 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1458 | typename Config::InEdgeList& in_el = in_edge_list(g, u);
|
---|
1459 | typename Config::InEdgeList::iterator
|
---|
1460 | in_ei = in_el.begin(), in_ei_end = in_el.end();
|
---|
1461 | for (; in_ei != in_ei_end; ++in_ei) {
|
---|
1462 | detail::erase_from_incidence_list
|
---|
1463 | (g.out_edge_list((*in_ei).get_target()), u, Cat());
|
---|
1464 | g.m_edges.erase((*in_ei).get_iter());
|
---|
1465 | }
|
---|
1466 | in_edge_list(g, u).clear();
|
---|
1467 | }
|
---|
1468 |
|
---|
1469 | // O(1) for allow_parallel_edge_tag
|
---|
1470 | // O(log(E/V)) for disallow_parallel_edge_tag
|
---|
1471 | template <class Config>
|
---|
1472 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
1473 | add_edge(typename Config::vertex_descriptor u,
|
---|
1474 | typename Config::vertex_descriptor v,
|
---|
1475 | const typename Config::edge_property_type& p,
|
---|
1476 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1477 | {
|
---|
1478 | typedef typename Config::graph_type graph_type;
|
---|
1479 | graph_type& g = static_cast<graph_type&>(g_);
|
---|
1480 | typedef typename Config::edge_descriptor edge_descriptor;
|
---|
1481 | typedef typename Config::StoredEdge StoredEdge;
|
---|
1482 | bool inserted;
|
---|
1483 | typename Config::EdgeContainer::value_type e(u, v, p);
|
---|
1484 | typename Config::EdgeContainer::iterator p_iter
|
---|
1485 | = graph_detail::push(g.m_edges, e).first;
|
---|
1486 | typename Config::OutEdgeList::iterator i;
|
---|
1487 | boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
|
---|
1488 | StoredEdge(v, p_iter, &g.m_edges));
|
---|
1489 | if (inserted) {
|
---|
1490 | boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
|
---|
1491 | return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
|
---|
1492 | true);
|
---|
1493 | } else {
|
---|
1494 | g.m_edges.erase(p_iter);
|
---|
1495 | return std::make_pair(edge_descriptor(u, v,
|
---|
1496 | &i->get_iter()->get_property()),
|
---|
1497 | false);
|
---|
1498 | }
|
---|
1499 | }
|
---|
1500 |
|
---|
1501 | template <class Config>
|
---|
1502 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
1503 | add_edge(typename Config::vertex_descriptor u,
|
---|
1504 | typename Config::vertex_descriptor v,
|
---|
1505 | bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1506 | {
|
---|
1507 | typename Config::edge_property_type p;
|
---|
1508 | return add_edge(u, v, p, g_);
|
---|
1509 | }
|
---|
1510 | // O(1)
|
---|
1511 | template <class Config>
|
---|
1512 | inline typename Config::degree_size_type
|
---|
1513 | degree(typename Config::vertex_descriptor u,
|
---|
1514 | const bidirectional_graph_helper_with_property<Config>& g_)
|
---|
1515 | {
|
---|
1516 | typedef typename Config::graph_type graph_type;
|
---|
1517 | const graph_type& g = static_cast<const graph_type&>(g_);
|
---|
1518 | return in_degree(u, g) + out_degree(u, g);
|
---|
1519 | }
|
---|
1520 |
|
---|
1521 | //=========================================================================
|
---|
1522 | // Adjacency List Helper Class
|
---|
1523 |
|
---|
1524 | template <class Config, class Base>
|
---|
1525 | struct adj_list_helper : public Base
|
---|
1526 | {
|
---|
1527 | typedef typename Config::graph_type AdjList;
|
---|
1528 | typedef typename Config::vertex_descriptor vertex_descriptor;
|
---|
1529 | typedef typename Config::edge_descriptor edge_descriptor;
|
---|
1530 | typedef typename Config::out_edge_iterator out_edge_iterator;
|
---|
1531 | typedef typename Config::in_edge_iterator in_edge_iterator;
|
---|
1532 | typedef typename Config::adjacency_iterator adjacency_iterator;
|
---|
1533 | typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
|
---|
1534 | typedef typename Config::vertex_iterator vertex_iterator;
|
---|
1535 | typedef typename Config::edge_iterator edge_iterator;
|
---|
1536 | typedef typename Config::directed_category directed_category;
|
---|
1537 | typedef typename Config::edge_parallel_category edge_parallel_category;
|
---|
1538 | typedef typename Config::vertices_size_type vertices_size_type;
|
---|
1539 | typedef typename Config::edges_size_type edges_size_type;
|
---|
1540 | typedef typename Config::degree_size_type degree_size_type;
|
---|
1541 | typedef typename Config::StoredEdge StoredEdge;
|
---|
1542 | typedef typename Config::vertex_property_type vertex_property_type;
|
---|
1543 | typedef typename Config::edge_property_type edge_property_type;
|
---|
1544 | typedef typename Config::graph_property_type graph_property_type;
|
---|
1545 |
|
---|
1546 | typedef typename Config::global_edgelist_selector
|
---|
1547 | global_edgelist_selector;
|
---|
1548 |
|
---|
1549 | typedef typename lookup_one_property<vertex_property_type, vertex_bundle_t>::type vertex_bundled;
|
---|
1550 | typedef typename lookup_one_property<edge_property_type, edge_bundle_t>::type edge_bundled;
|
---|
1551 | typedef typename lookup_one_property<graph_property_type, graph_bundle_t>::type graph_bundled;
|
---|
1552 | };
|
---|
1553 |
|
---|
1554 | template <class Config, class Base>
|
---|
1555 | inline std::pair<typename Config::adjacency_iterator,
|
---|
1556 | typename Config::adjacency_iterator>
|
---|
1557 | adjacent_vertices(typename Config::vertex_descriptor u,
|
---|
1558 | const adj_list_helper<Config, Base>& g_)
|
---|
1559 | {
|
---|
1560 | typedef typename Config::graph_type AdjList;
|
---|
1561 | const AdjList& cg = static_cast<const AdjList&>(g_);
|
---|
1562 | AdjList& g = const_cast<AdjList&>(cg);
|
---|
1563 | typedef typename Config::adjacency_iterator adjacency_iterator;
|
---|
1564 | typename Config::out_edge_iterator first, last;
|
---|
1565 | boost::tie(first, last) = out_edges(u, g);
|
---|
1566 | return std::make_pair(adjacency_iterator(first, &g),
|
---|
1567 | adjacency_iterator(last, &g));
|
---|
1568 | }
|
---|
1569 | template <class Config, class Base>
|
---|
1570 | inline std::pair<typename Config::inv_adjacency_iterator,
|
---|
1571 | typename Config::inv_adjacency_iterator>
|
---|
1572 | inv_adjacent_vertices(typename Config::vertex_descriptor u,
|
---|
1573 | const adj_list_helper<Config, Base>& g_)
|
---|
1574 | {
|
---|
1575 | typedef typename Config::graph_type AdjList;
|
---|
1576 | const AdjList& cg = static_cast<const AdjList&>(g_);
|
---|
1577 | AdjList& g = const_cast<AdjList&>(cg);
|
---|
1578 | typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
|
---|
1579 | typename Config::in_edge_iterator first, last;
|
---|
1580 | boost::tie(first, last) = in_edges(u, g);
|
---|
1581 | return std::make_pair(inv_adjacency_iterator(first, &g),
|
---|
1582 | inv_adjacency_iterator(last, &g));
|
---|
1583 | }
|
---|
1584 | template <class Config, class Base>
|
---|
1585 | inline std::pair<typename Config::out_edge_iterator,
|
---|
1586 | typename Config::out_edge_iterator>
|
---|
1587 | out_edges(typename Config::vertex_descriptor u,
|
---|
1588 | const adj_list_helper<Config, Base>& g_)
|
---|
1589 | {
|
---|
1590 | typedef typename Config::graph_type AdjList;
|
---|
1591 | typedef typename Config::out_edge_iterator out_edge_iterator;
|
---|
1592 | const AdjList& cg = static_cast<const AdjList&>(g_);
|
---|
1593 | AdjList& g = const_cast<AdjList&>(cg);
|
---|
1594 | return
|
---|
1595 | std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
|
---|
1596 | out_edge_iterator(g.out_edge_list(u).end(), u));
|
---|
1597 | }
|
---|
1598 | template <class Config, class Base>
|
---|
1599 | inline std::pair<typename Config::vertex_iterator,
|
---|
1600 | typename Config::vertex_iterator>
|
---|
1601 | vertices(const adj_list_helper<Config, Base>& g_)
|
---|
1602 | {
|
---|
1603 | typedef typename Config::graph_type AdjList;
|
---|
1604 | const AdjList& cg = static_cast<const AdjList&>(g_);
|
---|
1605 | AdjList& g = const_cast<AdjList&>(cg);
|
---|
1606 | return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
|
---|
1607 | }
|
---|
1608 | template <class Config, class Base>
|
---|
1609 | inline typename Config::vertices_size_type
|
---|
1610 | num_vertices(const adj_list_helper<Config, Base>& g_)
|
---|
1611 | {
|
---|
1612 | typedef typename Config::graph_type AdjList;
|
---|
1613 | const AdjList& g = static_cast<const AdjList&>(g_);
|
---|
1614 | return g.vertex_set().size();
|
---|
1615 | }
|
---|
1616 | template <class Config, class Base>
|
---|
1617 | inline typename Config::degree_size_type
|
---|
1618 | out_degree(typename Config::vertex_descriptor u,
|
---|
1619 | const adj_list_helper<Config, Base>& g_)
|
---|
1620 | {
|
---|
1621 | typedef typename Config::graph_type AdjList;
|
---|
1622 | const AdjList& g = static_cast<const AdjList&>(g_);
|
---|
1623 | return g.out_edge_list(u).size();
|
---|
1624 | }
|
---|
1625 | template <class Config, class Base>
|
---|
1626 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
1627 | edge(typename Config::vertex_descriptor u,
|
---|
1628 | typename Config::vertex_descriptor v,
|
---|
1629 | const adj_list_helper<Config, Base>& g_)
|
---|
1630 | {
|
---|
1631 | typedef typename Config::graph_type Graph;
|
---|
1632 | typedef typename Config::StoredEdge StoredEdge;
|
---|
1633 | const Graph& cg = static_cast<const Graph&>(g_);
|
---|
1634 | const typename Config::OutEdgeList& el = cg.out_edge_list(u);
|
---|
1635 | typename Config::OutEdgeList::const_iterator it = graph_detail::
|
---|
1636 | find(el, StoredEdge(v));
|
---|
1637 | return std::make_pair(
|
---|
1638 | typename Config::edge_descriptor
|
---|
1639 | (u, v, (it == el.end() ? 0 : &(*it).get_property())),
|
---|
1640 | (it != el.end()));
|
---|
1641 | }
|
---|
1642 |
|
---|
1643 | template <class Config, class Base>
|
---|
1644 | inline std::pair<typename Config::out_edge_iterator,
|
---|
1645 | typename Config::out_edge_iterator>
|
---|
1646 | edge_range(typename Config::vertex_descriptor u,
|
---|
1647 | typename Config::vertex_descriptor v,
|
---|
1648 | const adj_list_helper<Config, Base>& g_)
|
---|
1649 | {
|
---|
1650 | typedef typename Config::graph_type Graph;
|
---|
1651 | typedef typename Config::StoredEdge StoredEdge;
|
---|
1652 | const Graph& cg = static_cast<const Graph&>(g_);
|
---|
1653 | Graph& g = const_cast<Graph&>(cg);
|
---|
1654 | typedef typename Config::out_edge_iterator out_edge_iterator;
|
---|
1655 | typename Config::OutEdgeList& el = g.out_edge_list(u);
|
---|
1656 | typename Config::OutEdgeList::iterator first, last;
|
---|
1657 | typename Config::EdgeContainer fake_edge_container;
|
---|
1658 | boost::tie(first, last) = graph_detail::
|
---|
1659 | equal_range(el, StoredEdge(v));
|
---|
1660 | return std::make_pair(out_edge_iterator(first, u),
|
---|
1661 | out_edge_iterator(last, u));
|
---|
1662 | }
|
---|
1663 |
|
---|
1664 | template <class Config>
|
---|
1665 | inline typename Config::degree_size_type
|
---|
1666 | in_degree(typename Config::vertex_descriptor u,
|
---|
1667 | const directed_edges_helper<Config>& g_)
|
---|
1668 | {
|
---|
1669 | typedef typename Config::graph_type Graph;
|
---|
1670 | const Graph& cg = static_cast<const Graph&>(g_);
|
---|
1671 | Graph& g = const_cast<Graph&>(cg);
|
---|
1672 | return in_edge_list(g, u).size();
|
---|
1673 | }
|
---|
1674 |
|
---|
1675 | namespace detail {
|
---|
1676 | template <class Config, class Base, class Property>
|
---|
1677 | inline
|
---|
1678 | typename boost::property_map<typename Config::graph_type,
|
---|
1679 | Property>::type
|
---|
1680 | get_dispatch(adj_list_helper<Config,Base>&, Property p,
|
---|
1681 | boost::edge_property_tag) {
|
---|
1682 | typedef typename Config::graph_type Graph;
|
---|
1683 | typedef typename boost::property_map<Graph, Property>::type PA;
|
---|
1684 | return PA(p);
|
---|
1685 | }
|
---|
1686 | template <class Config, class Base, class Property>
|
---|
1687 | inline
|
---|
1688 | typename boost::property_map<typename Config::graph_type,
|
---|
1689 | Property>::const_type
|
---|
1690 | get_dispatch(const adj_list_helper<Config,Base>&, Property p,
|
---|
1691 | boost::edge_property_tag) {
|
---|
1692 | typedef typename Config::graph_type Graph;
|
---|
1693 | typedef typename boost::property_map<Graph, Property>::const_type PA;
|
---|
1694 | return PA(p);
|
---|
1695 | }
|
---|
1696 |
|
---|
1697 | template <class Config, class Base, class Property>
|
---|
1698 | inline
|
---|
1699 | typename boost::property_map<typename Config::graph_type,
|
---|
1700 | Property>::type
|
---|
1701 | get_dispatch(adj_list_helper<Config,Base>& g, Property p,
|
---|
1702 | boost::vertex_property_tag) {
|
---|
1703 | typedef typename Config::graph_type Graph;
|
---|
1704 | typedef typename boost::property_map<Graph, Property>::type PA;
|
---|
1705 | return PA(&static_cast<Graph&>(g), p);
|
---|
1706 | }
|
---|
1707 | template <class Config, class Base, class Property>
|
---|
1708 | inline
|
---|
1709 | typename boost::property_map<typename Config::graph_type,
|
---|
1710 | Property>::const_type
|
---|
1711 | get_dispatch(const adj_list_helper<Config, Base>& g, Property p,
|
---|
1712 | boost::vertex_property_tag) {
|
---|
1713 | typedef typename Config::graph_type Graph;
|
---|
1714 | typedef typename boost::property_map<Graph, Property>::const_type PA;
|
---|
1715 | const Graph& cg = static_cast<const Graph&>(g);
|
---|
1716 | return PA(&cg, p);
|
---|
1717 | }
|
---|
1718 |
|
---|
1719 | } // namespace detail
|
---|
1720 |
|
---|
1721 | // Implementation of the PropertyGraph interface
|
---|
1722 | template <class Config, class Base, class Property>
|
---|
1723 | inline
|
---|
1724 | typename boost::property_map<typename Config::graph_type, Property>::type
|
---|
1725 | get(Property p, adj_list_helper<Config, Base>& g) {
|
---|
1726 | typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
|
---|
1727 | return detail::get_dispatch(g, p, Kind());
|
---|
1728 | }
|
---|
1729 | template <class Config, class Base, class Property>
|
---|
1730 | inline
|
---|
1731 | typename boost::property_map<typename Config::graph_type,
|
---|
1732 | Property>::const_type
|
---|
1733 | get(Property p, const adj_list_helper<Config, Base>& g) {
|
---|
1734 | typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
|
---|
1735 | return detail::get_dispatch(g, p, Kind());
|
---|
1736 | }
|
---|
1737 |
|
---|
1738 | template <class Config, class Base, class Property, class Key>
|
---|
1739 | inline
|
---|
1740 | typename boost::property_traits<
|
---|
1741 | typename boost::property_map<typename Config::graph_type,
|
---|
1742 | Property>::type
|
---|
1743 | >::reference
|
---|
1744 | get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
|
---|
1745 | return get(get(p, g), key);
|
---|
1746 | }
|
---|
1747 |
|
---|
1748 | template <class Config, class Base, class Property, class Key>
|
---|
1749 | inline
|
---|
1750 | typename boost::property_traits<
|
---|
1751 | typename boost::property_map<typename Config::graph_type,
|
---|
1752 | Property>::const_type
|
---|
1753 | >::reference
|
---|
1754 | get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
|
---|
1755 | return get(get(p, g), key);
|
---|
1756 | }
|
---|
1757 |
|
---|
1758 | template <class Config, class Base, class Property, class Key,class Value>
|
---|
1759 | inline void
|
---|
1760 | put(Property p, adj_list_helper<Config, Base>& g,
|
---|
1761 | const Key& key, const Value& value)
|
---|
1762 | {
|
---|
1763 | typedef typename Config::graph_type Graph;
|
---|
1764 | typedef typename boost::property_map<Graph, Property>::type Map;
|
---|
1765 | Map pmap = get(p, static_cast<Graph&>(g));
|
---|
1766 | put(pmap, key, value);
|
---|
1767 | }
|
---|
1768 |
|
---|
1769 |
|
---|
1770 | //=========================================================================
|
---|
1771 | // Generalize Adjacency List Implementation
|
---|
1772 |
|
---|
1773 | struct adj_list_tag { };
|
---|
1774 |
|
---|
1775 | template <class Derived, class Config, class Base>
|
---|
1776 | class adj_list_impl
|
---|
1777 | : public adj_list_helper<Config, Base>
|
---|
1778 | {
|
---|
1779 | typedef typename Config::OutEdgeList OutEdgeList;
|
---|
1780 | typedef typename Config::InEdgeList InEdgeList;
|
---|
1781 | typedef typename Config::StoredVertexList StoredVertexList;
|
---|
1782 | public:
|
---|
1783 | typedef typename Config::stored_vertex stored_vertex;
|
---|
1784 | typedef typename Config::EdgeContainer EdgeContainer;
|
---|
1785 | typedef typename Config::vertex_descriptor vertex_descriptor;
|
---|
1786 | typedef typename Config::edge_descriptor edge_descriptor;
|
---|
1787 | typedef typename Config::vertex_iterator vertex_iterator;
|
---|
1788 | typedef typename Config::edge_iterator edge_iterator;
|
---|
1789 | typedef typename Config::edge_parallel_category edge_parallel_category;
|
---|
1790 | typedef typename Config::vertices_size_type vertices_size_type;
|
---|
1791 | typedef typename Config::edges_size_type edges_size_type;
|
---|
1792 | typedef typename Config::degree_size_type degree_size_type;
|
---|
1793 | typedef typename Config::edge_property_type edge_property_type;
|
---|
1794 | typedef adj_list_tag graph_tag;
|
---|
1795 |
|
---|
1796 | static vertex_descriptor null_vertex()
|
---|
1797 | {
|
---|
1798 | return 0;
|
---|
1799 | }
|
---|
1800 |
|
---|
1801 | inline adj_list_impl() { }
|
---|
1802 |
|
---|
1803 | inline adj_list_impl(const adj_list_impl& x) {
|
---|
1804 | copy_impl(x);
|
---|
1805 | }
|
---|
1806 | inline adj_list_impl& operator=(const adj_list_impl& x) {
|
---|
1807 | this->clear();
|
---|
1808 | copy_impl(x);
|
---|
1809 | return *this;
|
---|
1810 | }
|
---|
1811 | inline void clear() {
|
---|
1812 | for (typename StoredVertexList::iterator i = m_vertices.begin();
|
---|
1813 | i != m_vertices.end(); ++i)
|
---|
1814 | delete (stored_vertex*)*i;
|
---|
1815 | m_vertices.clear();
|
---|
1816 | m_edges.clear();
|
---|
1817 | }
|
---|
1818 | inline adj_list_impl(vertices_size_type num_vertices) {
|
---|
1819 | for (vertices_size_type i = 0; i < num_vertices; ++i)
|
---|
1820 | add_vertex(static_cast<Derived&>(*this));
|
---|
1821 | }
|
---|
1822 | template <class EdgeIterator>
|
---|
1823 | inline adj_list_impl(vertices_size_type num_vertices,
|
---|
1824 | EdgeIterator first, EdgeIterator last)
|
---|
1825 | {
|
---|
1826 | vertex_descriptor* v = new vertex_descriptor[num_vertices];
|
---|
1827 | for (vertices_size_type i = 0; i < num_vertices; ++i)
|
---|
1828 | v[i] = add_vertex(static_cast<Derived&>(*this));
|
---|
1829 |
|
---|
1830 | while (first != last) {
|
---|
1831 | add_edge(v[(*first).first], v[(*first).second], *this);
|
---|
1832 | ++first;
|
---|
1833 | }
|
---|
1834 | delete [] v;
|
---|
1835 | }
|
---|
1836 | template <class EdgeIterator, class EdgePropertyIterator>
|
---|
1837 | inline adj_list_impl(vertices_size_type num_vertices,
|
---|
1838 | EdgeIterator first, EdgeIterator last,
|
---|
1839 | EdgePropertyIterator ep_iter)
|
---|
1840 | {
|
---|
1841 | vertex_descriptor* v = new vertex_descriptor[num_vertices];
|
---|
1842 | for (vertices_size_type i = 0; i < num_vertices; ++i)
|
---|
1843 | v[i] = add_vertex(static_cast<Derived&>(*this));
|
---|
1844 |
|
---|
1845 | while (first != last) {
|
---|
1846 | add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
|
---|
1847 | ++first;
|
---|
1848 | ++ep_iter;
|
---|
1849 | }
|
---|
1850 | delete [] v;
|
---|
1851 | }
|
---|
1852 | ~adj_list_impl() {
|
---|
1853 | for (typename StoredVertexList::iterator i = m_vertices.begin();
|
---|
1854 | i != m_vertices.end(); ++i)
|
---|
1855 | delete (stored_vertex*)*i;
|
---|
1856 | }
|
---|
1857 | // protected:
|
---|
1858 | inline OutEdgeList& out_edge_list(vertex_descriptor v) {
|
---|
1859 | stored_vertex* sv = (stored_vertex*)v;
|
---|
1860 | return sv->m_out_edges;
|
---|
1861 | }
|
---|
1862 | inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
|
---|
1863 | stored_vertex* sv = (stored_vertex*)v;
|
---|
1864 | return sv->m_out_edges;
|
---|
1865 | }
|
---|
1866 | inline StoredVertexList& vertex_set() { return m_vertices; }
|
---|
1867 | inline const StoredVertexList& vertex_set() const { return m_vertices; }
|
---|
1868 |
|
---|
1869 | inline void copy_impl(const adj_list_impl& x_)
|
---|
1870 | {
|
---|
1871 | const Derived& x = static_cast<const Derived&>(x_);
|
---|
1872 |
|
---|
1873 | // Would be better to have a constant time way to get from
|
---|
1874 | // vertices in x to the corresponding vertices in *this.
|
---|
1875 | std::map<stored_vertex*,stored_vertex*> vertex_map;
|
---|
1876 |
|
---|
1877 | // Copy the stored vertex objects by adding each vertex
|
---|
1878 | // and copying its property object.
|
---|
1879 | vertex_iterator vi, vi_end;
|
---|
1880 | for (boost::tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
|
---|
1881 | stored_vertex* v = (stored_vertex*)add_vertex(*this);
|
---|
1882 | v->m_property = ((stored_vertex*)*vi)->m_property;
|
---|
1883 | vertex_map[(stored_vertex*)*vi] = v;
|
---|
1884 | }
|
---|
1885 | // Copy the edges by adding each edge and copying its
|
---|
1886 | // property object.
|
---|
1887 | edge_iterator ei, ei_end;
|
---|
1888 | for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
|
---|
1889 | edge_descriptor e;
|
---|
1890 | bool inserted;
|
---|
1891 | vertex_descriptor s = source(*ei,x), t = target(*ei,x);
|
---|
1892 | boost::tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
|
---|
1893 | vertex_map[(stored_vertex*)t], *this);
|
---|
1894 | *((edge_property_type*)e.m_eproperty)
|
---|
1895 | = *((edge_property_type*)(*ei).m_eproperty);
|
---|
1896 | }
|
---|
1897 | }
|
---|
1898 |
|
---|
1899 |
|
---|
1900 | typename Config::EdgeContainer m_edges;
|
---|
1901 | StoredVertexList m_vertices;
|
---|
1902 | };
|
---|
1903 |
|
---|
1904 | // O(1)
|
---|
1905 | template <class Derived, class Config, class Base>
|
---|
1906 | inline typename Config::vertex_descriptor
|
---|
1907 | add_vertex(adj_list_impl<Derived, Config, Base>& g_)
|
---|
1908 | {
|
---|
1909 | Derived& g = static_cast<Derived&>(g_);
|
---|
1910 | typedef typename Config::stored_vertex stored_vertex;
|
---|
1911 | stored_vertex* v = new stored_vertex;
|
---|
1912 | typename Config::StoredVertexList::iterator pos;
|
---|
1913 | bool inserted;
|
---|
1914 | boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
|
---|
1915 | v->m_position = pos;
|
---|
1916 | g.added_vertex(v);
|
---|
1917 | return v;
|
---|
1918 | }
|
---|
1919 | // O(1)
|
---|
1920 | template <class Derived, class Config, class Base>
|
---|
1921 | inline typename Config::vertex_descriptor
|
---|
1922 | add_vertex(const typename Config::vertex_property_type& p,
|
---|
1923 | adj_list_impl<Derived, Config, Base>& g_)
|
---|
1924 | {
|
---|
1925 | typedef typename Config::vertex_descriptor vertex_descriptor;
|
---|
1926 | Derived& g = static_cast<Derived&>(g_);
|
---|
1927 | if (optional<vertex_descriptor> v
|
---|
1928 | = g.vertex_by_property(get_property_value(p, vertex_bundle)))
|
---|
1929 | return *v;
|
---|
1930 |
|
---|
1931 | typedef typename Config::stored_vertex stored_vertex;
|
---|
1932 | stored_vertex* v = new stored_vertex(p);
|
---|
1933 | typename Config::StoredVertexList::iterator pos;
|
---|
1934 | bool inserted;
|
---|
1935 | boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
|
---|
1936 | v->m_position = pos;
|
---|
1937 | g.added_vertex(v);
|
---|
1938 | return v;
|
---|
1939 | }
|
---|
1940 | // O(1)
|
---|
1941 | template <class Derived, class Config, class Base>
|
---|
1942 | inline void remove_vertex(typename Config::vertex_descriptor u,
|
---|
1943 | adj_list_impl<Derived, Config, Base>& g_)
|
---|
1944 | {
|
---|
1945 | typedef typename Config::stored_vertex stored_vertex;
|
---|
1946 | Derived& g = static_cast<Derived&>(g_);
|
---|
1947 | g.removing_vertex(u, boost::graph_detail::iterator_stability(g_.m_vertices));
|
---|
1948 | stored_vertex* su = (stored_vertex*)u;
|
---|
1949 | g.m_vertices.erase(su->m_position);
|
---|
1950 | delete su;
|
---|
1951 | }
|
---|
1952 | // O(V)
|
---|
1953 | template <class Derived, class Config, class Base>
|
---|
1954 | inline typename Config::vertex_descriptor
|
---|
1955 | vertex(typename Config::vertices_size_type n,
|
---|
1956 | const adj_list_impl<Derived, Config, Base>& g_)
|
---|
1957 | {
|
---|
1958 | const Derived& g = static_cast<const Derived&>(g_);
|
---|
1959 | typename Config::vertex_iterator i = vertices(g).first;
|
---|
1960 | while (n--) ++i; // std::advance(i, n); (not VC++ portable)
|
---|
1961 | return *i;
|
---|
1962 | }
|
---|
1963 |
|
---|
1964 | //=========================================================================
|
---|
1965 | // Vector-Backbone Adjacency List Implementation
|
---|
1966 |
|
---|
1967 | namespace detail {
|
---|
1968 |
|
---|
1969 | template <class Graph, class vertex_descriptor>
|
---|
1970 | inline void
|
---|
1971 | remove_vertex_dispatch(Graph& g, vertex_descriptor u,
|
---|
1972 | boost::directed_tag)
|
---|
1973 | {
|
---|
1974 | typedef typename Graph::edge_parallel_category edge_parallel_category;
|
---|
1975 | g.m_vertices.erase(g.m_vertices.begin() + u);
|
---|
1976 | vertex_descriptor V = num_vertices(g);
|
---|
1977 | if (u != V) {
|
---|
1978 | for (vertex_descriptor v = 0; v < V; ++v)
|
---|
1979 | reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
|
---|
1980 | }
|
---|
1981 | }
|
---|
1982 |
|
---|
1983 | template <class Graph, class vertex_descriptor>
|
---|
1984 | inline void
|
---|
1985 | remove_vertex_dispatch(Graph& g, vertex_descriptor u,
|
---|
1986 | boost::undirected_tag)
|
---|
1987 | {
|
---|
1988 | typedef typename Graph::global_edgelist_selector EdgeListS;
|
---|
1989 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
1990 |
|
---|
1991 | typedef typename Graph::edge_parallel_category edge_parallel_category;
|
---|
1992 | g.m_vertices.erase(g.m_vertices.begin() + u);
|
---|
1993 | vertex_descriptor V = num_vertices(g);
|
---|
1994 | for (vertex_descriptor v = 0; v < V; ++v)
|
---|
1995 | reindex_edge_list(g.out_edge_list(v), u,
|
---|
1996 | edge_parallel_category());
|
---|
1997 | typedef typename Graph::EdgeContainer Container;
|
---|
1998 | typedef typename Container::iterator Iter;
|
---|
1999 | Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
|
---|
2000 | for (; ei != ei_end; ++ei) {
|
---|
2001 | if (ei->m_source > u)
|
---|
2002 | --ei->m_source;
|
---|
2003 | if (ei->m_target > u)
|
---|
2004 | --ei->m_target;
|
---|
2005 | }
|
---|
2006 | }
|
---|
2007 | template <class Graph, class vertex_descriptor>
|
---|
2008 | inline void
|
---|
2009 | remove_vertex_dispatch(Graph& g, vertex_descriptor u,
|
---|
2010 | boost::bidirectional_tag)
|
---|
2011 | {
|
---|
2012 | typedef typename Graph::global_edgelist_selector EdgeListS;
|
---|
2013 | BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
---|
2014 |
|
---|
2015 | typedef typename Graph::edge_parallel_category edge_parallel_category;
|
---|
2016 | g.m_vertices.erase(g.m_vertices.begin() + u);
|
---|
2017 | vertex_descriptor V = num_vertices(g);
|
---|
2018 | vertex_descriptor v;
|
---|
2019 | if (u != V) {
|
---|
2020 | for (v = 0; v < V; ++v)
|
---|
2021 | reindex_edge_list(g.out_edge_list(v), u,
|
---|
2022 | edge_parallel_category());
|
---|
2023 | for (v = 0; v < V; ++v)
|
---|
2024 | reindex_edge_list(in_edge_list(g, v), u,
|
---|
2025 | edge_parallel_category());
|
---|
2026 |
|
---|
2027 | typedef typename Graph::EdgeContainer Container;
|
---|
2028 | typedef typename Container::iterator Iter;
|
---|
2029 | Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
|
---|
2030 | for (; ei != ei_end; ++ei) {
|
---|
2031 | if (ei->m_source > u)
|
---|
2032 | --ei->m_source;
|
---|
2033 | if (ei->m_target > u)
|
---|
2034 | --ei->m_target;
|
---|
2035 | }
|
---|
2036 | }
|
---|
2037 | }
|
---|
2038 |
|
---|
2039 | template <class EdgeList, class vertex_descriptor>
|
---|
2040 | inline void
|
---|
2041 | reindex_edge_list(EdgeList& el, vertex_descriptor u,
|
---|
2042 | boost::allow_parallel_edge_tag)
|
---|
2043 | {
|
---|
2044 | typename EdgeList::iterator ei = el.begin(), e_end = el.end();
|
---|
2045 | for (; ei != e_end; ++ei)
|
---|
2046 | if ((*ei).get_target() > u)
|
---|
2047 | --(*ei).get_target();
|
---|
2048 | }
|
---|
2049 | template <class EdgeList, class vertex_descriptor>
|
---|
2050 | inline void
|
---|
2051 | reindex_edge_list(EdgeList& el, vertex_descriptor u,
|
---|
2052 | boost::disallow_parallel_edge_tag)
|
---|
2053 | {
|
---|
2054 | typename EdgeList::iterator ei = el.begin(), e_end = el.end();
|
---|
2055 | while (ei != e_end) {
|
---|
2056 | typename EdgeList::value_type ce = *ei;
|
---|
2057 | ++ei;
|
---|
2058 | if (ce.get_target() > u) {
|
---|
2059 | el.erase(ce);
|
---|
2060 | --ce.get_target();
|
---|
2061 | el.insert(ce);
|
---|
2062 | }
|
---|
2063 | }
|
---|
2064 | }
|
---|
2065 | } // namespace detail
|
---|
2066 |
|
---|
2067 | struct vec_adj_list_tag { };
|
---|
2068 |
|
---|
2069 | template <class Graph, class Config, class Base>
|
---|
2070 | class vec_adj_list_impl
|
---|
2071 | : public adj_list_helper<Config, Base>
|
---|
2072 | {
|
---|
2073 | typedef typename Config::OutEdgeList OutEdgeList;
|
---|
2074 | typedef typename Config::InEdgeList InEdgeList;
|
---|
2075 | typedef typename Config::StoredVertexList StoredVertexList;
|
---|
2076 | public:
|
---|
2077 | typedef typename Config::vertex_descriptor vertex_descriptor;
|
---|
2078 | typedef typename Config::edge_descriptor edge_descriptor;
|
---|
2079 | typedef typename Config::out_edge_iterator out_edge_iterator;
|
---|
2080 | typedef typename Config::edge_iterator edge_iterator;
|
---|
2081 | typedef typename Config::directed_category directed_category;
|
---|
2082 | typedef typename Config::vertices_size_type vertices_size_type;
|
---|
2083 | typedef typename Config::edges_size_type edges_size_type;
|
---|
2084 | typedef typename Config::degree_size_type degree_size_type;
|
---|
2085 | typedef typename Config::StoredEdge StoredEdge;
|
---|
2086 | typedef typename Config::stored_vertex stored_vertex;
|
---|
2087 | typedef typename Config::EdgeContainer EdgeContainer;
|
---|
2088 | typedef typename Config::edge_property_type edge_property_type;
|
---|
2089 | typedef vec_adj_list_tag graph_tag;
|
---|
2090 |
|
---|
2091 | static vertex_descriptor null_vertex()
|
---|
2092 | {
|
---|
2093 | return (std::numeric_limits<vertex_descriptor>::max)();
|
---|
2094 | }
|
---|
2095 |
|
---|
2096 | inline vec_adj_list_impl() { }
|
---|
2097 |
|
---|
2098 | inline vec_adj_list_impl(const vec_adj_list_impl& x) {
|
---|
2099 | copy_impl(x);
|
---|
2100 | }
|
---|
2101 | inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
|
---|
2102 | this->clear();
|
---|
2103 | copy_impl(x);
|
---|
2104 | return *this;
|
---|
2105 | }
|
---|
2106 | inline void clear() {
|
---|
2107 | m_vertices.clear();
|
---|
2108 | m_edges.clear();
|
---|
2109 | }
|
---|
2110 |
|
---|
2111 | inline vec_adj_list_impl(vertices_size_type _num_vertices)
|
---|
2112 | : m_vertices(_num_vertices) { }
|
---|
2113 |
|
---|
2114 | template <class EdgeIterator>
|
---|
2115 | inline vec_adj_list_impl(vertices_size_type num_vertices,
|
---|
2116 | EdgeIterator first, EdgeIterator last)
|
---|
2117 | : m_vertices(num_vertices)
|
---|
2118 | {
|
---|
2119 | while (first != last) {
|
---|
2120 | add_edge((*first).first, (*first).second,
|
---|
2121 | static_cast<Graph&>(*this));
|
---|
2122 | ++first;
|
---|
2123 | }
|
---|
2124 | }
|
---|
2125 | template <class EdgeIterator, class EdgePropertyIterator>
|
---|
2126 | inline vec_adj_list_impl(vertices_size_type num_vertices,
|
---|
2127 | EdgeIterator first, EdgeIterator last,
|
---|
2128 | EdgePropertyIterator ep_iter)
|
---|
2129 | : m_vertices(num_vertices)
|
---|
2130 | {
|
---|
2131 | while (first != last) {
|
---|
2132 | add_edge((*first).first, (*first).second, *ep_iter,
|
---|
2133 | static_cast<Graph&>(*this));
|
---|
2134 | ++first;
|
---|
2135 | ++ep_iter;
|
---|
2136 | }
|
---|
2137 | }
|
---|
2138 |
|
---|
2139 | // protected:
|
---|
2140 | inline boost::integer_range<vertex_descriptor> vertex_set() const {
|
---|
2141 | return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
|
---|
2142 | }
|
---|
2143 | inline OutEdgeList& out_edge_list(vertex_descriptor v) {
|
---|
2144 | return m_vertices[v].m_out_edges;
|
---|
2145 | }
|
---|
2146 | inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
|
---|
2147 | return m_vertices[v].m_out_edges;
|
---|
2148 | }
|
---|
2149 | inline void copy_impl(const vec_adj_list_impl& x_)
|
---|
2150 | {
|
---|
2151 | const Graph& x = static_cast<const Graph&>(x_);
|
---|
2152 | // Copy the stored vertex objects by adding each vertex
|
---|
2153 | // and copying its property object.
|
---|
2154 | for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
|
---|
2155 | vertex_descriptor v = add_vertex(*this);
|
---|
2156 | m_vertices[v].m_property = x.m_vertices[i].m_property;
|
---|
2157 | }
|
---|
2158 | // Copy the edges by adding each edge and copying its
|
---|
2159 | // property object.
|
---|
2160 | edge_iterator ei, ei_end;
|
---|
2161 | for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
|
---|
2162 | edge_descriptor e;
|
---|
2163 | bool inserted;
|
---|
2164 | boost::tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
|
---|
2165 | *((edge_property_type*)e.m_eproperty)
|
---|
2166 | = *((edge_property_type*)(*ei).m_eproperty);
|
---|
2167 | }
|
---|
2168 | }
|
---|
2169 | typename Config::EdgeContainer m_edges;
|
---|
2170 | StoredVertexList m_vertices;
|
---|
2171 | };
|
---|
2172 | // Had to make these non-members to avoid accidental instantiation
|
---|
2173 | // on SGI MIPSpro C++
|
---|
2174 | template <class G, class C, class B>
|
---|
2175 | inline typename C::InEdgeList&
|
---|
2176 | in_edge_list(vec_adj_list_impl<G,C,B>& g,
|
---|
2177 | typename C::vertex_descriptor v) {
|
---|
2178 | return g.m_vertices[v].m_in_edges;
|
---|
2179 | }
|
---|
2180 | template <class G, class C, class B>
|
---|
2181 | inline const typename C::InEdgeList&
|
---|
2182 | in_edge_list(const vec_adj_list_impl<G,C,B>& g,
|
---|
2183 | typename C::vertex_descriptor v) {
|
---|
2184 | return g.m_vertices[v].m_in_edges;
|
---|
2185 | }
|
---|
2186 |
|
---|
2187 | // O(1)
|
---|
2188 | template <class Graph, class Config, class Base>
|
---|
2189 | inline typename Config::vertex_descriptor
|
---|
2190 | add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
|
---|
2191 | Graph& g = static_cast<Graph&>(g_);
|
---|
2192 | g.m_vertices.resize(g.m_vertices.size() + 1);
|
---|
2193 | g.added_vertex(g.m_vertices.size() - 1);
|
---|
2194 | return g.m_vertices.size() - 1;
|
---|
2195 | }
|
---|
2196 |
|
---|
2197 | template <class Graph, class Config, class Base>
|
---|
2198 | inline typename Config::vertex_descriptor
|
---|
2199 | add_vertex(const typename Config::vertex_property_type& p,
|
---|
2200 | vec_adj_list_impl<Graph, Config, Base>& g_) {
|
---|
2201 | typedef typename Config::vertex_descriptor vertex_descriptor;
|
---|
2202 | Graph& g = static_cast<Graph&>(g_);
|
---|
2203 | if (optional<vertex_descriptor> v
|
---|
2204 | = g.vertex_by_property(get_property_value(p, vertex_bundle)))
|
---|
2205 | return *v;
|
---|
2206 | typedef typename Config::stored_vertex stored_vertex;
|
---|
2207 | g.m_vertices.push_back(stored_vertex(p));
|
---|
2208 | g.added_vertex(g.m_vertices.size() - 1);
|
---|
2209 | return g.m_vertices.size() - 1;
|
---|
2210 | }
|
---|
2211 |
|
---|
2212 | // Here we override the directed_graph_helper add_edge() function
|
---|
2213 | // so that the number of vertices is automatically changed if
|
---|
2214 | // either u or v is greater than the number of vertices.
|
---|
2215 | template <class Graph, class Config, class Base>
|
---|
2216 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
2217 | add_edge(typename Config::vertex_descriptor u,
|
---|
2218 | typename Config::vertex_descriptor v,
|
---|
2219 | const typename Config::edge_property_type& p,
|
---|
2220 | vec_adj_list_impl<Graph, Config, Base>& g_)
|
---|
2221 | {
|
---|
2222 | BOOST_USING_STD_MAX();
|
---|
2223 | typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
|
---|
2224 | if (x >= num_vertices(g_))
|
---|
2225 | g_.m_vertices.resize(x + 1);
|
---|
2226 | adj_list_helper<Config, Base>& g = g_;
|
---|
2227 | return add_edge(u, v, p, g);
|
---|
2228 | }
|
---|
2229 | template <class Graph, class Config, class Base>
|
---|
2230 | inline std::pair<typename Config::edge_descriptor, bool>
|
---|
2231 | add_edge(typename Config::vertex_descriptor u,
|
---|
2232 | typename Config::vertex_descriptor v,
|
---|
2233 | vec_adj_list_impl<Graph, Config, Base>& g_)
|
---|
2234 | {
|
---|
2235 | typename Config::edge_property_type p;
|
---|
2236 | return add_edge(u, v, p, g_);
|
---|
2237 | }
|
---|
2238 |
|
---|
2239 |
|
---|
2240 | // O(V + E)
|
---|
2241 | template <class Graph, class Config, class Base>
|
---|
2242 | inline void remove_vertex(typename Config::vertex_descriptor v,
|
---|
2243 | vec_adj_list_impl<Graph, Config, Base>& g_)
|
---|
2244 | {
|
---|
2245 | typedef typename Config::directed_category Cat;
|
---|
2246 | Graph& g = static_cast<Graph&>(g_);
|
---|
2247 | g.removing_vertex(v, boost::graph_detail::iterator_stability(g_.m_vertices));
|
---|
2248 | detail::remove_vertex_dispatch(g, v, Cat());
|
---|
2249 | }
|
---|
2250 | // O(1)
|
---|
2251 | template <class Graph, class Config, class Base>
|
---|
2252 | inline typename Config::vertex_descriptor
|
---|
2253 | vertex(typename Config::vertices_size_type n,
|
---|
2254 | const vec_adj_list_impl<Graph, Config, Base>&)
|
---|
2255 | {
|
---|
2256 | return n;
|
---|
2257 | }
|
---|
2258 |
|
---|
2259 |
|
---|
2260 | namespace detail {
|
---|
2261 |
|
---|
2262 | //=========================================================================
|
---|
2263 | // Adjacency List Generator
|
---|
2264 |
|
---|
2265 | template <class Graph, class VertexListS, class OutEdgeListS,
|
---|
2266 | class DirectedS, class VertexProperty, class EdgeProperty,
|
---|
2267 | class GraphProperty, class EdgeListS>
|
---|
2268 | struct adj_list_gen
|
---|
2269 | {
|
---|
2270 | typedef typename detail::is_random_access<VertexListS>::type
|
---|
2271 | is_rand_access;
|
---|
2272 | typedef typename has_property<EdgeProperty>::type has_edge_property;
|
---|
2273 | typedef typename DirectedS::is_directed_t DirectedT;
|
---|
2274 | typedef typename DirectedS::is_bidir_t BidirectionalT;
|
---|
2275 |
|
---|
2276 | struct config
|
---|
2277 | {
|
---|
2278 | typedef OutEdgeListS edgelist_selector;
|
---|
2279 | typedef EdgeListS global_edgelist_selector;
|
---|
2280 |
|
---|
2281 | typedef Graph graph_type;
|
---|
2282 | typedef EdgeProperty edge_property_type;
|
---|
2283 | typedef VertexProperty vertex_property_type;
|
---|
2284 | typedef GraphProperty graph_property_type;
|
---|
2285 | typedef std::size_t vertices_size_type;
|
---|
2286 |
|
---|
2287 | typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
|
---|
2288 | Traits;
|
---|
2289 |
|
---|
2290 | typedef typename Traits::directed_category directed_category;
|
---|
2291 | typedef typename Traits::edge_parallel_category edge_parallel_category;
|
---|
2292 | typedef typename Traits::vertex_descriptor vertex_descriptor;
|
---|
2293 | typedef typename Traits::edge_descriptor edge_descriptor;
|
---|
2294 |
|
---|
2295 | typedef void* vertex_ptr;
|
---|
2296 |
|
---|
2297 | // need to reorganize this to avoid instantiating stuff
|
---|
2298 | // that doesn't get used -JGS
|
---|
2299 |
|
---|
2300 | // VertexList and vertex_iterator
|
---|
2301 | typedef typename container_gen<VertexListS,
|
---|
2302 | vertex_ptr>::type SeqVertexList;
|
---|
2303 | typedef boost::integer_range<vertex_descriptor> RandVertexList;
|
---|
2304 | typedef typename mpl::if_<is_rand_access,
|
---|
2305 | RandVertexList, SeqVertexList>::type VertexList;
|
---|
2306 |
|
---|
2307 | typedef typename VertexList::iterator vertex_iterator;
|
---|
2308 |
|
---|
2309 | // EdgeContainer and StoredEdge
|
---|
2310 |
|
---|
2311 | typedef typename container_gen<EdgeListS,
|
---|
2312 | list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
|
---|
2313 |
|
---|
2314 | typedef typename mpl::and_<DirectedT,
|
---|
2315 | typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
|
---|
2316 |
|
---|
2317 | typedef typename mpl::if_<on_edge_storage,
|
---|
2318 | std::size_t, typename EdgeContainer::size_type
|
---|
2319 | >::type edges_size_type;
|
---|
2320 |
|
---|
2321 | typedef typename EdgeContainer::iterator EdgeIter;
|
---|
2322 |
|
---|
2323 | typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
|
---|
2324 |
|
---|
2325 | typedef typename mpl::if_<on_edge_storage,
|
---|
2326 | stored_edge_property<vertex_descriptor, EdgeProperty>,
|
---|
2327 | typename mpl::if_<is_edge_ra,
|
---|
2328 | stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
|
---|
2329 | stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
|
---|
2330 | >::type
|
---|
2331 | >::type StoredEdge;
|
---|
2332 |
|
---|
2333 | // Adjacency Types
|
---|
2334 |
|
---|
2335 | typedef typename container_gen<OutEdgeListS, StoredEdge>::type
|
---|
2336 | OutEdgeList;
|
---|
2337 | typedef typename OutEdgeList::size_type degree_size_type;
|
---|
2338 | typedef typename OutEdgeList::iterator OutEdgeIter;
|
---|
2339 |
|
---|
2340 | typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
|
---|
2341 | typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
|
---|
2342 | typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
|
---|
2343 |
|
---|
2344 | typedef out_edge_iter<
|
---|
2345 | OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
|
---|
2346 | > out_edge_iterator;
|
---|
2347 |
|
---|
2348 | typedef typename adjacency_iterator_generator<graph_type,
|
---|
2349 | vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
|
---|
2350 |
|
---|
2351 | typedef OutEdgeList InEdgeList;
|
---|
2352 | typedef OutEdgeIter InEdgeIter;
|
---|
2353 | typedef OutEdgeIterCat InEdgeIterCat;
|
---|
2354 | typedef OutEdgeIterDiff InEdgeIterDiff;
|
---|
2355 |
|
---|
2356 | typedef in_edge_iter<
|
---|
2357 | InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
|
---|
2358 | > in_edge_iterator;
|
---|
2359 |
|
---|
2360 | typedef typename inv_adjacency_iterator_generator<graph_type,
|
---|
2361 | vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
|
---|
2362 |
|
---|
2363 | // Edge Iterator
|
---|
2364 |
|
---|
2365 | typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
|
---|
2366 | typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
|
---|
2367 | typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
|
---|
2368 |
|
---|
2369 | typedef undirected_edge_iter<
|
---|
2370 | EdgeIter
|
---|
2371 | , edge_descriptor
|
---|
2372 | , EdgeIterDiff
|
---|
2373 | > UndirectedEdgeIter; // also used for bidirectional
|
---|
2374 |
|
---|
2375 | typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
|
---|
2376 | graph_type> DirectedEdgeIter;
|
---|
2377 |
|
---|
2378 | typedef typename mpl::if_<on_edge_storage,
|
---|
2379 | DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
|
---|
2380 |
|
---|
2381 | // stored_vertex and StoredVertexList
|
---|
2382 | typedef typename container_gen<VertexListS, vertex_ptr>::type
|
---|
2383 | SeqStoredVertexList;
|
---|
2384 | struct seq_stored_vertex {
|
---|
2385 | seq_stored_vertex() { }
|
---|
2386 | seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
---|
2387 | OutEdgeList m_out_edges;
|
---|
2388 | VertexProperty m_property;
|
---|
2389 | typename SeqStoredVertexList::iterator m_position;
|
---|
2390 | };
|
---|
2391 | struct bidir_seq_stored_vertex {
|
---|
2392 | bidir_seq_stored_vertex() { }
|
---|
2393 | bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
---|
2394 | OutEdgeList m_out_edges;
|
---|
2395 | InEdgeList m_in_edges;
|
---|
2396 | VertexProperty m_property;
|
---|
2397 | typename SeqStoredVertexList::iterator m_position;
|
---|
2398 | };
|
---|
2399 | struct rand_stored_vertex {
|
---|
2400 | rand_stored_vertex() { }
|
---|
2401 | rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
---|
2402 | OutEdgeList m_out_edges;
|
---|
2403 | VertexProperty m_property;
|
---|
2404 | };
|
---|
2405 | struct bidir_rand_stored_vertex {
|
---|
2406 | bidir_rand_stored_vertex() { }
|
---|
2407 | bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
---|
2408 | OutEdgeList m_out_edges;
|
---|
2409 | InEdgeList m_in_edges;
|
---|
2410 | VertexProperty m_property;
|
---|
2411 | };
|
---|
2412 | typedef typename mpl::if_<is_rand_access,
|
---|
2413 | typename mpl::if_<BidirectionalT,
|
---|
2414 | bidir_rand_stored_vertex, rand_stored_vertex>::type,
|
---|
2415 | typename mpl::if_<BidirectionalT,
|
---|
2416 | bidir_seq_stored_vertex, seq_stored_vertex>::type
|
---|
2417 | >::type StoredVertex;
|
---|
2418 | struct stored_vertex : public StoredVertex {
|
---|
2419 | stored_vertex() { }
|
---|
2420 | stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
|
---|
2421 | };
|
---|
2422 |
|
---|
2423 | typedef typename container_gen<VertexListS, stored_vertex>::type
|
---|
2424 | RandStoredVertexList;
|
---|
2425 | typedef typename mpl::if_< is_rand_access,
|
---|
2426 | RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
|
---|
2427 | }; // end of config
|
---|
2428 |
|
---|
2429 |
|
---|
2430 | typedef typename mpl::if_<BidirectionalT,
|
---|
2431 | bidirectional_graph_helper_with_property<config>,
|
---|
2432 | typename mpl::if_<DirectedT,
|
---|
2433 | directed_graph_helper<config>,
|
---|
2434 | undirected_graph_helper<config>
|
---|
2435 | >::type
|
---|
2436 | >::type DirectedHelper;
|
---|
2437 |
|
---|
2438 | typedef typename mpl::if_<is_rand_access,
|
---|
2439 | vec_adj_list_impl<Graph, config, DirectedHelper>,
|
---|
2440 | adj_list_impl<Graph, config, DirectedHelper>
|
---|
2441 | >::type type;
|
---|
2442 |
|
---|
2443 | };
|
---|
2444 |
|
---|
2445 | } // namespace detail
|
---|
2446 |
|
---|
2447 | //=========================================================================
|
---|
2448 | // Vertex Property Maps
|
---|
2449 |
|
---|
2450 | template <class Graph, class ValueType, class Reference, class Tag>
|
---|
2451 | struct adj_list_vertex_property_map
|
---|
2452 | : public boost::put_get_helper<
|
---|
2453 | Reference,
|
---|
2454 | adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
|
---|
2455 | >
|
---|
2456 | {
|
---|
2457 | typedef typename Graph::stored_vertex StoredVertex;
|
---|
2458 | typedef ValueType value_type;
|
---|
2459 | typedef Reference reference;
|
---|
2460 | typedef typename Graph::vertex_descriptor key_type;
|
---|
2461 | typedef boost::lvalue_property_map_tag category;
|
---|
2462 | inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { }
|
---|
2463 | inline Reference operator[](key_type v) const {
|
---|
2464 | StoredVertex* sv = (StoredVertex*)v;
|
---|
2465 | return get_property_value(sv->m_property, m_tag);
|
---|
2466 | }
|
---|
2467 | inline Reference operator()(key_type v) const {
|
---|
2468 | return this->operator[](v);
|
---|
2469 | }
|
---|
2470 | Tag m_tag;
|
---|
2471 | };
|
---|
2472 |
|
---|
2473 | template <class Graph, class Property, class PropRef>
|
---|
2474 | struct adj_list_vertex_all_properties_map
|
---|
2475 | : public boost::put_get_helper<PropRef,
|
---|
2476 | adj_list_vertex_all_properties_map<Graph, Property, PropRef>
|
---|
2477 | >
|
---|
2478 | {
|
---|
2479 | typedef typename Graph::stored_vertex StoredVertex;
|
---|
2480 | typedef Property value_type;
|
---|
2481 | typedef PropRef reference;
|
---|
2482 | typedef typename Graph::vertex_descriptor key_type;
|
---|
2483 | typedef boost::lvalue_property_map_tag category;
|
---|
2484 | inline adj_list_vertex_all_properties_map(const Graph* = 0, vertex_all_t = vertex_all_t()) { }
|
---|
2485 | inline PropRef operator[](key_type v) const {
|
---|
2486 | StoredVertex* sv = (StoredVertex*)v;
|
---|
2487 | return sv->m_property;
|
---|
2488 | }
|
---|
2489 | inline PropRef operator()(key_type v) const {
|
---|
2490 | return this->operator[](v);
|
---|
2491 | }
|
---|
2492 | };
|
---|
2493 |
|
---|
2494 | template <class Graph, class GraphPtr, class ValueType, class Reference,
|
---|
2495 | class Tag>
|
---|
2496 | struct vec_adj_list_vertex_property_map
|
---|
2497 | : public boost::put_get_helper<
|
---|
2498 | Reference,
|
---|
2499 | vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
|
---|
2500 | Tag>
|
---|
2501 | >
|
---|
2502 | {
|
---|
2503 | typedef ValueType value_type;
|
---|
2504 | typedef Reference reference;
|
---|
2505 | typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
|
---|
2506 | typedef boost::lvalue_property_map_tag category;
|
---|
2507 | vec_adj_list_vertex_property_map(GraphPtr g = 0, Tag tag = Tag()) : m_g(g), m_tag(tag) { }
|
---|
2508 | inline Reference operator[](key_type v) const {
|
---|
2509 | return get_property_value(m_g->m_vertices[v].m_property, m_tag);
|
---|
2510 | }
|
---|
2511 | inline Reference operator()(key_type v) const {
|
---|
2512 | return this->operator[](v);
|
---|
2513 | }
|
---|
2514 | GraphPtr m_g;
|
---|
2515 | Tag m_tag;
|
---|
2516 | };
|
---|
2517 |
|
---|
2518 | template <class Graph, class GraphPtr, class Property, class PropertyRef>
|
---|
2519 | struct vec_adj_list_vertex_all_properties_map
|
---|
2520 | : public boost::put_get_helper<PropertyRef,
|
---|
2521 | vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
|
---|
2522 | PropertyRef>
|
---|
2523 | >
|
---|
2524 | {
|
---|
2525 | typedef Property value_type;
|
---|
2526 | typedef PropertyRef reference;
|
---|
2527 | typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
|
---|
2528 | typedef boost::lvalue_property_map_tag category;
|
---|
2529 | vec_adj_list_vertex_all_properties_map(GraphPtr g = 0, vertex_all_t = vertex_all_t()) : m_g(g) { }
|
---|
2530 | inline PropertyRef operator[](key_type v) const {
|
---|
2531 | return m_g->m_vertices[v].m_property;
|
---|
2532 | }
|
---|
2533 | inline PropertyRef operator()(key_type v) const {
|
---|
2534 | return this->operator[](v);
|
---|
2535 | }
|
---|
2536 | GraphPtr m_g;
|
---|
2537 | };
|
---|
2538 |
|
---|
2539 | struct adj_list_any_vertex_pa {
|
---|
2540 | template <class Tag, class Graph, class Property>
|
---|
2541 | struct bind_ {
|
---|
2542 | typedef typename property_value<Property, Tag>::type value_type;
|
---|
2543 | typedef value_type& reference;
|
---|
2544 | typedef const value_type& const_reference;
|
---|
2545 |
|
---|
2546 | typedef adj_list_vertex_property_map
|
---|
2547 | <Graph, value_type, reference, Tag> type;
|
---|
2548 | typedef adj_list_vertex_property_map
|
---|
2549 | <Graph, value_type, const_reference, Tag> const_type;
|
---|
2550 | };
|
---|
2551 | };
|
---|
2552 | struct adj_list_all_vertex_pa {
|
---|
2553 | template <class Tag, class Graph, class Property>
|
---|
2554 | struct bind_ {
|
---|
2555 | typedef typename Graph::vertex_descriptor Vertex;
|
---|
2556 | typedef adj_list_vertex_all_properties_map<Graph,Property,
|
---|
2557 | Property&> type;
|
---|
2558 | typedef adj_list_vertex_all_properties_map<Graph,Property,
|
---|
2559 | const Property&> const_type;
|
---|
2560 | };
|
---|
2561 | };
|
---|
2562 |
|
---|
2563 | template <class Property, class Vertex>
|
---|
2564 | struct vec_adj_list_vertex_id_map
|
---|
2565 | : public boost::put_get_helper<
|
---|
2566 | Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
|
---|
2567 | >
|
---|
2568 | {
|
---|
2569 | typedef Vertex value_type;
|
---|
2570 | typedef Vertex key_type;
|
---|
2571 | typedef Vertex reference;
|
---|
2572 | typedef boost::readable_property_map_tag category;
|
---|
2573 | inline vec_adj_list_vertex_id_map() { }
|
---|
2574 | template <class Graph>
|
---|
2575 | inline vec_adj_list_vertex_id_map(const Graph&, vertex_index_t) { }
|
---|
2576 | inline value_type operator[](key_type v) const { return v; }
|
---|
2577 | inline value_type operator()(key_type v) const { return v; }
|
---|
2578 | };
|
---|
2579 |
|
---|
2580 | struct vec_adj_list_any_vertex_pa {
|
---|
2581 | template <class Tag, class Graph, class Property>
|
---|
2582 | struct bind_ {
|
---|
2583 | typedef typename property_value<Property, Tag>::type value_type;
|
---|
2584 | typedef value_type& reference;
|
---|
2585 | typedef const value_type& const_reference;
|
---|
2586 |
|
---|
2587 | typedef vec_adj_list_vertex_property_map
|
---|
2588 | <Graph, Graph*, value_type, reference, Tag> type;
|
---|
2589 | typedef vec_adj_list_vertex_property_map
|
---|
2590 | <Graph, const Graph*, value_type, const_reference, Tag> const_type;
|
---|
2591 | };
|
---|
2592 | };
|
---|
2593 | struct vec_adj_list_id_vertex_pa {
|
---|
2594 | template <class Tag, class Graph, class Property>
|
---|
2595 | struct bind_ {
|
---|
2596 | typedef typename Graph::vertex_descriptor Vertex;
|
---|
2597 | typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
|
---|
2598 | typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
|
---|
2599 | };
|
---|
2600 | };
|
---|
2601 | struct vec_adj_list_all_vertex_pa {
|
---|
2602 | template <class Tag, class Graph, class Property>
|
---|
2603 | struct bind_ {
|
---|
2604 | typedef typename Graph::vertex_descriptor Vertex;
|
---|
2605 | typedef vec_adj_list_vertex_all_properties_map
|
---|
2606 | <Graph, Graph*, Property, Property&> type;
|
---|
2607 | typedef vec_adj_list_vertex_all_properties_map
|
---|
2608 | <Graph, const Graph*, Property, const Property&> const_type;
|
---|
2609 | };
|
---|
2610 | };
|
---|
2611 | namespace detail {
|
---|
2612 | template <class Tag, class Graph, class Property>
|
---|
2613 | struct adj_list_choose_vertex_pa
|
---|
2614 | : boost::mpl::if_<
|
---|
2615 | boost::is_same<Tag, vertex_all_t>,
|
---|
2616 | adj_list_all_vertex_pa,
|
---|
2617 | adj_list_any_vertex_pa>::type
|
---|
2618 | ::template bind_<Tag, Graph, Property>
|
---|
2619 | {};
|
---|
2620 |
|
---|
2621 |
|
---|
2622 | template <class Tag>
|
---|
2623 | struct vec_adj_list_choose_vertex_pa_helper {
|
---|
2624 | typedef vec_adj_list_any_vertex_pa type;
|
---|
2625 | };
|
---|
2626 | template <>
|
---|
2627 | struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
|
---|
2628 | typedef vec_adj_list_id_vertex_pa type;
|
---|
2629 | };
|
---|
2630 | template <>
|
---|
2631 | struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
|
---|
2632 | typedef vec_adj_list_all_vertex_pa type;
|
---|
2633 | };
|
---|
2634 | template <class Tag, class Graph, class Property>
|
---|
2635 | struct vec_adj_list_choose_vertex_pa
|
---|
2636 | : vec_adj_list_choose_vertex_pa_helper<Tag>::type::template bind_<Tag,Graph,Property>
|
---|
2637 | {};
|
---|
2638 | } // namespace detail
|
---|
2639 |
|
---|
2640 | //=========================================================================
|
---|
2641 | // Edge Property Map
|
---|
2642 |
|
---|
2643 | template <class Directed, class Value, class Ref, class Vertex,
|
---|
2644 | class Property, class Tag>
|
---|
2645 | struct adj_list_edge_property_map
|
---|
2646 | : public put_get_helper<
|
---|
2647 | Ref,
|
---|
2648 | adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
|
---|
2649 | Tag>
|
---|
2650 | >
|
---|
2651 | {
|
---|
2652 | Tag tag;
|
---|
2653 | explicit adj_list_edge_property_map(Tag tag = Tag()): tag(tag) {}
|
---|
2654 |
|
---|
2655 | typedef Value value_type;
|
---|
2656 | typedef Ref reference;
|
---|
2657 | typedef detail::edge_desc_impl<Directed, Vertex> key_type;
|
---|
2658 | typedef boost::lvalue_property_map_tag category;
|
---|
2659 | inline Ref operator[](key_type e) const {
|
---|
2660 | Property& p = *(Property*)e.get_property();
|
---|
2661 | return get_property_value(p, tag);
|
---|
2662 | }
|
---|
2663 | inline Ref operator()(key_type e) const {
|
---|
2664 | return this->operator[](e);
|
---|
2665 | }
|
---|
2666 | };
|
---|
2667 |
|
---|
2668 | template <class Directed, class Property, class PropRef, class PropPtr,
|
---|
2669 | class Vertex>
|
---|
2670 | struct adj_list_edge_all_properties_map
|
---|
2671 | : public put_get_helper<PropRef,
|
---|
2672 | adj_list_edge_all_properties_map<Directed, Property, PropRef,
|
---|
2673 | PropPtr, Vertex>
|
---|
2674 | >
|
---|
2675 | {
|
---|
2676 | explicit adj_list_edge_all_properties_map(edge_all_t = edge_all_t()) {}
|
---|
2677 | typedef Property value_type;
|
---|
2678 | typedef PropRef reference;
|
---|
2679 | typedef detail::edge_desc_impl<Directed, Vertex> key_type;
|
---|
2680 | typedef boost::lvalue_property_map_tag category;
|
---|
2681 | inline PropRef operator[](key_type e) const {
|
---|
2682 | return *(PropPtr)e.get_property();
|
---|
2683 | }
|
---|
2684 | inline PropRef operator()(key_type e) const {
|
---|
2685 | return this->operator[](e);
|
---|
2686 | }
|
---|
2687 | };
|
---|
2688 |
|
---|
2689 | // Edge Property Maps
|
---|
2690 |
|
---|
2691 | namespace detail {
|
---|
2692 | struct adj_list_any_edge_pmap {
|
---|
2693 | template <class Graph, class Property, class Tag>
|
---|
2694 | struct bind_ {
|
---|
2695 | typedef typename property_value<Property,Tag>::type value_type;
|
---|
2696 | typedef value_type& reference;
|
---|
2697 | typedef const value_type& const_reference;
|
---|
2698 |
|
---|
2699 | typedef adj_list_edge_property_map
|
---|
2700 | <typename Graph::directed_category, value_type, reference,
|
---|
2701 | typename Graph::vertex_descriptor,Property,Tag> type;
|
---|
2702 | typedef adj_list_edge_property_map
|
---|
2703 | <typename Graph::directed_category, value_type, const_reference,
|
---|
2704 | typename Graph::vertex_descriptor,const Property, Tag> const_type;
|
---|
2705 | };
|
---|
2706 | };
|
---|
2707 | struct adj_list_all_edge_pmap {
|
---|
2708 | template <class Graph, class Property, class Tag>
|
---|
2709 | struct bind_ {
|
---|
2710 | typedef adj_list_edge_all_properties_map
|
---|
2711 | <typename Graph::directed_category, Property, Property&, Property*,
|
---|
2712 | typename Graph::vertex_descriptor> type;
|
---|
2713 | typedef adj_list_edge_all_properties_map
|
---|
2714 | <typename Graph::directed_category, Property, const Property&,
|
---|
2715 | const Property*, typename Graph::vertex_descriptor> const_type;
|
---|
2716 | };
|
---|
2717 | };
|
---|
2718 |
|
---|
2719 | template <class Tag>
|
---|
2720 | struct adj_list_choose_edge_pmap_helper {
|
---|
2721 | typedef adj_list_any_edge_pmap type;
|
---|
2722 | };
|
---|
2723 | template <>
|
---|
2724 | struct adj_list_choose_edge_pmap_helper<edge_all_t> {
|
---|
2725 | typedef adj_list_all_edge_pmap type;
|
---|
2726 | };
|
---|
2727 | template <class Tag, class Graph, class Property>
|
---|
2728 | struct adj_list_choose_edge_pmap
|
---|
2729 | : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag>
|
---|
2730 | {};
|
---|
2731 | struct adj_list_edge_property_selector {
|
---|
2732 | template <class Graph, class Property, class Tag>
|
---|
2733 | struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {};
|
---|
2734 | };
|
---|
2735 | } // namespace detail
|
---|
2736 |
|
---|
2737 | template <>
|
---|
2738 | struct edge_property_selector<adj_list_tag> {
|
---|
2739 | typedef detail::adj_list_edge_property_selector type;
|
---|
2740 | };
|
---|
2741 | template <>
|
---|
2742 | struct edge_property_selector<vec_adj_list_tag> {
|
---|
2743 | typedef detail::adj_list_edge_property_selector type;
|
---|
2744 | };
|
---|
2745 |
|
---|
2746 | // Vertex Property Maps
|
---|
2747 |
|
---|
2748 | struct adj_list_vertex_property_selector {
|
---|
2749 | template <class Graph, class Property, class Tag>
|
---|
2750 | struct bind_
|
---|
2751 | : detail::adj_list_choose_vertex_pa<Tag,Graph,Property>
|
---|
2752 | {};
|
---|
2753 | };
|
---|
2754 | template <>
|
---|
2755 | struct vertex_property_selector<adj_list_tag> {
|
---|
2756 | typedef adj_list_vertex_property_selector type;
|
---|
2757 | };
|
---|
2758 |
|
---|
2759 | struct vec_adj_list_vertex_property_selector {
|
---|
2760 | template <class Graph, class Property, class Tag>
|
---|
2761 | struct bind_: detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> {};
|
---|
2762 | };
|
---|
2763 | template <>
|
---|
2764 | struct vertex_property_selector<vec_adj_list_tag> {
|
---|
2765 | typedef vec_adj_list_vertex_property_selector type;
|
---|
2766 | };
|
---|
2767 |
|
---|
2768 | } // namespace boost
|
---|
2769 |
|
---|
2770 | namespace boost {
|
---|
2771 |
|
---|
2772 | template <typename V>
|
---|
2773 | struct hash< boost::detail::stored_edge<V> >
|
---|
2774 | {
|
---|
2775 | std::size_t
|
---|
2776 | operator()(const boost::detail::stored_edge<V>& e) const
|
---|
2777 | {
|
---|
2778 | return hash<V>()(e.m_target);
|
---|
2779 | }
|
---|
2780 | };
|
---|
2781 |
|
---|
2782 | template <typename V, typename P>
|
---|
2783 | struct hash< boost::detail::stored_edge_property <V,P> >
|
---|
2784 | {
|
---|
2785 | std::size_t
|
---|
2786 | operator()(const boost::detail::stored_edge_property<V,P>& e) const
|
---|
2787 | {
|
---|
2788 | return hash<V>()(e.m_target);
|
---|
2789 | }
|
---|
2790 | };
|
---|
2791 |
|
---|
2792 | template <typename V, typename I, typename P>
|
---|
2793 | struct hash< boost::detail::stored_edge_iter<V,I, P> >
|
---|
2794 | {
|
---|
2795 | std::size_t
|
---|
2796 | operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
|
---|
2797 | {
|
---|
2798 | return hash<V>()(e.m_target);
|
---|
2799 | }
|
---|
2800 | };
|
---|
2801 |
|
---|
2802 | }
|
---|
2803 |
|
---|
2804 |
|
---|
2805 | #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
|
---|
2806 |
|
---|
2807 | /*
|
---|
2808 | Implementation Notes:
|
---|
2809 |
|
---|
2810 | Many of the public interface functions in this file would have been
|
---|
2811 | more conveniently implemented as inline friend functions.
|
---|
2812 | However there are a few compiler bugs that make that approach
|
---|
2813 | non-portable.
|
---|
2814 |
|
---|
2815 | 1. g++ inline friend in namespace bug
|
---|
2816 | 2. g++ using clause doesn't work with inline friends
|
---|
2817 | 3. VC++ doesn't have Koenig lookup
|
---|
2818 |
|
---|
2819 | For these reasons, the functions were all written as non-inline free
|
---|
2820 | functions, and static cast was used to convert from the helper
|
---|
2821 | class to the adjacency_list derived class.
|
---|
2822 |
|
---|
2823 | Looking back, it might have been better to write out all functions
|
---|
2824 | in terms of the adjacency_list, and then use a tag to dispatch
|
---|
2825 | to the various helpers instead of using inheritance.
|
---|
2826 |
|
---|
2827 | */
|
---|