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