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