Context Navigation

Back to Ticket #11714

Ticket #11714: subgraph.hpp

File subgraph.hpp, 38.7 KB (added by Stefan Hammer <s.hammer@…>, 7 years ago)
UPDATE: Boost unit test for the issue

Line
1	//=======================================================================
2	// Copyright 2001 University of Notre Dame.
3	// Authors: Jeremy G. Siek and Lie-Quan Lee
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_SUBGRAPH_HPP
11	#define BOOST_SUBGRAPH_HPP
12
13	// UNDER CONSTRUCTION
14
15	#include <boost/config.hpp>
16	#include <list>
17	#include <vector>
18	#include <map>
19	#include <boost/assert.hpp>
20	#include <boost/graph/graph_traits.hpp>
21	#include <boost/graph/graph_mutability_traits.hpp>
22	#include <boost/graph/properties.hpp>
23	#include <boost/iterator/indirect_iterator.hpp>
24
25	#include <boost/static_assert.hpp>
26	#include <boost/assert.hpp>
27	#include <boost/type_traits.hpp>
28	#include <boost/mpl/if.hpp>
29	#include <boost/mpl/or.hpp>
30
31	namespace boost {
32
33	struct subgraph_tag { };
34
35	/** @name Property Lookup
36	* The local_property and global_property functions are used to create
37	* structures that determine the lookup strategy for properties in subgraphs.
38	* Note that the nested kind member is used to help interoperate with actual
39	* Property types.
40	*/
41	//@{
42	template <typename T>
43	struct local_property
44	{
45	typedef T kind;
46	local_property(T x) : value(x) { }
47	T value;
48	};
49
50	template <typename T>
51	inline local_property<T> local(T x)
52	{ return local_property<T>(x); }
53
54	template <typename T>
55	struct global_property
56	{
57	typedef T kind;
58	global_property(T x) : value(x) { }
59	T value;
60	};
61
62	template <typename T>
63	inline global_property<T> global(T x)
64	{ return global_property<T>(x); }
65	//@}
66
67	// Invariants of an induced subgraph:
68	// - If vertex u is in subgraph g, then u must be in g.parent().
69	// - If edge e is in subgraph g, then e must be in g.parent().
70	// - If edge e=(u,v) is in the root graph, then edge e
71	// is also in any subgraph that contains both vertex u and v.
72
73	// The Graph template parameter must have a vertex_index and edge_index
74	// internal property. It is assumed that the vertex indices are assigned
75	// automatically by the graph during a call to add_vertex(). It is not
76	// assumed that the edge vertices are assigned automatically, they are
77	// explicitly assigned here.
78
79	template <typename Graph>
80	class subgraph {
81	typedef graph_traits<Graph> Traits;
82	typedef std::list<subgraph<Graph>*> ChildrenList;
83	public:
84	// Graph requirements
85	typedef typename Traits::vertex_descriptor vertex_descriptor;
86	typedef typename Traits::edge_descriptor edge_descriptor;
87	typedef typename Traits::directed_category directed_category;
88	typedef typename Traits::edge_parallel_category edge_parallel_category;
89	typedef typename Traits::traversal_category traversal_category;
90
91	// IncidenceGraph requirements
92	typedef typename Traits::out_edge_iterator out_edge_iterator;
93	typedef typename Traits::degree_size_type degree_size_type;
94
95	// AdjacencyGraph requirements
96	typedef typename Traits::adjacency_iterator adjacency_iterator;
97
98	// VertexListGraph requirements
99	typedef typename Traits::vertex_iterator vertex_iterator;
100	typedef typename Traits::vertices_size_type vertices_size_type;
101
102	// EdgeListGraph requirements
103	typedef typename Traits::edge_iterator edge_iterator;
104	typedef typename Traits::edges_size_type edges_size_type;
105
106	typedef typename Traits::in_edge_iterator in_edge_iterator;
107
108	typedef typename edge_property_type<Graph>::type edge_property_type;
109	typedef typename vertex_property_type<Graph>::type vertex_property_type;
110	typedef subgraph_tag graph_tag;
111	typedef Graph graph_type;
112	typedef typename graph_property_type<Graph>::type graph_property_type;
113
114	// Create the main graph, the root of the subgraph tree
115	subgraph()
116	: m_parent(0), m_edge_counter(0)
117	{ }
118
119	subgraph(const graph_property_type& p)
120	: m_graph(p), m_parent(0), m_edge_counter(0)
121	{ }
122
123	subgraph(vertices_size_type n, const graph_property_type& p = graph_property_type())
124	: m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
125	{
126	typename Graph::vertex_iterator v, v_end;
127	vertices_size_type i = 0;
128	for(boost::tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
129	m_global_vertex[i++] = *v;
130	}
131
132	// copy constructor
133	subgraph(const subgraph& x)
134	: m_parent(x.m_parent), m_edge_counter(x.m_edge_counter)
135	, m_global_vertex(x.m_global_vertex), m_global_edge(x.m_global_edge)
136	{
137	if(x.is_root())
138	{
139	m_graph = x.m_graph;
140	}
141	// Do a deep copy (recursive).
142	// Only the root graph is copied, the subgraphs contain
143	// only references to the global vertices they own.
144	typename subgraph<Graph>::children_iterator i,i_end;
145	boost::tie(i,i_end) = x.children();
146	for(; i != i_end; ++i)
147	{
148	subgraph<Graph> child = this->create_subgraph();
149	child = *i;
150	vertex_iterator vi,vi_end;
151	boost::tie(vi,vi_end) = vertices(*i);
152	for (;vi!=vi_end;++vi)
153	{
154	add_vertex(*vi,child);
155	}
156	}
157	}
158
159
160	~subgraph() {
161	for(typename ChildrenList::iterator i = m_children.begin();
162	i != m_children.end(); ++i)
163	{
164	delete *i;
165	}
166	}
167
168	// Return a null vertex descriptor for the graph.
169	static vertex_descriptor null_vertex()
170	{ return Traits::null_vertex(); }
171
172
173	// Create a subgraph
174	subgraph<Graph>& create_subgraph() {
175	m_children.push_back(new subgraph<Graph>());
176	m_children.back()->m_parent = this;
177	return *m_children.back();
178	}
179
180	// Create a subgraph with the specified vertex set.
181	template <typename VertexIterator>
182	subgraph<Graph>& create_subgraph(VertexIterator first, VertexIterator last) {
183	m_children.push_back(new subgraph<Graph>());
184	m_children.back()->m_parent = this;
185	for(; first != last; ++first) {
186	add_vertex(first, m_children.back());
187	}
188	return *m_children.back();
189	}
190
191	// local <-> global descriptor conversion functions
192	vertex_descriptor local_to_global(vertex_descriptor u_local) const
193	{ return is_root() ? u_local : m_global_vertex[u_local]; }
194
195	vertex_descriptor global_to_local(vertex_descriptor u_global) const {
196	vertex_descriptor u_local; bool in_subgraph;
197	if (is_root()) return u_global;
198	boost::tie(u_local, in_subgraph) = this->find_vertex(u_global);
199	BOOST_ASSERT(in_subgraph == true);
200	return u_local;
201	}
202
203	edge_descriptor local_to_global(edge_descriptor e_local) const
204	{ return is_root() ? e_local : m_global_edge[get(get(edge_index, m_graph), e_local)]; }
205
206	edge_descriptor global_to_local(edge_descriptor e_global) const
207	{ return is_root() ? e_global : (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second; }
208
209	// Is vertex u (of the root graph) contained in this subgraph?
210	// If so, return the matching local vertex.
211	std::pair<vertex_descriptor, bool>
212	find_vertex(vertex_descriptor u_global) const {
213	if (is_root()) return std::make_pair(u_global, true);
214	typename LocalVertexMap::const_iterator i = m_local_vertex.find(u_global);
215	bool valid = i != m_local_vertex.end();
216	return std::make_pair((valid ? (*i).second : null_vertex()), valid);
217	}
218
219	// Is edge e (of the root graph) contained in this subgraph?
220	// If so, return the matching local edge.
221	std::pair<edge_descriptor, bool>
222	find_edge(edge_descriptor e_global) const {
223	if (is_root()) return std::make_pair(e_global, true);
224	typename LocalEdgeMap::const_iterator i =
225	m_local_edge.find(get(get(edge_index, root().m_graph), e_global));
226	bool valid = i != m_local_edge.end();
227	return std::make_pair((valid ? (*i).second : edge_descriptor()), valid);
228	}
229
230	// Return the parent graph.
231	subgraph& parent() { return *m_parent; }
232	const subgraph& parent() const { return *m_parent; }
233
234	// Return true if this is the root subgraph
235	bool is_root() const { return m_parent == 0; }
236
237	// Return the root graph of the subgraph tree.
238	subgraph& root()
239	{ return is_root() ? *this : m_parent->root(); }
240
241	const subgraph& root() const
242	{ return is_root() ? *this : m_parent->root(); }
243
244	// Return the children subgraphs of this graph/subgraph.
245	// Use a list of pointers because the VC++ std::list doesn't like
246	// storing incomplete type.
247	typedef indirect_iterator<
248	typename ChildrenList::const_iterator
249	, subgraph<Graph>
250	, std::bidirectional_iterator_tag
251	>
252	children_iterator;
253
254	typedef indirect_iterator<
255	typename ChildrenList::const_iterator
256	, subgraph<Graph> const
257	, std::bidirectional_iterator_tag
258	>
259	const_children_iterator;
260
261	std::pair<const_children_iterator, const_children_iterator> children() const {
262	return std::make_pair(const_children_iterator(m_children.begin()),
263	const_children_iterator(m_children.end()));
264	}
265
266	std::pair<children_iterator, children_iterator> children() {
267	return std::make_pair(children_iterator(m_children.begin()),
268	children_iterator(m_children.end()));
269	}
270
271	std::size_t num_children() const { return m_children.size(); }
272
273	#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
274	// Defualt property access delegates the lookup to global properties.
275	template <typename Descriptor>
276	typename graph::detail::bundled_result<Graph, Descriptor>::type&
277	operator[](Descriptor x)
278	{ return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)]; }
279
280	template <typename Descriptor>
281	typename graph::detail::bundled_result<Graph, Descriptor>::type const&
282	operator[](Descriptor x) const
283	{ return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)]; }
284
285	// Local property access returns the local property of the given descripor.
286	template <typename Descriptor>
287	typename graph::detail::bundled_result<Graph, Descriptor>::type&
288	operator[](local_property<Descriptor> x)
289	{ return m_graph[x.value]; }
290
291	template <typename Descriptor>
292	typename graph::detail::bundled_result<Graph, Descriptor>::type const&
293	operator[](local_property<Descriptor> x) const
294	{ return m_graph[x.value]; }
295
296	// Global property access returns the global property associated with the
297	// given descriptor. This is an alias for the default bundled property
298	// access operations.
299	template <typename Descriptor>
300	typename graph::detail::bundled_result<Graph, Descriptor>::type&
301	operator[](global_property<Descriptor> x)
302	{ return (*this)[x.value]; }
303
304	template <typename Descriptor>
305	typename graph::detail::bundled_result<Graph, Descriptor>::type const&
306	operator[](global_property<Descriptor> x) const
307	{ return (*this)[x.value]; }
308
309	#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
310
311	// private:
312	typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap;
313	typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type;
314	BOOST_STATIC_ASSERT((!is_same<edge_index_type,
315	boost::detail::error_property_not_found>::value));
316
317	private:
318	typedef std::vector<vertex_descriptor> GlobalVertexList;
319	typedef std::vector<edge_descriptor> GlobalEdgeList;
320	typedef std::map<vertex_descriptor, vertex_descriptor> LocalVertexMap;
321	typedef std::map<edge_index_type, edge_descriptor> LocalEdgeMap;
322	// TODO: Should the LocalVertexMap be: map<index_type, descriptor>?
323	// TODO: Can we relax the indexing requirement if both descriptors are
324	// LessThanComparable?
325	// TODO: Should we really be using unorderd_map for improved lookup times?
326
327	public: // Probably shouldn't be public....
328	Graph m_graph;
329	subgraph<Graph>* m_parent;
330	edge_index_type m_edge_counter; // for generating unique edge indices
331	ChildrenList m_children;
332	GlobalVertexList m_global_vertex; // local -> global
333	LocalVertexMap m_local_vertex; // global -> local
334	GlobalEdgeList m_global_edge; // local -> global
335	LocalEdgeMap m_local_edge; // global -> local
336
337	edge_descriptor local_add_edge(vertex_descriptor u_local,
338	vertex_descriptor v_local,
339	edge_descriptor e_global)
340	{
341	edge_descriptor e_local;
342	bool inserted;
343	boost::tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
344	put(edge_index, m_graph, e_local, m_edge_counter++);
345	m_global_edge.push_back(e_global);
346	m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
347	return e_local;
348	}
349	};
350
351	template <typename Graph>
352	struct vertex_bundle_type<subgraph<Graph> >
353	: vertex_bundle_type<Graph>
354	{ };
355
356	template<typename Graph>
357	struct edge_bundle_type<subgraph<Graph> >
358	: edge_bundle_type<Graph>
359	{ };
360
361	template<typename Graph>
362	struct graph_bundle_type<subgraph<Graph> >
363	: graph_bundle_type<Graph>
364	{ };
365
366	//===========================================================================
367	// Functions special to the Subgraph Class
368
369
370	namespace detail {
371
372	template <typename G>
373	typename subgraph<G>::vertex_descriptor
374	add_vertex_recur_up(typename subgraph<G>::vertex_descriptor u_global,
375	subgraph<G>& g)
376	{
377	if (!g.is_root()) {
378	if (!g.find_vertex(u_global).second) {
379	typename subgraph<G>::vertex_descriptor u_local, v_global;
380	typename subgraph<G>::edge_descriptor e_global;
381
382	add_vertex_recur_up(u_global, g.parent());
383
384	u_local = add_vertex(g.m_graph);
385	g.m_global_vertex.push_back(u_global);
386	g.m_local_vertex[u_global] = u_local;
387
388	subgraph<G>& r = g.root();
389
390	// remember edge global and local maps
391	{
392	typename subgraph<G>::out_edge_iterator ei, ei_end;
393	for (boost::tie(ei, ei_end) = out_edges(u_global, r);
394	ei != ei_end; ++ei) {
395	e_global = *ei;
396	v_global = target(e_global, r);
397	if (g.find_vertex(v_global).second == true)
398	g.local_add_edge(u_local, g.global_to_local(v_global), e_global);
399	}
400	}
401	if (is_directed(g)) { // not necessary for undirected graph
402	typename subgraph<G>::vertex_iterator vi, vi_end;
403	typename subgraph<G>::out_edge_iterator ei, ei_end;
404	for(boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
405	v_global = *vi;
406	if (v_global == u_global)
407	continue; // don't insert self loops twice!
408	if (!g.find_vertex(v_global).second)
409	continue; // not a subgraph vertex => try next one
410	for(boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
411	e_global = *ei;
412	if(target(e_global, r) == u_global) {
413	g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
414	}
415	}
416	}
417	}
418	return u_local;
419	} else {
420	return g.find_vertex(u_global).first;
421	}
422	} else {
423	return u_global;
424	}
425	}
426
427	} // namespace detail
428
429
430	template <typename G>
431	typename subgraph<G>::vertex_descriptor
432	add_vertex(typename subgraph<G>::vertex_descriptor u_global,
433	subgraph<G>& g)
434	{
435	BOOST_ASSERT(!g.is_root());
436	typename subgraph<G>::vertex_descriptor u_local;
437
438	u_local = detail::add_vertex_recur_up(u_global, g);
439
440	return u_local;
441	}
442
443	// NOTE: Descriptors are local unless otherwise noted.
444
445	//===========================================================================
446	// Functions required by the IncidenceGraph concept
447
448	template <typename G>
449	std::pair<typename graph_traits<G>::out_edge_iterator,
450	typename graph_traits<G>::out_edge_iterator>
451	out_edges(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
452	{ return out_edges(v, g.m_graph); }
453
454	template <typename G>
455	typename graph_traits<G>::degree_size_type
456	out_degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
457	{ return out_degree(v, g.m_graph); }
458
459	template <typename G>
460	typename graph_traits<G>::vertex_descriptor
461	source(typename graph_traits<G>::edge_descriptor e, const subgraph<G>& g)
462	{ return source(e, g.m_graph); }
463
464	template <typename G>
465	typename graph_traits<G>::vertex_descriptor
466	target(typename graph_traits<G>::edge_descriptor e, const subgraph<G>& g)
467	{ return target(e, g.m_graph); }
468
469	//===========================================================================
470	// Functions required by the BidirectionalGraph concept
471
472	template <typename G>
473	std::pair<typename graph_traits<G>::in_edge_iterator,
474	typename graph_traits<G>::in_edge_iterator>
475	in_edges(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
476	{ return in_edges(v, g.m_graph); }
477
478	template <typename G>
479	typename graph_traits<G>::degree_size_type
480	in_degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
481	{ return in_degree(v, g.m_graph); }
482
483	template <typename G>
484	typename graph_traits<G>::degree_size_type
485	degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
486	{ return degree(v, g.m_graph); }
487
488	//===========================================================================
489	// Functions required by the AdjacencyGraph concept
490
491	template <typename G>
492	std::pair<typename subgraph<G>::adjacency_iterator,
493	typename subgraph<G>::adjacency_iterator>
494	adjacent_vertices(typename subgraph<G>::vertex_descriptor v, const subgraph<G>& g)
495	{ return adjacent_vertices(v, g.m_graph); }
496
497	//===========================================================================
498	// Functions required by the VertexListGraph concept
499
500	template <typename G>
501	std::pair<typename subgraph<G>::vertex_iterator,
502	typename subgraph<G>::vertex_iterator>
503	vertices(const subgraph<G>& g)
504	{ return vertices(g.m_graph); }
505
506	template <typename G>
507	typename subgraph<G>::vertices_size_type
508	num_vertices(const subgraph<G>& g)
509	{ return num_vertices(g.m_graph); }
510
511	//===========================================================================
512	// Functions required by the EdgeListGraph concept
513
514	template <typename G>
515	std::pair<typename subgraph<G>::edge_iterator,
516	typename subgraph<G>::edge_iterator>
517	edges(const subgraph<G>& g)
518	{ return edges(g.m_graph); }
519
520	template <typename G>
521	typename subgraph<G>::edges_size_type
522	num_edges(const subgraph<G>& g)
523	{ return num_edges(g.m_graph); }
524
525	//===========================================================================
526	// Functions required by the AdjacencyMatrix concept
527
528	template <typename G>
529	std::pair<typename subgraph<G>::edge_descriptor, bool>
530	edge(typename subgraph<G>::vertex_descriptor u,
531	typename subgraph<G>::vertex_descriptor v,
532	const subgraph<G>& g)
533	{ return edge(u, v, g.m_graph); }
534
535	//===========================================================================
536	// Functions required by the MutableGraph concept
537
538	namespace detail {
539
540	template <typename Vertex, typename Edge, typename Graph>
541	void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
542	subgraph<Graph>& g);
543
544	template <typename Vertex, typename Edge, typename Children, typename G>
545	void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
546	Children& c, subgraph<G>* orig)
547	{
548	for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
549	if ((*i)->find_vertex(u_global).second &&
550	(*i)->find_vertex(v_global).second)
551	{
552	add_edge_recur_down(u_global, v_global, e_global, **i, orig);
553	}
554	}
555	}
556
557	template <typename Vertex, typename Edge, typename Graph>
558	void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
559	subgraph<Graph>& g, subgraph<Graph>* orig)
560	{
561	if(&g != orig ) {
562	// add local edge only if u_global and v_global are in subgraph g
563	Vertex u_local, v_local;
564	bool u_in_subgraph, v_in_subgraph;
565	boost::tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
566	boost::tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
567	if(u_in_subgraph && v_in_subgraph) {
568	g.local_add_edge(u_local, v_local, e_global);
569	}
570	}
571	children_add_edge(u_global, v_global, e_global, g.m_children, orig);
572	}
573
574	template <typename Vertex, typename Graph>
575	std::pair<typename subgraph<Graph>::edge_descriptor, bool>
576	add_edge_recur_up(Vertex u_global, Vertex v_global,
577	const typename Graph::edge_property_type& ep,
578	subgraph<Graph>& g, subgraph<Graph>* orig)
579	{
580	if(g.is_root()) {
581	typename subgraph<Graph>::edge_descriptor e_global;
582	bool inserted;
583	boost::tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);
584	put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
585	g.m_global_edge.push_back(e_global);
586	children_add_edge(u_global, v_global, e_global, g.m_children, orig);
587	return std::make_pair(e_global, inserted);
588	} else {
589	return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
590	}
591	}
592
593	} // namespace detail
594
595	// Add an edge to the subgraph g, specified by the local vertex descriptors u
596	// and v. In addition, the edge will be added to any (all) other subgraphs that
597	// contain vertex descriptors u and v.
598
599	template <typename G>
600	std::pair<typename subgraph<G>::edge_descriptor, bool>
601	add_edge(typename subgraph<G>::vertex_descriptor u,
602	typename subgraph<G>::vertex_descriptor v,
603	const typename G::edge_property_type& ep,
604	subgraph<G>& g)
605	{
606	if (g.is_root()) {
607	// u and v are really global
608	return detail::add_edge_recur_up(u, v, ep, g, &g);
609	} else {
610	typename subgraph<G>::edge_descriptor e_local, e_global;
611	bool inserted;
612	boost::tie(e_global, inserted) =
613	detail::add_edge_recur_up(g.local_to_global(u),
614	g.local_to_global(v),
615	ep, g, &g);
616	e_local = g.local_add_edge(u, v, e_global);
617	return std::make_pair(e_local, inserted);
618	}
619	}
620
621	template <typename G>
622	std::pair<typename subgraph<G>::edge_descriptor, bool>
623	add_edge(typename subgraph<G>::vertex_descriptor u,
624	typename subgraph<G>::vertex_descriptor v,
625	subgraph<G>& g)
626	{ return add_edge(u, v, typename G::edge_property_type(), g); }
627
628	namespace detail {
629	//-------------------------------------------------------------------------
630	// implementation of remove_edge(u,v,g)
631	template <typename Vertex, typename Graph>
632	void remove_edge_recur_down(Vertex u_global, Vertex v_global,
633	subgraph<Graph>& g);
634
635	template <typename Vertex, typename Children>
636	void children_remove_edge(Vertex u_global, Vertex v_global,
637	Children& c)
638	{
639	for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
640	if((*i)->find_vertex(u_global).second &&
641	(*i)->find_vertex(v_global).second)
642	{
643	remove_edge_recur_down(u_global, v_global, **i);
644	}
645	}
646	}
647
648	template <typename Vertex, typename Graph>
649	void remove_edge_recur_down(Vertex u_global, Vertex v_global,
650	subgraph<Graph>& g)
651	{
652	Vertex u_local, v_local;
653	u_local = g.m_local_vertex[u_global];
654	v_local = g.m_local_vertex[v_global];
655	remove_edge(u_local, v_local, g.m_graph);
656	children_remove_edge(u_global, v_global, g.m_children);
657	}
658
659	template <typename Vertex, typename Graph>
660	void remove_edge_recur_up(Vertex u_global, Vertex v_global,
661	subgraph<Graph>& g)
662	{
663	if(g.is_root()) {
664	remove_edge(u_global, v_global, g.m_graph);
665	children_remove_edge(u_global, v_global, g.m_children);
666	} else {
667	remove_edge_recur_up(u_global, v_global, *g.m_parent);
668	}
669	}
670
671	//-------------------------------------------------------------------------
672	// implementation of remove_edge(e,g)
673
674	template <typename G, typename Edge, typename Children>
675	void children_remove_edge(Edge e_global, Children& c)
676	{
677	for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
678	std::pair<typename subgraph<G>::edge_descriptor, bool> found =
679	(*i)->find_edge(e_global);
680	if (!found.second) {
681	continue;
682	}
683	children_remove_edge<G>(e_global, (*i)->m_children);
684	remove_edge(found.first, (*i)->m_graph);
685	}
686	}
687
688	} // namespace detail
689
690	template <typename G>
691	void
692	remove_edge(typename subgraph<G>::vertex_descriptor u,
693	typename subgraph<G>::vertex_descriptor v,
694	subgraph<G>& g)
695	{
696	if(g.is_root()) {
697	detail::remove_edge_recur_up(u, v, g);
698	} else {
699	detail::remove_edge_recur_up(g.local_to_global(u),
700	g.local_to_global(v), g);
701	}
702	}
703
704	template <typename G>
705	void
706	remove_edge(typename subgraph<G>::edge_descriptor e, subgraph<G>& g)
707	{
708	typename subgraph<G>::edge_descriptor e_global = g.local_to_global(e);
709	#ifndef NDEBUG
710	std::pair<typename subgraph<G>::edge_descriptor, bool> fe = g.find_edge(e_global);
711	BOOST_ASSERT(fe.second && fe.first == e);
712	#endif //NDEBUG
713	subgraph<G> &root = g.root(); // chase to root
714	detail::children_remove_edge<G>(e_global, root.m_children);
715	remove_edge(e_global, root.m_graph); // kick edge from root
716	}
717
718	// This is slow, but there may not be a good way to do it safely otherwise
719	template <typename Predicate, typename G>
720	void
721	remove_edge_if(Predicate p, subgraph<G>& g) {
722	while (true) {
723	bool any_removed = false;
724	typedef typename subgraph<G>::edge_iterator ei_type;
725	for (std::pair<ei_type, ei_type> ep = edges(g);
726	ep.first != ep.second; ++ep.first) {
727	if (p(*ep.first)) {
728	any_removed = true;
729	remove_edge(*ep.first, g);
730	break; /* Since iterators may be invalidated */
731	}
732	}
733	if (!any_removed) break;
734	}
735	}
736
737	template <typename G>
738	void
739	clear_vertex(typename subgraph<G>::vertex_descriptor v, subgraph<G>& g) {
740	while (true) {
741	typedef typename subgraph<G>::out_edge_iterator oei_type;
742	std::pair<oei_type, oei_type> p = out_edges(v, g);
743	if (p.first == p.second) break;
744	remove_edge(*p.first, g);
745	}
746	}
747
748	namespace detail {
749	template <typename G>
750	typename subgraph<G>::vertex_descriptor
751	add_vertex_recur_up(subgraph<G>& g)
752	{
753	typename subgraph<G>::vertex_descriptor u_local, u_global;
754	if (g.is_root()) {
755	u_global = add_vertex(g.m_graph);
756	g.m_global_vertex.push_back(u_global);
757	} else {
758	u_global = add_vertex_recur_up(*g.m_parent);
759	u_local = add_vertex(g.m_graph);
760	g.m_global_vertex.push_back(u_global);
761	g.m_local_vertex[u_global] = u_local;
762	}
763	return u_global;
764	}
765	} // namespace detail
766
767	template <typename G>
768	typename subgraph<G>::vertex_descriptor
769	add_vertex(subgraph<G>& g)
770	{
771	typename subgraph<G>::vertex_descriptor u_local, u_global;
772	if(g.is_root()) {
773	u_global = add_vertex(g.m_graph);
774	g.m_global_vertex.push_back(u_global);
775	u_local = u_global;
776	} else {
777	u_global = detail::add_vertex_recur_up(g.parent());
778	u_local = add_vertex(g.m_graph);
779	g.m_global_vertex.push_back(u_global);
780	g.m_local_vertex[u_global] = u_local;
781	}
782	return u_local;
783	}
784
785
786	#if 0
787	// TODO: Under Construction
788	template <typename G>
789	void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
790	{ BOOST_ASSERT(false); }
791	#endif
792
793	//===========================================================================
794	// Functions required by the PropertyGraph concept
795
796	/**
797	* The global property map returns the global properties associated with local
798	* descriptors.
799	*/
800	template <typename GraphPtr, typename PropertyMap, typename Tag>
801	class subgraph_global_property_map
802	: public put_get_helper<
803	typename property_traits<PropertyMap>::reference,
804	subgraph_global_property_map<GraphPtr, PropertyMap, Tag>
805	>
806	{
807	typedef property_traits<PropertyMap> Traits;
808	public:
809	typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
810	readable_property_map_tag,
811	typename Traits::category>::type
812	category;
813	typedef typename Traits::value_type value_type;
814	typedef typename Traits::key_type key_type;
815	typedef typename Traits::reference reference;
816
817	subgraph_global_property_map()
818	{ }
819
820	subgraph_global_property_map(GraphPtr g, Tag tag)
821	: m_g(g), m_tag(tag)
822	{ }
823
824	reference operator[](key_type e) const {
825	PropertyMap pmap = get(m_tag, m_g->root().m_graph);
826	return m_g->is_root()
827	? pmap[e]
828	: pmap[m_g->local_to_global(e)];
829	}
830
831	GraphPtr m_g;
832	Tag m_tag;
833	};
834
835	/**
836	* The local property map returns the local property associated with the local
837	* descriptors.
838	*/
839	template <typename GraphPtr, typename PropertyMap, typename Tag>
840	class subgraph_local_property_map
841	: public put_get_helper<
842	typename property_traits<PropertyMap>::reference,
843	subgraph_local_property_map<GraphPtr, PropertyMap, Tag>
844	>
845	{
846	typedef property_traits<PropertyMap> Traits;
847	public:
848	typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
849	readable_property_map_tag,
850	typename Traits::category>::type
851	category;
852	typedef typename Traits::value_type value_type;
853	typedef typename Traits::key_type key_type;
854	typedef typename Traits::reference reference;
855
856	typedef Tag tag;
857	typedef PropertyMap pmap;
858
859	subgraph_local_property_map()
860	{ }
861
862	subgraph_local_property_map(GraphPtr g, Tag tag)
863	: m_g(g), m_tag(tag)
864	{ }
865
866	reference operator[](key_type e) const {
867	// Get property map on the underlying graph.
868	PropertyMap pmap = get(m_tag, m_g->m_graph);
869	return pmap[e];
870	}
871
872	GraphPtr m_g;
873	Tag m_tag;
874	};
875
876	namespace detail {
877	// Extract the actual tags from local or global property maps so we don't
878	// try to find non-properties.
879	template <typename P> struct extract_lg_tag { typedef P type; };
880	template <typename P> struct extract_lg_tag< local_property<P> > {
881	typedef P type;
882	};
883	template <typename P> struct extract_lg_tag< global_property<P> > {
884	typedef P type;
885	};
886
887	// NOTE: Mysterious Property template parameter unused in both metafunction
888	// classes.
889	struct subgraph_global_pmap {
890	template <class Tag, class SubGraph, class Property>
891	struct bind_ {
892	typedef typename SubGraph::graph_type Graph;
893	typedef SubGraph* SubGraphPtr;
894	typedef const SubGraph* const_SubGraphPtr;
895	typedef typename extract_lg_tag<Tag>::type TagType;
896	typedef typename property_map<Graph, TagType>::type PMap;
897	typedef typename property_map<Graph, TagType>::const_type const_PMap;
898	public:
899	typedef subgraph_global_property_map<SubGraphPtr, PMap, TagType> type;
900	typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, TagType>
901	const_type;
902	};
903	};
904
905	struct subgraph_local_pmap {
906	template <class Tag, class SubGraph, class Property>
907	struct bind_ {
908	typedef typename SubGraph::graph_type Graph;
909	typedef SubGraph* SubGraphPtr;
910	typedef const SubGraph* const_SubGraphPtr;
911	typedef typename extract_lg_tag<Tag>::type TagType;
912	typedef typename property_map<Graph, TagType>::type PMap;
913	typedef typename property_map<Graph, TagType>::const_type const_PMap;
914	public:
915	typedef subgraph_local_property_map<SubGraphPtr, PMap, TagType> type;
916	typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, TagType>
917	const_type;
918	};
919	};
920
921	// These metafunctions select the corresponding metafunctions above, and
922	// are used by the choose_pmap metafunction below to specialize the choice
923	// of local/global property map. By default, we defer to the global
924	// property.
925	template <class Tag>
926	struct subgraph_choose_pmap_helper {
927	typedef subgraph_global_pmap type;
928	};
929	template <class Tag>
930	struct subgraph_choose_pmap_helper< local_property<Tag> > {
931	typedef subgraph_local_pmap type;
932	};
933	template <class Tag>
934	struct subgraph_choose_pmap_helper< global_property<Tag> > {
935	typedef subgraph_global_pmap type;
936	};
937
938	// As above, unless we're requesting vertex_index_t. Then it's always a
939	// local property map. This enables the correct translation of descriptors
940	// between local and global layers.
941	template <>
942	struct subgraph_choose_pmap_helper<vertex_index_t> {
943	typedef subgraph_local_pmap type;
944	};
945	template <>
946	struct subgraph_choose_pmap_helper< local_property<vertex_index_t> > {
947	typedef subgraph_local_pmap type;
948	};
949	template <>
950	struct subgraph_choose_pmap_helper< global_property<vertex_index_t> > {
951	typedef subgraph_local_pmap type;
952	};
953
954	// Determine the kind of property. If SameType<Tag, vertex_index_t>, then
955	// the property lookup is always local. Otherwise, the lookup is global.
956	// NOTE: Property parameter is basically unused.
957	template <class Tag, class Graph, class Property>
958	struct subgraph_choose_pmap {
959	typedef typename subgraph_choose_pmap_helper<Tag>::type Helper;
960	typedef typename Helper::template bind_<Tag, Graph, Property> Bind;
961	typedef typename Bind::type type;
962	typedef typename Bind::const_type const_type;
963	};
964
965	// Used by the vertex/edge property selectors to determine the kind(s) of
966	// property maps used by the property_map type generator.
967	struct subgraph_property_generator {
968	template <class SubGraph, class Property, class Tag>
969	struct bind_ {
970	typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice;
971	typedef typename Choice::type type;
972	typedef typename Choice::const_type const_type;
973	};
974	};
975
976	} // namespace detail
977
978	template <>
979	struct vertex_property_selector<subgraph_tag> {
980	typedef detail::subgraph_property_generator type;
981	};
982
983	template <>
984	struct edge_property_selector<subgraph_tag> {
985	typedef detail::subgraph_property_generator type;
986	};
987
988	// ==================================================
989	// get(p, g), get(p, g, k), and put(p, g, k, v)
990	// ==================================================
991	template <typename G, typename Property>
992	typename property_map<subgraph<G>, Property>::type
993	get(Property p, subgraph<G>& g) {
994	typedef typename property_map< subgraph<G>, Property>::type PMap;
995	return PMap(&g, p);
996	}
997
998	template <typename G, typename Property>
999	typename property_map<subgraph<G>, Property>::const_type
1000	get(Property p, const subgraph<G>& g) {
1001	typedef typename property_map< subgraph<G>, Property>::const_type PMap;
1002	return PMap(&g, p);
1003	}
1004
1005	template <typename G, typename Property, typename Key>
1006	typename property_traits<
1007	typename property_map<subgraph<G>, Property>::const_type
1008	>::value_type
1009	get(Property p, const subgraph<G>& g, const Key& k) {
1010	typedef typename property_map< subgraph<G>, Property>::const_type PMap;
1011	PMap pmap(&g, p);
1012	return pmap[k];
1013	}
1014
1015	template <typename G, typename Property, typename Key, typename Value>
1016	void put(Property p, subgraph<G>& g, const Key& k, const Value& val) {
1017	typedef typename property_map< subgraph<G>, Property>::type PMap;
1018	PMap pmap(&g, p);
1019	pmap[k] = val;
1020	}
1021
1022	// ==================================================
1023	// get(global(p), g)
1024	// NOTE: get(global(p), g, k) and put(global(p), g, k, v) not supported
1025	// ==================================================
1026	template <typename G, typename Property>
1027	typename property_map<subgraph<G>, global_property<Property> >::type
1028	get(global_property<Property> p, subgraph<G>& g) {
1029	typedef typename property_map<
1030	subgraph<G>, global_property<Property>
1031	>::type Map;
1032	return Map(&g, p.value);
1033	}
1034
1035	template <typename G, typename Property>
1036	typename property_map<subgraph<G>, global_property<Property> >::const_type
1037	get(global_property<Property> p, const subgraph<G>& g) {
1038	typedef typename property_map<
1039	subgraph<G>, global_property<Property>
1040	>::const_type Map;
1041	return Map(&g, p.value);
1042	}
1043
1044	// ==================================================
1045	// get(local(p), g)
1046	// NOTE: get(local(p), g, k) and put(local(p), g, k, v) not supported
1047	// ==================================================
1048	template <typename G, typename Property>
1049	typename property_map<subgraph<G>, local_property<Property> >::type
1050	get(local_property<Property> p, subgraph<G>& g) {
1051	typedef typename property_map<
1052	subgraph<G>, local_property<Property>
1053	>::type Map;
1054	return Map(&g, p.value);
1055	}
1056
1057	template <typename G, typename Property>
1058	typename property_map<subgraph<G>, local_property<Property> >::const_type
1059	get(local_property<Property> p, const subgraph<G>& g) {
1060	typedef typename property_map<
1061	subgraph<G>, local_property<Property>
1062	>::const_type Map;
1063	return Map(&g, p.value);
1064	}
1065
1066	template <typename G, typename Tag>
1067	inline typename graph_property<G, Tag>::type&
1068	get_property(subgraph<G>& g, Tag tag) {
1069	return get_property(g.m_graph, tag);
1070	}
1071
1072	template <typename G, typename Tag>
1073	inline const typename graph_property<G, Tag>::type&
1074	get_property(const subgraph<G>& g, Tag tag) {
1075	return get_property(g.m_graph, tag);
1076	}
1077
1078	//===========================================================================
1079	// Miscellaneous Functions
1080
1081	template <typename G>
1082	typename subgraph<G>::vertex_descriptor
1083	vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g)
1084	{ return vertex(n, g.m_graph); }
1085
1086	//===========================================================================
1087	// Mutability Traits
1088	// Just pull the mutability traits form the underlying graph. Note that this
1089	// will probably fail (badly) for labeled graphs.
1090	template <typename G>
1091	struct graph_mutability_traits< subgraph<G> > {
1092	typedef typename graph_mutability_traits<G>::category category;
1093	};
1094
1095	} // namespace boost
1096
1097	#endif // BOOST_SUBGRAPH_HPP

Download in other formats:

Original Format