Line data Source code
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 0 : inline out_edge_iter() { }
145 0 : inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
146 0 : : super_t(i), m_src(src) { }
147 :
148 : inline EdgeDescriptor
149 0 : dereference() const
150 : {
151 0 : return EdgeDescriptor(m_src, (*this->base()).get_target(),
152 0 : &(*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 0 : inline in_edge_iter() { }
178 0 : inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
179 0 : : super_t(i), m_src(src) { }
180 :
181 : inline EdgeDescriptor
182 0 : dereference() const
183 : {
184 0 : return EdgeDescriptor((*this->base()).get_target(), m_src,
185 0 : &this->base()->get_property());
186 : }
187 : VertexDescriptor m_src;
188 : };
189 :
190 : //=========================================================================
191 : // Undirected Edge Iterator Implementation
192 :
193 : template <class EdgeIter, class EdgeDescriptor, class Difference>
194 : struct undirected_edge_iter
195 : : iterator_adaptor<
196 : undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
197 : , EdgeIter
198 : , EdgeDescriptor
199 : , use_default
200 : , EdgeDescriptor
201 : , Difference
202 : >
203 : {
204 : typedef iterator_adaptor<
205 : undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
206 : , EdgeIter
207 : , EdgeDescriptor
208 : , use_default
209 : , EdgeDescriptor
210 : , Difference
211 : > super_t;
212 :
213 : undirected_edge_iter() {}
214 :
215 : explicit undirected_edge_iter(EdgeIter i)
216 : : super_t(i) {}
217 :
218 : inline EdgeDescriptor
219 : dereference() const {
220 : return EdgeDescriptor(
221 : (*this->base()).m_source
222 : , (*this->base()).m_target
223 : , &this->base()->get_property());
224 : }
225 : };
226 :
227 : //=========================================================================
228 : // Edge Storage Types (stored in the out-edge/in-edge lists)
229 :
230 : template <class Vertex>
231 : class stored_edge
232 : : public boost::equality_comparable1< stored_edge<Vertex>,
233 : boost::less_than_comparable1< stored_edge<Vertex> > >
234 : {
235 : public:
236 : typedef no_property property_type;
237 : inline stored_edge() { }
238 0 : inline stored_edge(Vertex target, const no_property& = no_property())
239 0 : : m_target(target) { }
240 0 : inline Vertex& get_target() const { return m_target; }
241 : inline const no_property& get_property() const { return s_prop; }
242 : inline bool operator==(const stored_edge& x) const
243 : { return m_target == x.get_target(); }
244 : inline bool operator<(const stored_edge& x) const
245 : { return m_target < x.get_target(); }
246 : //protected: need to add hash<> as a friend
247 : static no_property s_prop;
248 : // Sometimes target not used as key in the set, and in that case
249 : // it is ok to change the target.
250 : mutable Vertex m_target;
251 : };
252 : template <class Vertex>
253 : no_property stored_edge<Vertex>::s_prop;
254 :
255 : #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || defined(BOOST_NO_CXX11_SMART_PTR)
256 : template <class Vertex, class Property>
257 : class stored_edge_property : public stored_edge<Vertex> {
258 : typedef stored_edge_property self;
259 : typedef stored_edge<Vertex> Base;
260 : public:
261 : typedef Property property_type;
262 : inline stored_edge_property() { }
263 : inline stored_edge_property(Vertex target,
264 : const Property& p = Property())
265 : : stored_edge<Vertex>(target), m_property(new Property(p)) { }
266 : stored_edge_property(const self& x)
267 : : Base(static_cast< Base const& >(x)), m_property(const_cast<self&>(x).m_property) { }
268 : self& operator=(const self& x) {
269 : // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
270 : static_cast<Base&>(*this) = static_cast< Base const& >(x);
271 : m_property = const_cast<self&>(x).m_property;
272 : return *this;
273 : }
274 : #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
275 : // NOTE Don't rely on default operators, their behavior is broken on several compilers (GCC 4.6).
276 : stored_edge_property(self&& x)
277 : : Base(static_cast< Base&& >(x)), m_property(std::move(x.m_property)) { }
278 : self& operator=(self&& x) {
279 : // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
280 : static_cast<Base&>(*this) = static_cast< Base&& >(x);
281 : m_property = std::move(x.m_property);
282 : return *this;
283 : }
284 : #endif
285 : inline Property& get_property() { return *m_property; }
286 : inline const Property& get_property() const { return *m_property; }
287 : protected:
288 : // Holding the property by-value causes edge-descriptor
289 : // invalidation for add_edge() with EdgeList=vecS. Instead we
290 : // hold a pointer to the property. std::auto_ptr is not
291 : // a perfect fit for the job, but it is darn close.
292 : #ifdef BOOST_NO_AUTO_PTR
293 : std::unique_ptr<Property> m_property;
294 : #else
295 : std::auto_ptr<Property> m_property;
296 : #endif
297 : };
298 : #else
299 : template <class Vertex, class Property>
300 0 : class stored_edge_property : public stored_edge<Vertex> {
301 : typedef stored_edge_property self;
302 : typedef stored_edge<Vertex> Base;
303 : public:
304 : typedef Property property_type;
305 : inline stored_edge_property() { }
306 0 : inline stored_edge_property(Vertex target,
307 : const Property& p = Property())
308 0 : : stored_edge<Vertex>(target), m_property(new Property(p)) { }
309 0 : stored_edge_property(self&& x) : Base(static_cast< Base&& >(x)),
310 0 : m_property(std::move(x.m_property)) { }
311 : stored_edge_property(self const& x) : Base(static_cast< Base const& >(x)),
312 : m_property(std::move(const_cast<self&>(x).m_property)) { }
313 : self& operator=(self&& x) {
314 : // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
315 : static_cast<Base&>(*this) = static_cast< Base&& >(x);
316 : m_property = std::move(x.m_property);
317 : return *this;
318 : }
319 : self& operator=(self const& x) {
320 : // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
321 : static_cast<Base&>(*this) = static_cast< Base const& >(x);
322 : m_property = std::move(const_cast<self&>(x).m_property);
323 : return *this;
324 : }
325 0 : 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 0 : inline stored_edge_iter(Vertex v, Iter i, void* = 0)
343 0 : : stored_edge<Vertex>(v), m_iter(i) { }
344 0 : 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 0 : 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 0 : const graph_type& cg = static_cast<const graph_type&>(g_);
594 0 : graph_type& g = const_cast<graph_type&>(cg);
595 0 : return std::make_pair( edge_iterator(g.vertex_set().begin(),
596 0 : g.vertex_set().begin(),
597 0 : g.vertex_set().end(), g),
598 0 : edge_iterator(g.vertex_set().begin(),
599 0 : g.vertex_set().end(),
600 0 : 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 0 : num_edges(const directed_graph_helper<Config>& g_)
699 : {
700 : typedef typename Config::graph_type graph_type;
701 0 : const graph_type& g = static_cast<const graph_type&>(g_);
702 0 : typename Config::edges_size_type num_e = 0;
703 0 : typename Config::vertex_iterator vi, vi_end;
704 0 : for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
705 0 : 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 0 : 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 0 : graph_type& g = static_cast<graph_type&>(g_);
721 0 : typename Config::OutEdgeList::iterator i;
722 : bool inserted;
723 0 : boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
724 : StoredEdge(v, p));
725 0 : return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
726 0 : 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 0 : 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 0 : list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
875 0 : : Base(u, v), m_property(p) { }
876 0 : 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 0 : in_edges(typename Config::vertex_descriptor u,
1176 : const bidirectional_graph_helper<Config>& g_)
1177 : {
1178 : typedef typename Config::graph_type graph_type;
1179 0 : const graph_type& cg = static_cast<const graph_type&>(g_);
1180 0 : graph_type& g = const_cast<graph_type&>(cg);
1181 : typedef typename Config::in_edge_iterator in_edge_iterator;
1182 : return
1183 0 : std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
1184 0 : 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 0 : 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 0 : 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 0 : typename Config::EdgeContainer::value_type e(u, v, p);
1489 0 : typename Config::EdgeContainer::iterator p_iter
1490 0 : = graph_detail::push(g.m_edges, e).first;
1491 0 : typename Config::OutEdgeList::iterator i;
1492 0 : boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1493 0 : StoredEdge(v, p_iter, &g.m_edges));
1494 : if (inserted) {
1495 0 : boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
1496 0 : 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 0 : adjacent_vertices(typename Config::vertex_descriptor u,
1563 : const adj_list_helper<Config, Base>& g_)
1564 : {
1565 : typedef typename Config::graph_type AdjList;
1566 0 : const AdjList& cg = static_cast<const AdjList&>(g_);
1567 0 : AdjList& g = const_cast<AdjList&>(cg);
1568 : typedef typename Config::adjacency_iterator adjacency_iterator;
1569 0 : typename Config::out_edge_iterator first, last;
1570 0 : boost::tie(first, last) = out_edges(u, g);
1571 0 : return std::make_pair(adjacency_iterator(first, &g),
1572 0 : 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 0 : 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 0 : const AdjList& cg = static_cast<const AdjList&>(g_);
1598 0 : AdjList& g = const_cast<AdjList&>(cg);
1599 : return
1600 0 : std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
1601 0 : 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 0 : vertices(const adj_list_helper<Config, Base>& g_)
1607 : {
1608 : typedef typename Config::graph_type AdjList;
1609 0 : const AdjList& cg = static_cast<const AdjList&>(g_);
1610 0 : AdjList& g = const_cast<AdjList&>(cg);
1611 0 : 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 0 : num_vertices(const adj_list_helper<Config, Base>& g_)
1616 : {
1617 : typedef typename Config::graph_type AdjList;
1618 0 : const AdjList& g = static_cast<const AdjList&>(g_);
1619 0 : return g.vertex_set().size();
1620 : }
1621 : template <class Config, class Base>
1622 : inline typename Config::degree_size_type
1623 0 : out_degree(typename Config::vertex_descriptor u,
1624 : const adj_list_helper<Config, Base>& g_)
1625 : {
1626 : typedef typename Config::graph_type AdjList;
1627 0 : const AdjList& g = static_cast<const AdjList&>(g_);
1628 0 : 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 0 : 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 0 : 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 0 : 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 0 : 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 0 : 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 0 : 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 0 : 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 0 : const Graph& cg = static_cast<const Graph&>(g);
1721 0 : 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 0 : 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 0 : 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 0 : 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 0 : 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 :
2055 : template <class EdgeList, class vertex_descriptor>
2056 : inline void
2057 : reindex_edge_list(EdgeList& el, vertex_descriptor u,
2058 : boost::disallow_parallel_edge_tag)
2059 : {
2060 : for(typename EdgeList::iterator ei = el.begin(); ei != el.end(); ++ei) {
2061 : if (ei->get_target() > u) {
2062 : typename EdgeList::value_type ce = *ei;
2063 : el.erase(ce);
2064 : --ce.get_target();
2065 : el.insert(ce);
2066 : }
2067 : }
2068 : }
2069 : } // namespace detail
2070 :
2071 : struct vec_adj_list_tag { };
2072 :
2073 : template <class Graph, class Config, class Base>
2074 0 : class vec_adj_list_impl
2075 : : public adj_list_helper<Config, Base>
2076 : {
2077 : typedef typename Config::OutEdgeList OutEdgeList;
2078 : typedef typename Config::InEdgeList InEdgeList;
2079 : typedef typename Config::StoredVertexList StoredVertexList;
2080 : public:
2081 : typedef typename Config::vertex_descriptor vertex_descriptor;
2082 : typedef typename Config::edge_descriptor edge_descriptor;
2083 : typedef typename Config::out_edge_iterator out_edge_iterator;
2084 : typedef typename Config::edge_iterator edge_iterator;
2085 : typedef typename Config::directed_category directed_category;
2086 : typedef typename Config::vertices_size_type vertices_size_type;
2087 : typedef typename Config::edges_size_type edges_size_type;
2088 : typedef typename Config::degree_size_type degree_size_type;
2089 : typedef typename Config::StoredEdge StoredEdge;
2090 : typedef typename Config::stored_vertex stored_vertex;
2091 : typedef typename Config::EdgeContainer EdgeContainer;
2092 : typedef typename Config::edge_property_type edge_property_type;
2093 : typedef vec_adj_list_tag graph_tag;
2094 :
2095 0 : static vertex_descriptor null_vertex()
2096 : {
2097 : return (std::numeric_limits<vertex_descriptor>::max)();
2098 : }
2099 :
2100 0 : inline vec_adj_list_impl() { }
2101 :
2102 : inline vec_adj_list_impl(const vec_adj_list_impl& x) {
2103 : copy_impl(x);
2104 : }
2105 0 : inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
2106 0 : this->clear();
2107 0 : copy_impl(x);
2108 : return *this;
2109 : }
2110 0 : inline void clear() {
2111 0 : m_vertices.clear();
2112 0 : m_edges.clear();
2113 0 : }
2114 :
2115 0 : inline vec_adj_list_impl(vertices_size_type _num_vertices)
2116 0 : : m_vertices(_num_vertices) { }
2117 :
2118 : template <class EdgeIterator>
2119 : inline vec_adj_list_impl(vertices_size_type num_vertices,
2120 : EdgeIterator first, EdgeIterator last)
2121 : : m_vertices(num_vertices)
2122 : {
2123 : while (first != last) {
2124 : add_edge((*first).first, (*first).second,
2125 : static_cast<Graph&>(*this));
2126 : ++first;
2127 : }
2128 : }
2129 : template <class EdgeIterator, class EdgePropertyIterator>
2130 : inline vec_adj_list_impl(vertices_size_type num_vertices,
2131 : EdgeIterator first, EdgeIterator last,
2132 : EdgePropertyIterator ep_iter)
2133 : : m_vertices(num_vertices)
2134 : {
2135 : while (first != last) {
2136 : add_edge((*first).first, (*first).second, *ep_iter,
2137 : static_cast<Graph&>(*this));
2138 : ++first;
2139 : ++ep_iter;
2140 : }
2141 : }
2142 :
2143 : // protected:
2144 0 : inline boost::integer_range<vertex_descriptor> vertex_set() const {
2145 0 : return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
2146 : }
2147 0 : inline OutEdgeList& out_edge_list(vertex_descriptor v) {
2148 0 : return m_vertices[v].m_out_edges;
2149 : }
2150 0 : inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
2151 0 : return m_vertices[v].m_out_edges;
2152 : }
2153 0 : inline void copy_impl(const vec_adj_list_impl& x_)
2154 : {
2155 0 : const Graph& x = static_cast<const Graph&>(x_);
2156 : // Copy the stored vertex objects by adding each vertex
2157 : // and copying its property object.
2158 0 : for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
2159 0 : vertex_descriptor v = add_vertex(*this);
2160 0 : m_vertices[v].m_property = x.m_vertices[i].m_property;
2161 : }
2162 : // Copy the edges by adding each edge and copying its
2163 : // property object.
2164 0 : edge_iterator ei, ei_end;
2165 0 : for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
2166 0 : edge_descriptor e;
2167 : bool inserted;
2168 0 : boost::tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
2169 0 : *((edge_property_type*)e.m_eproperty)
2170 0 : = *((edge_property_type*)(*ei).m_eproperty);
2171 : }
2172 0 : }
2173 : typename Config::EdgeContainer m_edges;
2174 : StoredVertexList m_vertices;
2175 : };
2176 : // Had to make these non-members to avoid accidental instantiation
2177 : // on SGI MIPSpro C++
2178 : template <class G, class C, class B>
2179 : inline typename C::InEdgeList&
2180 0 : in_edge_list(vec_adj_list_impl<G,C,B>& g,
2181 : typename C::vertex_descriptor v) {
2182 0 : return g.m_vertices[v].m_in_edges;
2183 : }
2184 : template <class G, class C, class B>
2185 : inline const typename C::InEdgeList&
2186 : in_edge_list(const vec_adj_list_impl<G,C,B>& g,
2187 : typename C::vertex_descriptor v) {
2188 : return g.m_vertices[v].m_in_edges;
2189 : }
2190 :
2191 : // O(1)
2192 : template <class Graph, class Config, class Base>
2193 : inline typename Config::vertex_descriptor
2194 0 : add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
2195 0 : Graph& g = static_cast<Graph&>(g_);
2196 0 : g.m_vertices.resize(g.m_vertices.size() + 1);
2197 0 : g.added_vertex(g.m_vertices.size() - 1);
2198 0 : return g.m_vertices.size() - 1;
2199 : }
2200 :
2201 : template <class Graph, class Config, class Base>
2202 : inline typename Config::vertex_descriptor
2203 : add_vertex(const typename Config::vertex_property_type& p,
2204 : vec_adj_list_impl<Graph, Config, Base>& g_) {
2205 : typedef typename Config::vertex_descriptor vertex_descriptor;
2206 : Graph& g = static_cast<Graph&>(g_);
2207 : if (optional<vertex_descriptor> v
2208 : = g.vertex_by_property(get_property_value(p, vertex_bundle)))
2209 : return *v;
2210 : typedef typename Config::stored_vertex stored_vertex;
2211 : g.m_vertices.push_back(stored_vertex(p));
2212 : g.added_vertex(g.m_vertices.size() - 1);
2213 : return g.m_vertices.size() - 1;
2214 : }
2215 :
2216 : // Here we override the directed_graph_helper add_edge() function
2217 : // so that the number of vertices is automatically changed if
2218 : // either u or v is greater than the number of vertices.
2219 : template <class Graph, class Config, class Base>
2220 : inline std::pair<typename Config::edge_descriptor, bool>
2221 0 : add_edge(typename Config::vertex_descriptor u,
2222 : typename Config::vertex_descriptor v,
2223 : const typename Config::edge_property_type& p,
2224 : vec_adj_list_impl<Graph, Config, Base>& g_)
2225 : {
2226 : BOOST_USING_STD_MAX();
2227 0 : typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
2228 0 : if (x >= num_vertices(g_))
2229 0 : g_.m_vertices.resize(x + 1);
2230 0 : adj_list_helper<Config, Base>& g = g_;
2231 0 : return add_edge(u, v, p, g);
2232 : }
2233 : template <class Graph, class Config, class Base>
2234 : inline std::pair<typename Config::edge_descriptor, bool>
2235 0 : add_edge(typename Config::vertex_descriptor u,
2236 : typename Config::vertex_descriptor v,
2237 : vec_adj_list_impl<Graph, Config, Base>& g_)
2238 : {
2239 0 : typename Config::edge_property_type p;
2240 0 : return add_edge(u, v, p, g_);
2241 : }
2242 :
2243 :
2244 : // O(V + E)
2245 : template <class Graph, class Config, class Base>
2246 : inline void remove_vertex(typename Config::vertex_descriptor v,
2247 : vec_adj_list_impl<Graph, Config, Base>& g_)
2248 : {
2249 : typedef typename Config::directed_category Cat;
2250 : Graph& g = static_cast<Graph&>(g_);
2251 : g.removing_vertex(v, boost::graph_detail::iterator_stability(g_.m_vertices));
2252 : detail::remove_vertex_dispatch(g, v, Cat());
2253 : }
2254 : // O(1)
2255 : template <class Graph, class Config, class Base>
2256 : inline typename Config::vertex_descriptor
2257 : vertex(typename Config::vertices_size_type n,
2258 : const vec_adj_list_impl<Graph, Config, Base>&)
2259 : {
2260 : return n;
2261 : }
2262 :
2263 :
2264 : namespace detail {
2265 :
2266 : //=========================================================================
2267 : // Adjacency List Generator
2268 :
2269 : template <class Graph, class VertexListS, class OutEdgeListS,
2270 : class DirectedS, class VertexProperty, class EdgeProperty,
2271 : class GraphProperty, class EdgeListS>
2272 : struct adj_list_gen
2273 : {
2274 : typedef typename detail::is_random_access<VertexListS>::type
2275 : is_rand_access;
2276 : typedef typename has_property<EdgeProperty>::type has_edge_property;
2277 : typedef typename DirectedS::is_directed_t DirectedT;
2278 : typedef typename DirectedS::is_bidir_t BidirectionalT;
2279 :
2280 : struct config
2281 : {
2282 : typedef OutEdgeListS edgelist_selector;
2283 : typedef EdgeListS global_edgelist_selector;
2284 :
2285 : typedef Graph graph_type;
2286 : typedef EdgeProperty edge_property_type;
2287 : typedef VertexProperty vertex_property_type;
2288 : typedef GraphProperty graph_property_type;
2289 : typedef std::size_t vertices_size_type;
2290 :
2291 : typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
2292 : Traits;
2293 :
2294 : typedef typename Traits::directed_category directed_category;
2295 : typedef typename Traits::edge_parallel_category edge_parallel_category;
2296 : typedef typename Traits::vertex_descriptor vertex_descriptor;
2297 : typedef typename Traits::edge_descriptor edge_descriptor;
2298 :
2299 : typedef void* vertex_ptr;
2300 :
2301 : // need to reorganize this to avoid instantiating stuff
2302 : // that doesn't get used -JGS
2303 :
2304 : // VertexList and vertex_iterator
2305 : typedef typename container_gen<VertexListS,
2306 : vertex_ptr>::type SeqVertexList;
2307 : typedef boost::integer_range<vertex_descriptor> RandVertexList;
2308 : typedef typename mpl::if_<is_rand_access,
2309 : RandVertexList, SeqVertexList>::type VertexList;
2310 :
2311 : typedef typename VertexList::iterator vertex_iterator;
2312 :
2313 : // EdgeContainer and StoredEdge
2314 :
2315 : typedef typename container_gen<EdgeListS,
2316 : list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
2317 :
2318 : typedef typename mpl::and_<DirectedT,
2319 : typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
2320 :
2321 : typedef typename mpl::if_<on_edge_storage,
2322 : std::size_t, typename EdgeContainer::size_type
2323 : >::type edges_size_type;
2324 :
2325 : typedef typename EdgeContainer::iterator EdgeIter;
2326 :
2327 : typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
2328 :
2329 : typedef typename mpl::if_<on_edge_storage,
2330 : stored_edge_property<vertex_descriptor, EdgeProperty>,
2331 : typename mpl::if_<is_edge_ra,
2332 : stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
2333 : stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
2334 : >::type
2335 : >::type StoredEdge;
2336 :
2337 : // Adjacency Types
2338 :
2339 : typedef typename container_gen<OutEdgeListS, StoredEdge>::type
2340 : OutEdgeList;
2341 : typedef typename OutEdgeList::size_type degree_size_type;
2342 : typedef typename OutEdgeList::iterator OutEdgeIter;
2343 :
2344 : typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
2345 : typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
2346 : typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
2347 :
2348 : typedef out_edge_iter<
2349 : OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
2350 : > out_edge_iterator;
2351 :
2352 : typedef typename adjacency_iterator_generator<graph_type,
2353 : vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
2354 :
2355 : typedef OutEdgeList InEdgeList;
2356 : typedef OutEdgeIter InEdgeIter;
2357 : typedef OutEdgeIterCat InEdgeIterCat;
2358 : typedef OutEdgeIterDiff InEdgeIterDiff;
2359 :
2360 : typedef in_edge_iter<
2361 : InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
2362 : > in_edge_iterator;
2363 :
2364 : typedef typename inv_adjacency_iterator_generator<graph_type,
2365 : vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
2366 :
2367 : // Edge Iterator
2368 :
2369 : typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
2370 : typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
2371 : typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
2372 :
2373 : typedef undirected_edge_iter<
2374 : EdgeIter
2375 : , edge_descriptor
2376 : , EdgeIterDiff
2377 : > UndirectedEdgeIter; // also used for bidirectional
2378 :
2379 : typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
2380 : graph_type> DirectedEdgeIter;
2381 :
2382 : typedef typename mpl::if_<on_edge_storage,
2383 : DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
2384 :
2385 : // stored_vertex and StoredVertexList
2386 : typedef typename container_gen<VertexListS, vertex_ptr>::type
2387 : SeqStoredVertexList;
2388 : struct seq_stored_vertex {
2389 : seq_stored_vertex() { }
2390 : seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
2391 : OutEdgeList m_out_edges;
2392 : VertexProperty m_property;
2393 : typename SeqStoredVertexList::iterator m_position;
2394 : };
2395 : struct bidir_seq_stored_vertex {
2396 : bidir_seq_stored_vertex() { }
2397 : bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
2398 : OutEdgeList m_out_edges;
2399 : InEdgeList m_in_edges;
2400 : VertexProperty m_property;
2401 : typename SeqStoredVertexList::iterator m_position;
2402 : };
2403 0 : struct rand_stored_vertex {
2404 0 : rand_stored_vertex() { }
2405 : rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
2406 : OutEdgeList m_out_edges;
2407 : VertexProperty m_property;
2408 : };
2409 : struct bidir_rand_stored_vertex {
2410 0 : bidir_rand_stored_vertex() { }
2411 : bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
2412 : OutEdgeList m_out_edges;
2413 : InEdgeList m_in_edges;
2414 : VertexProperty m_property;
2415 : };
2416 : typedef typename mpl::if_<is_rand_access,
2417 : typename mpl::if_<BidirectionalT,
2418 : bidir_rand_stored_vertex, rand_stored_vertex>::type,
2419 : typename mpl::if_<BidirectionalT,
2420 : bidir_seq_stored_vertex, seq_stored_vertex>::type
2421 : >::type StoredVertex;
2422 0 : struct stored_vertex : public StoredVertex {
2423 0 : stored_vertex() { }
2424 : stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
2425 : };
2426 :
2427 : typedef typename container_gen<VertexListS, stored_vertex>::type
2428 : RandStoredVertexList;
2429 : typedef typename mpl::if_< is_rand_access,
2430 : RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
2431 : }; // end of config
2432 :
2433 :
2434 : typedef typename mpl::if_<BidirectionalT,
2435 : bidirectional_graph_helper_with_property<config>,
2436 : typename mpl::if_<DirectedT,
2437 : directed_graph_helper<config>,
2438 : undirected_graph_helper<config>
2439 : >::type
2440 : >::type DirectedHelper;
2441 :
2442 : typedef typename mpl::if_<is_rand_access,
2443 : vec_adj_list_impl<Graph, config, DirectedHelper>,
2444 : adj_list_impl<Graph, config, DirectedHelper>
2445 : >::type type;
2446 :
2447 : };
2448 :
2449 : } // namespace detail
2450 :
2451 : //=========================================================================
2452 : // Vertex Property Maps
2453 :
2454 : template <class Graph, class ValueType, class Reference, class Tag>
2455 : struct adj_list_vertex_property_map
2456 : : public boost::put_get_helper<
2457 : Reference,
2458 : adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
2459 : >
2460 : {
2461 : typedef typename Graph::stored_vertex StoredVertex;
2462 : typedef ValueType value_type;
2463 : typedef Reference reference;
2464 : typedef typename Graph::vertex_descriptor key_type;
2465 : typedef boost::lvalue_property_map_tag category;
2466 : inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { }
2467 : inline Reference operator[](key_type v) const {
2468 : StoredVertex* sv = (StoredVertex*)v;
2469 : return get_property_value(sv->m_property, m_tag);
2470 : }
2471 : inline Reference operator()(key_type v) const {
2472 : return this->operator[](v);
2473 : }
2474 : Tag m_tag;
2475 : };
2476 :
2477 : template <class Graph, class Property, class PropRef>
2478 : struct adj_list_vertex_all_properties_map
2479 : : public boost::put_get_helper<PropRef,
2480 : adj_list_vertex_all_properties_map<Graph, Property, PropRef>
2481 : >
2482 : {
2483 : typedef typename Graph::stored_vertex StoredVertex;
2484 : typedef Property value_type;
2485 : typedef PropRef reference;
2486 : typedef typename Graph::vertex_descriptor key_type;
2487 : typedef boost::lvalue_property_map_tag category;
2488 : inline adj_list_vertex_all_properties_map(const Graph* = 0, vertex_all_t = vertex_all_t()) { }
2489 : inline PropRef operator[](key_type v) const {
2490 : StoredVertex* sv = (StoredVertex*)v;
2491 : return sv->m_property;
2492 : }
2493 : inline PropRef operator()(key_type v) const {
2494 : return this->operator[](v);
2495 : }
2496 : };
2497 :
2498 : template <class Graph, class GraphPtr, class ValueType, class Reference,
2499 : class Tag>
2500 : struct vec_adj_list_vertex_property_map
2501 : : public boost::put_get_helper<
2502 : Reference,
2503 : vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
2504 : Tag>
2505 : >
2506 : {
2507 : typedef ValueType value_type;
2508 : typedef Reference reference;
2509 : typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
2510 : typedef boost::lvalue_property_map_tag category;
2511 0 : vec_adj_list_vertex_property_map(GraphPtr g = 0, Tag tag = Tag()) : m_g(g), m_tag(tag) { }
2512 0 : inline Reference operator[](key_type v) const {
2513 0 : return get_property_value(m_g->m_vertices[v].m_property, m_tag);
2514 : }
2515 : inline Reference operator()(key_type v) const {
2516 : return this->operator[](v);
2517 : }
2518 : GraphPtr m_g;
2519 : Tag m_tag;
2520 : };
2521 :
2522 : template <class Graph, class GraphPtr, class Property, class PropertyRef>
2523 : struct vec_adj_list_vertex_all_properties_map
2524 : : public boost::put_get_helper<PropertyRef,
2525 : vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
2526 : PropertyRef>
2527 : >
2528 : {
2529 : typedef Property value_type;
2530 : typedef PropertyRef reference;
2531 : typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
2532 : typedef boost::lvalue_property_map_tag category;
2533 : vec_adj_list_vertex_all_properties_map(GraphPtr g = 0, vertex_all_t = vertex_all_t()) : m_g(g) { }
2534 : inline PropertyRef operator[](key_type v) const {
2535 : return m_g->m_vertices[v].m_property;
2536 : }
2537 : inline PropertyRef operator()(key_type v) const {
2538 : return this->operator[](v);
2539 : }
2540 : GraphPtr m_g;
2541 : };
2542 :
2543 : struct adj_list_any_vertex_pa {
2544 : template <class Tag, class Graph, class Property>
2545 : struct bind_ {
2546 : typedef typename property_value<Property, Tag>::type value_type;
2547 : typedef value_type& reference;
2548 : typedef const value_type& const_reference;
2549 :
2550 : typedef adj_list_vertex_property_map
2551 : <Graph, value_type, reference, Tag> type;
2552 : typedef adj_list_vertex_property_map
2553 : <Graph, value_type, const_reference, Tag> const_type;
2554 : };
2555 : };
2556 : struct adj_list_all_vertex_pa {
2557 : template <class Tag, class Graph, class Property>
2558 : struct bind_ {
2559 : typedef typename Graph::vertex_descriptor Vertex;
2560 : typedef adj_list_vertex_all_properties_map<Graph,Property,
2561 : Property&> type;
2562 : typedef adj_list_vertex_all_properties_map<Graph,Property,
2563 : const Property&> const_type;
2564 : };
2565 : };
2566 :
2567 : template <class Property, class Vertex>
2568 : struct vec_adj_list_vertex_id_map
2569 : : public boost::put_get_helper<
2570 : Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
2571 : >
2572 : {
2573 : typedef Vertex value_type;
2574 : typedef Vertex key_type;
2575 : typedef Vertex reference;
2576 : typedef boost::readable_property_map_tag category;
2577 : inline vec_adj_list_vertex_id_map() { }
2578 : template <class Graph>
2579 0 : inline vec_adj_list_vertex_id_map(const Graph&, vertex_index_t) { }
2580 0 : inline value_type operator[](key_type v) const { return v; }
2581 : inline value_type operator()(key_type v) const { return v; }
2582 : };
2583 :
2584 : struct vec_adj_list_any_vertex_pa {
2585 : template <class Tag, class Graph, class Property>
2586 : struct bind_ {
2587 : typedef typename property_value<Property, Tag>::type value_type;
2588 : typedef value_type& reference;
2589 : typedef const value_type& const_reference;
2590 :
2591 : typedef vec_adj_list_vertex_property_map
2592 : <Graph, Graph*, value_type, reference, Tag> type;
2593 : typedef vec_adj_list_vertex_property_map
2594 : <Graph, const Graph*, value_type, const_reference, Tag> const_type;
2595 : };
2596 : };
2597 : struct vec_adj_list_id_vertex_pa {
2598 : template <class Tag, class Graph, class Property>
2599 : struct bind_ {
2600 : typedef typename Graph::vertex_descriptor Vertex;
2601 : typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
2602 : typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
2603 : };
2604 : };
2605 : struct vec_adj_list_all_vertex_pa {
2606 : template <class Tag, class Graph, class Property>
2607 : struct bind_ {
2608 : typedef typename Graph::vertex_descriptor Vertex;
2609 : typedef vec_adj_list_vertex_all_properties_map
2610 : <Graph, Graph*, Property, Property&> type;
2611 : typedef vec_adj_list_vertex_all_properties_map
2612 : <Graph, const Graph*, Property, const Property&> const_type;
2613 : };
2614 : };
2615 : namespace detail {
2616 : template <class Tag, class Graph, class Property>
2617 : struct adj_list_choose_vertex_pa
2618 : : boost::mpl::if_<
2619 : boost::is_same<Tag, vertex_all_t>,
2620 : adj_list_all_vertex_pa,
2621 : adj_list_any_vertex_pa>::type
2622 : ::template bind_<Tag, Graph, Property>
2623 : {};
2624 :
2625 :
2626 : template <class Tag>
2627 : struct vec_adj_list_choose_vertex_pa_helper {
2628 : typedef vec_adj_list_any_vertex_pa type;
2629 : };
2630 : template <>
2631 : struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
2632 : typedef vec_adj_list_id_vertex_pa type;
2633 : };
2634 : template <>
2635 : struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
2636 : typedef vec_adj_list_all_vertex_pa type;
2637 : };
2638 : template <class Tag, class Graph, class Property>
2639 : struct vec_adj_list_choose_vertex_pa
2640 : : vec_adj_list_choose_vertex_pa_helper<Tag>::type::template bind_<Tag,Graph,Property>
2641 : {};
2642 : } // namespace detail
2643 :
2644 : //=========================================================================
2645 : // Edge Property Map
2646 :
2647 : template <class Directed, class Value, class Ref, class Vertex,
2648 : class Property, class Tag>
2649 : struct adj_list_edge_property_map
2650 : : public put_get_helper<
2651 : Ref,
2652 : adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
2653 : Tag>
2654 : >
2655 : {
2656 : Tag tag;
2657 0 : explicit adj_list_edge_property_map(Tag tag = Tag()): tag(tag) {}
2658 :
2659 : typedef Value value_type;
2660 : typedef Ref reference;
2661 : typedef detail::edge_desc_impl<Directed, Vertex> key_type;
2662 : typedef boost::lvalue_property_map_tag category;
2663 0 : inline Ref operator[](key_type e) const {
2664 0 : Property& p = *(Property*)e.get_property();
2665 0 : return get_property_value(p, tag);
2666 : }
2667 : inline Ref operator()(key_type e) const {
2668 : return this->operator[](e);
2669 : }
2670 : };
2671 :
2672 : template <class Directed, class Property, class PropRef, class PropPtr,
2673 : class Vertex>
2674 : struct adj_list_edge_all_properties_map
2675 : : public put_get_helper<PropRef,
2676 : adj_list_edge_all_properties_map<Directed, Property, PropRef,
2677 : PropPtr, Vertex>
2678 : >
2679 : {
2680 : explicit adj_list_edge_all_properties_map(edge_all_t = edge_all_t()) {}
2681 : typedef Property value_type;
2682 : typedef PropRef reference;
2683 : typedef detail::edge_desc_impl<Directed, Vertex> key_type;
2684 : typedef boost::lvalue_property_map_tag category;
2685 : inline PropRef operator[](key_type e) const {
2686 : return *(PropPtr)e.get_property();
2687 : }
2688 : inline PropRef operator()(key_type e) const {
2689 : return this->operator[](e);
2690 : }
2691 : };
2692 :
2693 : // Edge Property Maps
2694 :
2695 : namespace detail {
2696 : struct adj_list_any_edge_pmap {
2697 : template <class Graph, class Property, class Tag>
2698 : struct bind_ {
2699 : typedef typename property_value<Property,Tag>::type value_type;
2700 : typedef value_type& reference;
2701 : typedef const value_type& const_reference;
2702 :
2703 : typedef adj_list_edge_property_map
2704 : <typename Graph::directed_category, value_type, reference,
2705 : typename Graph::vertex_descriptor,Property,Tag> type;
2706 : typedef adj_list_edge_property_map
2707 : <typename Graph::directed_category, value_type, const_reference,
2708 : typename Graph::vertex_descriptor,const Property, Tag> const_type;
2709 : };
2710 : };
2711 : struct adj_list_all_edge_pmap {
2712 : template <class Graph, class Property, class Tag>
2713 : struct bind_ {
2714 : typedef adj_list_edge_all_properties_map
2715 : <typename Graph::directed_category, Property, Property&, Property*,
2716 : typename Graph::vertex_descriptor> type;
2717 : typedef adj_list_edge_all_properties_map
2718 : <typename Graph::directed_category, Property, const Property&,
2719 : const Property*, typename Graph::vertex_descriptor> const_type;
2720 : };
2721 : };
2722 :
2723 : template <class Tag>
2724 : struct adj_list_choose_edge_pmap_helper {
2725 : typedef adj_list_any_edge_pmap type;
2726 : };
2727 : template <>
2728 : struct adj_list_choose_edge_pmap_helper<edge_all_t> {
2729 : typedef adj_list_all_edge_pmap type;
2730 : };
2731 : template <class Tag, class Graph, class Property>
2732 : struct adj_list_choose_edge_pmap
2733 : : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag>
2734 : {};
2735 : struct adj_list_edge_property_selector {
2736 : template <class Graph, class Property, class Tag>
2737 : struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {};
2738 : };
2739 : } // namespace detail
2740 :
2741 : template <>
2742 : struct edge_property_selector<adj_list_tag> {
2743 : typedef detail::adj_list_edge_property_selector type;
2744 : };
2745 : template <>
2746 : struct edge_property_selector<vec_adj_list_tag> {
2747 : typedef detail::adj_list_edge_property_selector type;
2748 : };
2749 :
2750 : // Vertex Property Maps
2751 :
2752 : struct adj_list_vertex_property_selector {
2753 : template <class Graph, class Property, class Tag>
2754 : struct bind_
2755 : : detail::adj_list_choose_vertex_pa<Tag,Graph,Property>
2756 : {};
2757 : };
2758 : template <>
2759 : struct vertex_property_selector<adj_list_tag> {
2760 : typedef adj_list_vertex_property_selector type;
2761 : };
2762 :
2763 : struct vec_adj_list_vertex_property_selector {
2764 : template <class Graph, class Property, class Tag>
2765 : struct bind_: detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> {};
2766 : };
2767 : template <>
2768 : struct vertex_property_selector<vec_adj_list_tag> {
2769 : typedef vec_adj_list_vertex_property_selector type;
2770 : };
2771 :
2772 : } // namespace boost
2773 :
2774 : namespace boost {
2775 :
2776 : template <typename V>
2777 : struct hash< boost::detail::stored_edge<V> >
2778 : {
2779 : std::size_t
2780 : operator()(const boost::detail::stored_edge<V>& e) const
2781 : {
2782 : return hash<V>()(e.m_target);
2783 : }
2784 : };
2785 :
2786 : template <typename V, typename P>
2787 : struct hash< boost::detail::stored_edge_property <V,P> >
2788 : {
2789 : std::size_t
2790 : operator()(const boost::detail::stored_edge_property<V,P>& e) const
2791 : {
2792 : return hash<V>()(e.m_target);
2793 : }
2794 : };
2795 :
2796 : template <typename V, typename I, typename P>
2797 : struct hash< boost::detail::stored_edge_iter<V,I, P> >
2798 : {
2799 : std::size_t
2800 : operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
2801 : {
2802 : return hash<V>()(e.m_target);
2803 : }
2804 : };
2805 :
2806 : }
2807 :
2808 :
2809 : #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
2810 :
2811 : /*
2812 : Implementation Notes:
2813 :
2814 : Many of the public interface functions in this file would have been
2815 : more conveniently implemented as inline friend functions.
2816 : However there are a few compiler bugs that make that approach
2817 : non-portable.
2818 :
2819 : 1. g++ inline friend in namespace bug
2820 : 2. g++ using clause doesn't work with inline friends
2821 : 3. VC++ doesn't have Koenig lookup
2822 :
2823 : For these reasons, the functions were all written as non-inline free
2824 : functions, and static cast was used to convert from the helper
2825 : class to the adjacency_list derived class.
2826 :
2827 : Looking back, it might have been better to write out all functions
2828 : in terms of the adjacency_list, and then use a tag to dispatch
2829 : to the various helpers instead of using inheritance.
2830 :
2831 : */
|
