Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

adjacency_matrix.hpp @ 857

Revision 857, 37.6 KB checked in by igarcia, 19 years ago (diff)

Line
1	//=======================================================================
2	// Copyright 2001 University of Notre Dame.
3	// Author: Jeremy G. Siek
4	//
5	// Distributed under the Boost Software License, Version 1.0. (See
6	// accompanying file LICENSE_1_0.txt or copy at
7	// http://www.boost.org/LICENSE_1_0.txt)
8	//=======================================================================
9
10	#ifndef BOOST_ADJACENCY_MATRIX_HPP
11	#define BOOST_ADJACENCY_MATRIX_HPP
12
13	#include <boost/config.hpp>
14	#include <vector>
15	#include <memory>
16	#include <cassert>
17	#include <boost/limits.hpp>
18	#include <boost/iterator.hpp>
19	#include <boost/graph/graph_traits.hpp>
20	#include <boost/graph/graph_selectors.hpp>
21	#include <boost/pending/ct_if.hpp>
22	#include <boost/graph/adjacency_iterator.hpp>
23	#include <boost/graph/detail/edge.hpp>
24	#include <boost/iterator/iterator_adaptor.hpp>
25	#include <boost/iterator/filter_iterator.hpp>
26	#include <boost/pending/integer_range.hpp>
27	#include <boost/graph/properties.hpp>
28	#include <boost/tuple/tuple.hpp>
29
30	namespace boost {
31
32	namespace detail {
33
34	template <class Directed, class Vertex>
35	class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>
36	{
37	typedef edge_desc_impl<Directed,Vertex> Base;
38	public:
39	matrix_edge_desc_impl() { }
40	matrix_edge_desc_impl(bool exists, Vertex s, Vertex d,
41	const void* ep = 0)
42	: Base(s, d, ep), m_exists(exists) { }
43	bool exists() const { return m_exists; }
44	private:
45	bool m_exists;
46	};
47
48	struct does_edge_exist {
49	template <class Edge>
50	bool operator()(const Edge& e) const { return e.exists(); }
51	};
52
53	template <typename EdgeProperty>
54	bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {
55	return stored_edge.first;
56	}
57	template <typename EdgeProperty>
58	void set_edge_exists(
59	std::pair<bool, EdgeProperty>& stored_edge,
60	bool flag,
61	int
62	) {
63	stored_edge.first = flag;
64	}
65
66	template <typename EdgeProxy>
67	bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {
68	return edge_proxy;
69	}
70	template <typename EdgeProxy>
71	EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {
72	edge_proxy = flag;
73	return edge_proxy; // just to avoid never used warning
74	}
75
76
77
78	template <typename EdgeProperty>
79	const EdgeProperty&
80	get_property(const std::pair<bool, EdgeProperty>& stored_edge) {
81	return stored_edge.second;
82	}
83	template <typename EdgeProperty>
84	EdgeProperty&
85	get_property(std::pair<bool, EdgeProperty>& stored_edge) {
86	return stored_edge.second;
87	}
88
89	template <typename StoredEdgeProperty, typename EdgeProperty>
90	inline void
91	set_property(std::pair<bool, StoredEdgeProperty>& stored_edge,
92	const EdgeProperty& ep, int) {
93	stored_edge.second = ep;
94	}
95
96	inline const no_property& get_property(const char&) {
97	static no_property s_prop;
98	return s_prop;
99	}
100	inline no_property& get_property(char&) {
101	static no_property s_prop;
102	return s_prop;
103	}
104	template <typename EdgeProxy, typename EdgeProperty>
105	inline void
106	set_property(EdgeProxy, const EdgeProperty&, ...) {}
107
108	//=======================================================================
109	// Directed Out Edge Iterator
110
111	template <
112	typename VertexDescriptor, typename MatrixIter
113	, typename VerticesSizeType, typename EdgeDescriptor
114	>
115	struct dir_adj_matrix_out_edge_iter
116	: iterator_adaptor<
117	dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
118	, MatrixIter
119	, EdgeDescriptor
120	, use_default
121	, EdgeDescriptor
122	, std::ptrdiff_t
123	>
124	{
125	typedef iterator_adaptor<
126	dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
127	, MatrixIter
128	, EdgeDescriptor
129	, use_default
130	, EdgeDescriptor
131	, std::ptrdiff_t
132	> super_t;
133
134	dir_adj_matrix_out_edge_iter() { }
135
136	dir_adj_matrix_out_edge_iter(
137	const MatrixIter& i
138	, const VertexDescriptor& src
139	, const VerticesSizeType& n
140	)
141	: super_t(i), m_src(src), m_targ(0), m_n(n)
142	{ }
143
144	void increment() {
145	++this->base_reference();
146	++m_targ;
147	}
148
149	inline EdgeDescriptor
150	dereference() const
151	{
152	return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
153	&get_property(*this->base()));
154	}
155	VertexDescriptor m_src, m_targ;
156	VerticesSizeType m_n;
157	};
158
159	//=======================================================================
160	// Undirected Out Edge Iterator
161
162	template <
163	typename VertexDescriptor, typename MatrixIter
164	, typename VerticesSizeType, typename EdgeDescriptor
165	>
166	struct undir_adj_matrix_out_edge_iter
167	: iterator_adaptor<
168	undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
169	, MatrixIter
170	, EdgeDescriptor
171	, use_default
172	, EdgeDescriptor
173	, std::ptrdiff_t
174	>
175	{
176	typedef iterator_adaptor<
177	undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
178	, MatrixIter
179	, EdgeDescriptor
180	, use_default
181	, EdgeDescriptor
182	, std::ptrdiff_t
183	> super_t;
184
185	undir_adj_matrix_out_edge_iter() { }
186
187	undir_adj_matrix_out_edge_iter(
188	const MatrixIter& i
189	, const VertexDescriptor& src
190	, const VerticesSizeType& n
191	)
192	: super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
193	{}
194
195	void increment()
196	{
197	if (m_targ < m_src) // first half
198	{
199	++this->base_reference();
200	}
201	else if (m_targ < m_n - 1)
202	{ // second half
203	++m_inc;
204	this->base_reference() += m_inc;
205	}
206	else
207	{ // past-the-end
208	this->base_reference() += m_n - m_src;
209	}
210	++m_targ;
211	}
212
213	inline EdgeDescriptor
214	dereference() const
215	{
216	return EdgeDescriptor(
217	get_edge_exists(*this->base(), 0), m_src, m_targ
218	, &get_property(*this->base())
219	);
220	}
221
222	VertexDescriptor m_src, m_inc, m_targ;
223	VerticesSizeType m_n;
224	};
225
226	//=======================================================================
227	// Edge Iterator
228
229	template <typename Directed, typename MatrixIter,
230	typename VerticesSizeType, typename EdgeDescriptor>
231	struct adj_matrix_edge_iter
232	: iterator_adaptor<
233	adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor>
234	, MatrixIter
235	, EdgeDescriptor
236	, use_default
237	, EdgeDescriptor
238	, std::ptrdiff_t
239	>
240	{
241	typedef iterator_adaptor<
242	adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor>
243	, MatrixIter
244	, EdgeDescriptor
245	, use_default
246	, EdgeDescriptor
247	, std::ptrdiff_t
248	> super_t;
249
250	adj_matrix_edge_iter() { }
251
252	adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n)
253	: super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }
254
255	void increment()
256	{
257	increment_dispatch(this->base_reference(), Directed());
258	}
259
260	void increment_dispatch(MatrixIter& i, directedS)
261	{
262	++i;
263	if (m_targ == m_n - 1)
264	{
265	m_targ = 0;
266	++m_src;
267	}
268	else
269	{
270	++m_targ;
271	}
272	}
273
274	void increment_dispatch(MatrixIter& i, undirectedS)
275	{
276	++i;
277	if (m_targ == m_src)
278	{
279	m_targ = 0;
280	++m_src;
281	}
282	else
283	{
284	++m_targ;
285	}
286	}
287
288	inline EdgeDescriptor
289	dereference() const
290	{
291	return EdgeDescriptor(
292	get_edge_exists(
293	this->base(), 0), m_src, m_targ, &get_property(this->base())
294	);
295	}
296
297	MatrixIter m_start;
298	VerticesSizeType m_src, m_targ, m_n;
299	};
300
301	} // namespace detail
302
303	//=========================================================================
304	// Adjacency Matrix Traits
305	template <typename Directed = directedS>
306	class adjacency_matrix_traits {
307	typedef typename Directed::is_bidir_t is_bidir;
308	typedef typename Directed::is_directed_t is_directed;
309	public:
310	typedef typename boost::ct_if_t<is_bidir,
311	bidirectional_tag,
312	typename boost::ct_if_t<is_directed,
313	directed_tag, undirected_tag
314	>::type
315	>::type directed_category;
316
317	typedef disallow_parallel_edge_tag edge_parallel_category;
318
319	typedef std::size_t vertex_descriptor;
320
321	typedef detail::matrix_edge_desc_impl<directed_category,
322	vertex_descriptor> edge_descriptor;
323	};
324
325	struct adjacency_matrix_class_tag { };
326
327	struct adj_matrix_traversal_tag :
328	public virtual adjacency_matrix_tag,
329	public virtual vertex_list_graph_tag,
330	public virtual incidence_graph_tag,
331	public virtual adjacency_graph_tag,
332	public virtual edge_list_graph_tag { };
333
334	//=========================================================================
335	// Adjacency Matrix Class
336	template <typename Directed = directedS,
337	typename VertexProperty = no_property,
338	typename EdgeProperty = no_property,
339	typename GraphProperty = no_property,
340	typename Allocator = std::allocator<bool> >
341	class adjacency_matrix {
342	typedef adjacency_matrix self;
343	typedef adjacency_matrix_traits<Directed> Traits;
344
345	public:
346	#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
347	typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type
348	vertex_property_type;
349	typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type
350	edge_property_type;
351
352	private:
353	typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged
354	maybe_vertex_bundled;
355
356	typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged
357	maybe_edge_bundled;
358
359	public:
360	// The types that are actually bundled
361	typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
362	no_vertex_bundle,
363	maybe_vertex_bundled>::type vertex_bundled;
364	typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
365	no_edge_bundle,
366	maybe_edge_bundled>::type edge_bundled;
367	#else
368	typedef EdgeProperty edge_property_type;
369	typedef VertexProperty vertex_property_type;
370	typedef no_vertex_bundle vertex_bundled;
371	typedef no_edge_bundle edge_bundled;
372	#endif
373
374	public: // should be private
375	typedef typename ct_if_t<typename has_property<edge_property_type>::type,
376	std::pair<bool, edge_property_type>, char>::type StoredEdge;
377	#if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) \|\| defined(BOOST_NO_STD_ALLOCATOR)
378	typedef std::vector<StoredEdge> Matrix;
379	#else
380	// This causes internal compiler error for MSVC
381	typedef typename Allocator::template rebind<StoredEdge>::other Alloc;
382	typedef std::vector<StoredEdge, Alloc> Matrix;
383	#endif
384	typedef typename Matrix::iterator MatrixIter;
385	typedef typename Matrix::size_type size_type;
386	public:
387	// Graph concept required types
388	typedef typename Traits::vertex_descriptor vertex_descriptor;
389	typedef typename Traits::edge_descriptor edge_descriptor;
390	typedef typename Traits::directed_category directed_category;
391	typedef typename Traits::edge_parallel_category edge_parallel_category;
392	typedef adj_matrix_traversal_tag traversal_category;
393
394	static vertex_descriptor null_vertex()
395	{
396	return (std::numeric_limits<vertex_descriptor>::max)();
397	}
398
399	//private: if friends worked, these would be private
400
401	typedef detail::dir_adj_matrix_out_edge_iter<
402	vertex_descriptor, MatrixIter, size_type, edge_descriptor
403	> DirOutEdgeIter;
404
405	typedef detail::undir_adj_matrix_out_edge_iter<
406	vertex_descriptor, MatrixIter, size_type, edge_descriptor
407	> UnDirOutEdgeIter;
408
409	typedef typename ct_if_t<
410	typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter
411	>::type unfiltered_out_edge_iter;
412
413	typedef detail::adj_matrix_edge_iter<
414	Directed, MatrixIter, size_type, edge_descriptor
415	> unfiltered_edge_iter;
416
417	public:
418
419	// IncidenceGraph concept required types
420	typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>
421	out_edge_iterator;
422
423	typedef size_type degree_size_type;
424
425	// BidirectionalGraph required types
426	typedef void in_edge_iterator;
427
428	// AdjacencyGraph required types
429	typedef typename adjacency_iterator_generator<self,
430	vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
431
432	// VertexListGraph required types
433	typedef size_type vertices_size_type;
434	typedef integer_range<vertex_descriptor> VertexList;
435	typedef typename VertexList::iterator vertex_iterator;
436
437	// EdgeListGrpah required types
438	typedef size_type edges_size_type;
439	typedef filter_iterator<
440	detail::does_edge_exist, unfiltered_edge_iter
441	> edge_iterator;
442
443	// PropertyGraph required types
444	typedef adjacency_matrix_class_tag graph_tag;
445
446	// Constructor required by MutableGraph
447	adjacency_matrix(vertices_size_type n_vertices)
448	: m_matrix(Directed::is_directed ?
449	(n_vertices * n_vertices)
450	: (n_vertices * (n_vertices + 1) / 2)),
451	m_vertex_set(0, n_vertices),
452	m_vertex_properties(n_vertices),
453	m_num_edges(0) { }
454
455	#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
456	// Directly access a vertex or edge bundle
457	vertex_bundled& operator[](vertex_descriptor v)
458	{ return get(vertex_bundle, *this)[v]; }
459
460	const vertex_bundled& operator[](vertex_descriptor v) const
461	{ return get(vertex_bundle, *this)[v]; }
462
463	edge_bundled& operator[](edge_descriptor e)
464	{ return get(edge_bundle, *this)[e]; }
465
466	const edge_bundled& operator[](edge_descriptor e) const
467	{ return get(edge_bundle, *this)[e]; }
468	#endif
469
470	//private: if friends worked, these would be private
471
472	typename Matrix::const_reference
473	get_edge(vertex_descriptor u, vertex_descriptor v) const {
474	if (Directed::is_directed)
475	return m_matrix[u * m_vertex_set.size() + v];
476	else {
477	if (v > u)
478	std::swap(u, v);
479	return m_matrix[u * (u + 1)/2 + v];
480	}
481	}
482	typename Matrix::reference
483	get_edge(vertex_descriptor u, vertex_descriptor v) {
484	if (Directed::is_directed)
485	return m_matrix[u * m_vertex_set.size() + v];
486	else {
487	if (v > u)
488	std::swap(u, v);
489	return m_matrix[u * (u + 1)/2 + v];
490	}
491	}
492
493	Matrix m_matrix;
494	VertexList m_vertex_set;
495	std::vector<vertex_property_type> m_vertex_properties;
496	size_type m_num_edges;
497	};
498
499	//=========================================================================
500	// Functions required by the AdjacencyMatrix concept
501
502	template <typename D, typename VP, typename EP, typename GP, typename A>
503	std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
504	bool>
505	edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
506	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
507	const adjacency_matrix<D,VP,EP,GP,A>& g)
508	{
509	bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);
510	typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
511	e(exists, u, v, &detail::get_property(g.get_edge(u,v)));
512	return std::make_pair(e, exists);
513	}
514
515	//=========================================================================
516	// Functions required by the IncidenceGraph concept
517
518	// O(1)
519	template <typename VP, typename EP, typename GP, typename A>
520	std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,
521	typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>
522	out_edges
523	(typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
524	const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
525	{
526	typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
527	Graph& g = const_cast<Graph&>(g_);
528	typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();
529	typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
530	typename Graph::MatrixIter l = f + g.m_vertex_set.size();
531	typename Graph::unfiltered_out_edge_iter
532	first(f, u, g.m_vertex_set.size())
533	, last(l, u, g.m_vertex_set.size());
534	detail::does_edge_exist pred;
535	typedef typename Graph::out_edge_iterator out_edge_iterator;
536	return std::make_pair(out_edge_iterator(pred, first, last),
537	out_edge_iterator(pred, last, last));
538	}
539
540	// O(1)
541	template <typename VP, typename EP, typename GP, typename A>
542	std::pair<
543	typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,
544	typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>
545	out_edges
546	(typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
547	const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
548	{
549	typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
550	Graph& g = const_cast<Graph&>(g_);
551	typename Graph::vertices_size_type offset = u * (u + 1) / 2;
552	typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
553	typename Graph::MatrixIter l = g.m_matrix.end();
554
555	typename Graph::unfiltered_out_edge_iter
556	first(f, u, g.m_vertex_set.size())
557	, last(l, u, g.m_vertex_set.size());
558
559	detail::does_edge_exist pred;
560	typedef typename Graph::out_edge_iterator out_edge_iterator;
561	return std::make_pair(out_edge_iterator(pred, first, last),
562	out_edge_iterator(pred, last, last));
563	}
564
565	// O(N)
566	template <typename D, typename VP, typename EP, typename GP, typename A>
567	typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
568	out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
569	const adjacency_matrix<D,VP,EP,GP,A>& g)
570	{
571	typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
572	typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;
573	for (tie(f, l) = out_edges(u, g); f != l; ++f)
574	++n;
575	return n;
576	}
577
578	// O(1)
579	template <typename D, typename VP, typename EP, typename GP, typename A,
580	typename Dir, typename Vertex>
581	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
582	source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
583	const adjacency_matrix<D,VP,EP,GP,A>&)
584	{
585	return e.m_source;
586	}
587
588	// O(1)
589	template <typename D, typename VP, typename EP, typename GP, typename A,
590	typename Dir, typename Vertex>
591	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
592	target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
593	const adjacency_matrix<D,VP,EP,GP,A>&)
594	{
595	return e.m_target;
596	}
597
598	//=========================================================================
599	// Functions required by the AdjacencyGraph concept
600
601	template <typename D, typename VP, typename EP, typename GP, typename A>
602	std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,
603	typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>
604	adjacent_vertices
605	(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
606	const adjacency_matrix<D,VP,EP,GP,A>& g_)
607	{
608	typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
609	const Graph& cg = static_cast<const Graph&>(g_);
610	Graph& g = const_cast<Graph&>(cg);
611	typedef typename Graph::adjacency_iterator adjacency_iterator;
612	typename Graph::out_edge_iterator first, last;
613	boost::tie(first, last) = out_edges(u, g);
614	return std::make_pair(adjacency_iterator(first, &g),
615	adjacency_iterator(last, &g));
616	}
617
618	//=========================================================================
619	// Functions required by the VertexListGraph concept
620
621	template <typename D, typename VP, typename EP, typename GP, typename A>
622	std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,
623	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>
624	vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {
625	typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
626	Graph& g = const_cast<Graph&>(g_);
627	return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());
628	}
629
630	template <typename D, typename VP, typename EP, typename GP, typename A>
631	typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type
632	num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {
633	return g.m_vertex_set.size();
634	}
635
636	//=========================================================================
637	// Functions required by the EdgeListGraph concept
638
639	template <typename D, typename VP, typename EP, typename GP, typename A>
640	std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,
641	typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>
642	edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)
643	{
644	typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
645	Graph& g = const_cast<Graph&>(g_);
646
647	typename Graph::unfiltered_edge_iter
648	first(g.m_matrix.begin(), g.m_matrix.begin(),
649	g.m_vertex_set.size()),
650	last(g.m_matrix.end(), g.m_matrix.begin(),
651	g.m_vertex_set.size());
652	detail::does_edge_exist pred;
653	typedef typename Graph::edge_iterator edge_iterator;
654	return std::make_pair(edge_iterator(pred, first, last),
655	edge_iterator(pred, last, last));
656	}
657
658	// O(1)
659	template <typename D, typename VP, typename EP, typename GP, typename A>
660	typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type
661	num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)
662	{
663	return g.m_num_edges;
664	}
665
666	//=========================================================================
667	// Functions required by the MutableGraph concept
668
669	// O(1)
670	template <typename D, typename VP, typename EP, typename GP, typename A>
671	std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
672	add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
673	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
674	const EP& ep,
675	adjacency_matrix<D,VP,EP,GP,A>& g)
676	{
677	typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
678	edge_descriptor;
679	if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
680	++(g.m_num_edges);
681	detail::set_property(g.get_edge(u,v), ep, 0);
682	detail::set_edge_exists(g.get_edge(u,v), true, 0);
683	return std::make_pair
684	(edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
685	true);
686	} else
687	return std::make_pair
688	(edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
689	false);
690	}
691	// O(1)
692	template <typename D, typename VP, typename EP, typename GP, typename A>
693	std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
694	add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
695	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
696	adjacency_matrix<D,VP,EP,GP,A>& g)
697	{
698	EP ep;
699	return add_edge(u, v, ep, g);
700	}
701
702	// O(1)
703	template <typename D, typename VP, typename EP, typename GP, typename A>
704	void
705	remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
706	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
707	adjacency_matrix<D,VP,EP,GP,A>& g)
708	{
709	--(g.m_num_edges);
710	detail::set_edge_exists(g.get_edge(u,v), false, 0);
711	}
712
713	// O(1)
714	template <typename D, typename VP, typename EP, typename GP, typename A>
715	void
716	remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,
717	adjacency_matrix<D,VP,EP,GP,A>& g)
718	{
719	remove_edge(source(e, g), target(e, g), g);
720	}
721
722
723	template <typename D, typename VP, typename EP, typename GP, typename A>
724	inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
725	add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
726	// UNDER CONSTRUCTION
727	assert(false);
728	return *vertices(g).first;
729	}
730
731	template <typename D, typename VP, typename EP, typename GP, typename A>
732	inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
733	add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {
734	// UNDER CONSTRUCTION
735	assert(false);
736	return *vertices(g).first;
737	}
738
739	template <typename D, typename VP, typename EP, typename GP, typename A>
740	inline void
741	remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
742	adjacency_matrix<D,VP,EP,GP,A>& g)
743	{
744	// UNDER CONSTRUCTION
745	assert(false);
746	}
747
748	// O(V)
749	template <typename VP, typename EP, typename GP, typename A>
750	void
751	clear_vertex
752	(typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
753	adjacency_matrix<directedS,VP,EP,GP,A>& g)
754	{
755	typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator
756	vi, vi_end;
757	for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
758	remove_edge(u, *vi, g);
759	for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
760	remove_edge(*vi, u, g);
761	}
762
763	// O(V)
764	template <typename VP, typename EP, typename GP, typename A>
765	void
766	clear_vertex
767	(typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
768	adjacency_matrix<undirectedS,VP,EP,GP,A>& g)
769	{
770	typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator
771	vi, vi_end;
772	for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
773	remove_edge(u, *vi, g);
774	}
775
776	//=========================================================================
777	// Vertex Property Map
778
779	template <typename GraphPtr, typename Vertex, typename T, typename R,
780	typename Tag>
781	class adj_matrix_vertex_property_map
782	: public put_get_helper<R,
783	adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >
784	{
785	public:
786	typedef T value_type;
787	typedef R reference;
788	typedef Vertex key_type;
789	typedef boost::lvalue_property_map_tag category;
790	adj_matrix_vertex_property_map() { }
791	adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { }
792	inline reference operator[](key_type v) const {
793	return get_property_value(m_g->m_vertex_properties[v], Tag());
794	}
795	GraphPtr m_g;
796	};
797
798	template <class Property, class Vertex>
799	struct adj_matrix_vertex_id_map
800	: public boost::put_get_helper<Vertex,
801	adj_matrix_vertex_id_map<Property, Vertex> >
802	{
803	typedef Vertex value_type;
804	typedef Vertex reference;
805	typedef Vertex key_type;
806	typedef boost::readable_property_map_tag category;
807	adj_matrix_vertex_id_map() { }
808	template <class Graph>
809	inline adj_matrix_vertex_id_map(const Graph&) { }
810	inline value_type operator[](key_type v) const { return v; }
811	};
812
813	namespace detail {
814
815	struct adj_matrix_any_vertex_pa {
816	template <class Tag, class Graph, class Property>
817	struct bind_ {
818	typedef typename property_value<Property,Tag>::type Value;
819	typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
820
821	typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,
822	Tag> type;
823	typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value,
824	const Value&, Tag> const_type;
825	};
826	};
827	struct adj_matrix_id_vertex_pa {
828	template <class Tag, class Graph, class Property>
829	struct bind_ {
830	typedef typename Graph::vertex_descriptor Vertex;
831	typedef adj_matrix_vertex_id_map<Property, Vertex> type;
832	typedef adj_matrix_vertex_id_map<Property, Vertex> const_type;
833	};
834	};
835
836	template <class Tag>
837	struct adj_matrix_choose_vertex_pa_helper {
838	typedef adj_matrix_any_vertex_pa type;
839	};
840	template <>
841	struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> {
842	typedef adj_matrix_id_vertex_pa type;
843	};
844
845	template <class Tag, class Graph, class Property>
846	struct adj_matrix_choose_vertex_pa {
847	typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper;
848	typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
849	typedef typename Bind::type type;
850	typedef typename Bind::const_type const_type;
851	};
852
853	struct adj_matrix_vertex_property_selector {
854	template <class Graph, class Property, class Tag>
855	struct bind_ {
856	typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice;
857	typedef typename Choice::type type;
858	typedef typename Choice::const_type const_type;
859	};
860	};
861
862	} // namespace detail
863
864	template <>
865	struct vertex_property_selector<adjacency_matrix_class_tag> {
866	typedef detail::adj_matrix_vertex_property_selector type;
867	};
868
869	//=========================================================================
870	// Edge Property Map
871
872
873	template <typename Directed, typename Property, typename Vertex,
874	typename T, typename R, typename Tag>
875	class adj_matrix_edge_property_map
876	: public put_get_helper<R,
877	adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >
878	{
879	public:
880	typedef T value_type;
881	typedef R reference;
882	typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type;
883	typedef boost::lvalue_property_map_tag category;
884	inline reference operator[](key_type e) const {
885	Property& p = (Property)e.get_property();
886	return get_property_value(p, Tag());
887	}
888	};
889	struct adj_matrix_edge_property_selector {
890	template <class Graph, class Property, class Tag>
891	struct bind_ {
892	typedef typename property_value<Property,Tag>::type T;
893	typedef typename Graph::vertex_descriptor Vertex;
894	typedef adj_matrix_edge_property_map<typename Graph::directed_category,
895	Property, Vertex, T, T&, Tag> type;
896	typedef adj_matrix_edge_property_map<typename Graph::directed_category,
897	Property, Vertex, T, const T&, Tag> const_type;
898	};
899	};
900	template <>
901	struct edge_property_selector<adjacency_matrix_class_tag> {
902	typedef adj_matrix_edge_property_selector type;
903	};
904
905	//=========================================================================
906	// Functions required by PropertyGraph
907
908	namespace detail {
909
910	template <typename Property, typename D, typename VP, typename EP,
911	typename GP, typename A>
912	typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
913	Property>::type
914	get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,
915	vertex_property_tag)
916	{
917	typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
918	typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
919	Property>::type PA;
920	return PA(&g);
921	}
922	template <typename Property, typename D, typename VP, typename EP,
923	typename GP, typename A>
924	typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
925	Property>::type
926	get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property,
927	edge_property_tag)
928	{
929	typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
930	Property>::type PA;
931	return PA();
932	}
933	template <typename Property, typename D, typename VP, typename EP,
934	typename GP, typename A>
935	typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
936	Property>::const_type
937	get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property,
938	vertex_property_tag)
939	{
940	typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
941	typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
942	Property>::const_type PA;
943	return PA(&g);
944	}
945	template <typename Property, typename D, typename VP, typename EP,
946	typename GP, typename A>
947	typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
948	Property>::const_type
949	get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property,
950	edge_property_tag)
951	{
952	typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
953	Property>::const_type PA;
954	return PA();
955	}
956
957	} // namespace detail
958
959	template <typename Property, typename D, typename VP, typename EP,
960	typename GP, typename A>
961	inline
962	typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type
963	get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g)
964	{
965	typedef typename property_kind<Property>::type Kind;
966	return detail::get_dispatch(g, p, Kind());
967	}
968
969	template <typename Property, typename D, typename VP, typename EP,
970	typename GP, typename A>
971	inline
972	typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
973	get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g)
974	{
975	typedef typename property_kind<Property>::type Kind;
976	return detail::get_dispatch(g, p, Kind());
977	}
978
979	template <typename Property, typename D, typename VP, typename EP,
980	typename GP, typename A, typename Key>
981	inline
982	typename property_traits<
983	typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
984	>::value_type
985	get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g,
986	const Key& key)
987	{
988	return get(get(p, g), key);
989	}
990
991	template <typename Property, typename D, typename VP, typename EP,
992	typename GP, typename A, typename Key, typename Value>
993	inline void
994	put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g,
995	const Key& key, const Value& value)
996	{
997	typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
998	typedef typename boost::property_map<Graph, Property>::type Map;
999	Map pmap = get(p, g);
1000	put(pmap, key, value);
1001	}
1002
1003	//=========================================================================
1004	// Other Functions
1005
1006	template <typename D, typename VP, typename EP, typename GP, typename A>
1007	typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1008	vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,
1009	const adjacency_matrix<D,VP,EP,GP,A>& g)
1010	{
1011	return n;
1012	}
1013
1014	// Support for bundled properties
1015	#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1016	template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1017	typename Allocator, typename T, typename Bundle>
1018	inline
1019	typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1020	T Bundle::*>::type
1021	get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g)
1022	{
1023	typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1024	T Bundle::*>::type
1025	result_type;
1026	return result_type(&g, p);
1027	}
1028
1029	template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1030	typename Allocator, typename T, typename Bundle>
1031	inline
1032	typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1033	T Bundle::*>::const_type
1034	get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g)
1035	{
1036	typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1037	T Bundle::*>::const_type
1038	result_type;
1039	return result_type(&g, p);
1040	}
1041
1042	template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1043	typename Allocator, typename T, typename Bundle, typename Key>
1044	inline T
1045	get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g,
1046	const Key& key)
1047	{
1048	return get(get(p, g), key);
1049	}
1050
1051	template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1052	typename Allocator, typename T, typename Bundle, typename Key>
1053	inline void
1054	put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g,
1055	const Key& key, const T& value)
1056	{
1057	put(get(p, g), key, value);
1058	}
1059
1060	#endif
1061
1062	} // namespace boost
1063
1064	#endif // BOOST_ADJACENCY_MATRIX_HPP

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: NonGTP/Boost/boost/graph/adjacency_matrix.hpp @ 857

Download in other formats: