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