ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
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
31namespace boost {
32
33struct 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//@{
42template <typename T>
43struct local_property
44{
45 typedef T kind;
46 local_property(T x) : value(x) { }
47 T value;
48};
49
50template <typename T>
51inline local_property<T> local(T x)
52{ return local_property<T>(x); }
53
54template <typename T>
55struct global_property
56{
57 typedef T kind;
58 global_property(T x) : value(x) { }
59 T value;
60};
61
62template <typename T>
63inline 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
79template <typename Graph>
80class subgraph {
81 typedef graph_traits<Graph> Traits;
82 typedef std::list<subgraph<Graph>*> ChildrenList;
83public:
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
317private:
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
327public: // 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
351template <typename Graph>
352struct vertex_bundle_type<subgraph<Graph> >
353 : vertex_bundle_type<Graph>
354{ };
355
356template<typename Graph>
357struct edge_bundle_type<subgraph<Graph> >
358 : edge_bundle_type<Graph>
359{ };
360
361template<typename Graph>
362struct graph_bundle_type<subgraph<Graph> >
363 : graph_bundle_type<Graph>
364{ };
365
366//===========================================================================
367// Functions special to the Subgraph Class
368
369template <typename G>
370typename subgraph<G>::vertex_descriptor
371add_vertex(typename subgraph<G>::vertex_descriptor u_global,
372 subgraph<G>& g)
373{
374 BOOST_ASSERT(!g.is_root());
375 typename subgraph<G>::vertex_descriptor u_local, v_global;
376 typename subgraph<G>::edge_descriptor e_global;
377
378 u_local = add_vertex(g.m_graph);
379 g.m_global_vertex.push_back(u_global);
380 g.m_local_vertex[u_global] = u_local;
381
382 subgraph<G>& r = g.root();
383
384 // remember edge global and local maps
385 {
386 typename subgraph<G>::out_edge_iterator ei, ei_end;
387 for (boost::tie(ei, ei_end) = out_edges(u_global, r);
388 ei != ei_end; ++ei) {
389 e_global = *ei;
390 v_global = target(e_global, r);
391 if (g.find_vertex(v_global).second == true)
392 g.local_add_edge(u_local, g.global_to_local(v_global), e_global);
393 }
394 }
395 if (is_directed(g)) { // not necessary for undirected graph
396 typename subgraph<G>::vertex_iterator vi, vi_end;
397 typename subgraph<G>::out_edge_iterator ei, ei_end;
398 for(boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
399 v_global = *vi;
400 if (v_global == u_global)
401 continue; // don't insert self loops twice!
402 if (!g.find_vertex(v_global).second)
403 continue; // not a subgraph vertex => try next one
404 for(boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
405 e_global = *ei;
406 if(target(e_global, r) == u_global) {
407 g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
408 }
409 }
410 }
411 }
412
413 return u_local;
414}
415
416// NOTE: Descriptors are local unless otherwise noted.
417
418//===========================================================================
419// Functions required by the IncidenceGraph concept
420
421template <typename G>
422std::pair<typename graph_traits<G>::out_edge_iterator,
423 typename graph_traits<G>::out_edge_iterator>
424out_edges(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
425{ return out_edges(v, g.m_graph); }
426
427template <typename G>
428typename graph_traits<G>::degree_size_type
429out_degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
430{ return out_degree(v, g.m_graph); }
431
432template <typename G>
433typename graph_traits<G>::vertex_descriptor
434source(typename graph_traits<G>::edge_descriptor e, const subgraph<G>& g)
435{ return source(e, g.m_graph); }
436
437template <typename G>
438typename graph_traits<G>::vertex_descriptor
439target(typename graph_traits<G>::edge_descriptor e, const subgraph<G>& g)
440{ return target(e, g.m_graph); }
441
442//===========================================================================
443// Functions required by the BidirectionalGraph concept
444
445template <typename G>
446std::pair<typename graph_traits<G>::in_edge_iterator,
447 typename graph_traits<G>::in_edge_iterator>
448in_edges(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
449{ return in_edges(v, g.m_graph); }
450
451template <typename G>
452typename graph_traits<G>::degree_size_type
453in_degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
454{ return in_degree(v, g.m_graph); }
455
456template <typename G>
457typename graph_traits<G>::degree_size_type
458degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
459{ return degree(v, g.m_graph); }
460
461//===========================================================================
462// Functions required by the AdjacencyGraph concept
463
464template <typename G>
465std::pair<typename subgraph<G>::adjacency_iterator,
466 typename subgraph<G>::adjacency_iterator>
467adjacent_vertices(typename subgraph<G>::vertex_descriptor v, const subgraph<G>& g)
468{ return adjacent_vertices(v, g.m_graph); }
469
470//===========================================================================
471// Functions required by the VertexListGraph concept
472
473template <typename G>
474std::pair<typename subgraph<G>::vertex_iterator,
475 typename subgraph<G>::vertex_iterator>
476vertices(const subgraph<G>& g)
477{ return vertices(g.m_graph); }
478
479template <typename G>
480typename subgraph<G>::vertices_size_type
481num_vertices(const subgraph<G>& g)
482{ return num_vertices(g.m_graph); }
483
484//===========================================================================
485// Functions required by the EdgeListGraph concept
486
487template <typename G>
488std::pair<typename subgraph<G>::edge_iterator,
489 typename subgraph<G>::edge_iterator>
490edges(const subgraph<G>& g)
491{ return edges(g.m_graph); }
492
493template <typename G>
494typename subgraph<G>::edges_size_type
495num_edges(const subgraph<G>& g)
496{ return num_edges(g.m_graph); }
497
498//===========================================================================
499// Functions required by the AdjacencyMatrix concept
500
501template <typename G>
502std::pair<typename subgraph<G>::edge_descriptor, bool>
503edge(typename subgraph<G>::vertex_descriptor u,
504 typename subgraph<G>::vertex_descriptor v,
505 const subgraph<G>& g)
506{ return edge(u, v, g.m_graph); }
507
508//===========================================================================
509// Functions required by the MutableGraph concept
510
511namespace detail {
512
513 template <typename Vertex, typename Edge, typename Graph>
514 void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
515 subgraph<Graph>& g);
516
517 template <typename Vertex, typename Edge, typename Children, typename G>
518 void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
519 Children& c, subgraph<G>* orig)
520 {
521 for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
522 if ((*i)->find_vertex(u_global).second &&
523 (*i)->find_vertex(v_global).second)
524 {
525 add_edge_recur_down(u_global, v_global, e_global, **i, orig);
526 }
527 }
528 }
529
530 template <typename Vertex, typename Edge, typename Graph>
531 void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
532 subgraph<Graph>& g, subgraph<Graph>* orig)
533 {
534 if(&g != orig ) {
535 // add local edge only if u_global and v_global are in subgraph g
536 Vertex u_local, v_local;
537 bool u_in_subgraph, v_in_subgraph;
538 boost::tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
539 boost::tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
540 if(u_in_subgraph && v_in_subgraph) {
541 g.local_add_edge(u_local, v_local, e_global);
542 }
543 }
544 children_add_edge(u_global, v_global, e_global, g.m_children, orig);
545 }
546
547 template <typename Vertex, typename Graph>
548 std::pair<typename subgraph<Graph>::edge_descriptor, bool>
549 add_edge_recur_up(Vertex u_global, Vertex v_global,
550 const typename Graph::edge_property_type& ep,
551 subgraph<Graph>& g, subgraph<Graph>* orig)
552 {
553 if(g.is_root()) {
554 typename subgraph<Graph>::edge_descriptor e_global;
555 bool inserted;
556 boost::tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);
557 put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
558 g.m_global_edge.push_back(e_global);
559 children_add_edge(u_global, v_global, e_global, g.m_children, orig);
560 return std::make_pair(e_global, inserted);
561 } else {
562 return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
563 }
564 }
565
566} // namespace detail
567
568// Add an edge to the subgraph g, specified by the local vertex descriptors u
569// and v. In addition, the edge will be added to any (all) other subgraphs that
570// contain vertex descriptors u and v.
571
572template <typename G>
573std::pair<typename subgraph<G>::edge_descriptor, bool>
574add_edge(typename subgraph<G>::vertex_descriptor u,
575 typename subgraph<G>::vertex_descriptor v,
576 const typename G::edge_property_type& ep,
577 subgraph<G>& g)
578{
579 if (g.is_root()) {
580 // u and v are really global
581 return detail::add_edge_recur_up(u, v, ep, g, &g);
582 } else {
583 typename subgraph<G>::edge_descriptor e_local, e_global;
584 bool inserted;
585 boost::tie(e_global, inserted) =
586 detail::add_edge_recur_up(g.local_to_global(u),
587 g.local_to_global(v),
588 ep, g, &g);
589 e_local = g.local_add_edge(u, v, e_global);
590 return std::make_pair(e_local, inserted);
591 }
592}
593
594template <typename G>
595std::pair<typename subgraph<G>::edge_descriptor, bool>
596add_edge(typename subgraph<G>::vertex_descriptor u,
597 typename subgraph<G>::vertex_descriptor v,
598 subgraph<G>& g)
599{ return add_edge(u, v, typename G::edge_property_type(), g); }
600
601namespace detail {
602 //-------------------------------------------------------------------------
603 // implementation of remove_edge(u,v,g)
604 template <typename Vertex, typename Graph>
605 void remove_edge_recur_down(Vertex u_global, Vertex v_global,
606 subgraph<Graph>& g);
607
608 template <typename Vertex, typename Children>
609 void children_remove_edge(Vertex u_global, Vertex v_global,
610 Children& c)
611 {
612 for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
613 if((*i)->find_vertex(u_global).second &&
614 (*i)->find_vertex(v_global).second)
615 {
616 remove_edge_recur_down(u_global, v_global, **i);
617 }
618 }
619 }
620
621 template <typename Vertex, typename Graph>
622 void remove_edge_recur_down(Vertex u_global, Vertex v_global,
623 subgraph<Graph>& g)
624 {
625 Vertex u_local, v_local;
626 u_local = g.m_local_vertex[u_global];
627 v_local = g.m_local_vertex[v_global];
628 remove_edge(u_local, v_local, g.m_graph);
629 children_remove_edge(u_global, v_global, g.m_children);
630 }
631
632 template <typename Vertex, typename Graph>
633 void remove_edge_recur_up(Vertex u_global, Vertex v_global,
634 subgraph<Graph>& g)
635 {
636 if(g.is_root()) {
637 remove_edge(u_global, v_global, g.m_graph);
638 children_remove_edge(u_global, v_global, g.m_children);
639 } else {
640 remove_edge_recur_up(u_global, v_global, *g.m_parent);
641 }
642 }
643
644 //-------------------------------------------------------------------------
645 // implementation of remove_edge(e,g)
646
647 template <typename G, typename Edge, typename Children>
648 void children_remove_edge(Edge e_global, Children& c)
649 {
650 for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
651 std::pair<typename subgraph<G>::edge_descriptor, bool> found =
652 (*i)->find_edge(e_global);
653 if (!found.second) {
654 continue;
655 }
656 children_remove_edge<G>(e_global, (*i)->m_children);
657 remove_edge(found.first, (*i)->m_graph);
658 }
659 }
660
661} // namespace detail
662
663template <typename G>
664void
665remove_edge(typename subgraph<G>::vertex_descriptor u,
666 typename subgraph<G>::vertex_descriptor v,
667 subgraph<G>& g)
668{
669 if(g.is_root()) {
670 detail::remove_edge_recur_up(u, v, g);
671 } else {
672 detail::remove_edge_recur_up(g.local_to_global(u),
673 g.local_to_global(v), g);
674 }
675}
676
677template <typename G>
678void
679remove_edge(typename subgraph<G>::edge_descriptor e, subgraph<G>& g)
680{
681 typename subgraph<G>::edge_descriptor e_global = g.local_to_global(e);
682#ifndef NDEBUG
683 std::pair<typename subgraph<G>::edge_descriptor, bool> fe = g.find_edge(e_global);
684 BOOST_ASSERT(fe.second && fe.first == e);
685#endif //NDEBUG
686 subgraph<G> &root = g.root(); // chase to root
687 detail::children_remove_edge<G>(e_global, root.m_children);
688 remove_edge(e_global, root.m_graph); // kick edge from root
689}
690
691// This is slow, but there may not be a good way to do it safely otherwise
692template <typename Predicate, typename G>
693void
694remove_edge_if(Predicate p, subgraph<G>& g) {
695 while (true) {
696 bool any_removed = false;
697 typedef typename subgraph<G>::edge_iterator ei_type;
698 for (std::pair<ei_type, ei_type> ep = edges(g);
699 ep.first != ep.second; ++ep.first) {
700 if (p(*ep.first)) {
701 any_removed = true;
702 remove_edge(*ep.first, g);
703 break; /* Since iterators may be invalidated */
704 }
705 }
706 if (!any_removed) break;
707 }
708}
709
710template <typename G>
711void
712clear_vertex(typename subgraph<G>::vertex_descriptor v, subgraph<G>& g) {
713 while (true) {
714 typedef typename subgraph<G>::out_edge_iterator oei_type;
715 std::pair<oei_type, oei_type> p = out_edges(v, g);
716 if (p.first == p.second) break;
717 remove_edge(*p.first, g);
718 }
719}
720
721namespace detail {
722 template <typename G>
723 typename subgraph<G>::vertex_descriptor
724 add_vertex_recur_up(subgraph<G>& g)
725 {
726 typename subgraph<G>::vertex_descriptor u_local, u_global;
727 if (g.is_root()) {
728 u_global = add_vertex(g.m_graph);
729 g.m_global_vertex.push_back(u_global);
730 } else {
731 u_global = add_vertex_recur_up(*g.m_parent);
732 u_local = add_vertex(g.m_graph);
733 g.m_global_vertex.push_back(u_global);
734 g.m_local_vertex[u_global] = u_local;
735 }
736 return u_global;
737 }
738} // namespace detail
739
740template <typename G>
741typename subgraph<G>::vertex_descriptor
742add_vertex(subgraph<G>& g)
743{
744 typename subgraph<G>::vertex_descriptor u_local, u_global;
745 if(g.is_root()) {
746 u_global = add_vertex(g.m_graph);
747 g.m_global_vertex.push_back(u_global);
748 u_local = u_global;
749 } else {
750 u_global = detail::add_vertex_recur_up(g.parent());
751 u_local = add_vertex(g.m_graph);
752 g.m_global_vertex.push_back(u_global);
753 g.m_local_vertex[u_global] = u_local;
754 }
755 return u_local;
756}
757
758
759#if 0
760// TODO: Under Construction
761template <typename G>
762void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
763{ BOOST_ASSERT(false); }
764#endif
765
766//===========================================================================
767// Functions required by the PropertyGraph concept
768
769/**
770 * The global property map returns the global properties associated with local
771 * descriptors.
772 */
773template <typename GraphPtr, typename PropertyMap, typename Tag>
774class subgraph_global_property_map
775 : public put_get_helper<
776 typename property_traits<PropertyMap>::reference,
777 subgraph_global_property_map<GraphPtr, PropertyMap, Tag>
778 >
779{
780 typedef property_traits<PropertyMap> Traits;
781public:
782 typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
783 readable_property_map_tag,
784 typename Traits::category>::type
785 category;
786 typedef typename Traits::value_type value_type;
787 typedef typename Traits::key_type key_type;
788 typedef typename Traits::reference reference;
789
790 subgraph_global_property_map()
791 { }
792
793 subgraph_global_property_map(GraphPtr g, Tag tag)
794 : m_g(g), m_tag(tag)
795 { }
796
797 reference operator[](key_type e) const {
798 PropertyMap pmap = get(m_tag, m_g->root().m_graph);
799 return m_g->is_root()
800 ? pmap[e]
801 : pmap[m_g->local_to_global(e)];
802 }
803
804 GraphPtr m_g;
805 Tag m_tag;
806};
807
808/**
809 * The local property map returns the local property associated with the local
810 * descriptors.
811 */
812template <typename GraphPtr, typename PropertyMap, typename Tag>
813class subgraph_local_property_map
814 : public put_get_helper<
815 typename property_traits<PropertyMap>::reference,
816 subgraph_local_property_map<GraphPtr, PropertyMap, Tag>
817 >
818{
819 typedef property_traits<PropertyMap> Traits;
820public:
821 typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
822 readable_property_map_tag,
823 typename Traits::category>::type
824 category;
825 typedef typename Traits::value_type value_type;
826 typedef typename Traits::key_type key_type;
827 typedef typename Traits::reference reference;
828
829 typedef Tag tag;
830 typedef PropertyMap pmap;
831
832 subgraph_local_property_map()
833 { }
834
835 subgraph_local_property_map(GraphPtr g, Tag tag)
836 : m_g(g), m_tag(tag)
837 { }
838
839 reference operator[](key_type e) const {
840 // Get property map on the underlying graph.
841 PropertyMap pmap = get(m_tag, m_g->m_graph);
842 return pmap[e];
843 }
844
845 GraphPtr m_g;
846 Tag m_tag;
847};
848
849namespace detail {
850 // Extract the actual tags from local or global property maps so we don't
851 // try to find non-properties.
852 template <typename P> struct extract_lg_tag { typedef P type; };
853 template <typename P> struct extract_lg_tag< local_property<P> > {
854 typedef P type;
855 };
856 template <typename P> struct extract_lg_tag< global_property<P> > {
857 typedef P type;
858 };
859
860 // NOTE: Mysterious Property template parameter unused in both metafunction
861 // classes.
862 struct subgraph_global_pmap {
863 template <class Tag, class SubGraph, class Property>
864 struct bind_ {
865 typedef typename SubGraph::graph_type Graph;
866 typedef SubGraph* SubGraphPtr;
867 typedef const SubGraph* const_SubGraphPtr;
868 typedef typename extract_lg_tag<Tag>::type TagType;
869 typedef typename property_map<Graph, TagType>::type PMap;
870 typedef typename property_map<Graph, TagType>::const_type const_PMap;
871 public:
872 typedef subgraph_global_property_map<SubGraphPtr, PMap, TagType> type;
873 typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, TagType>
874 const_type;
875 };
876 };
877
878 struct subgraph_local_pmap {
879 template <class Tag, class SubGraph, class Property>
880 struct bind_ {
881 typedef typename SubGraph::graph_type Graph;
882 typedef SubGraph* SubGraphPtr;
883 typedef const SubGraph* const_SubGraphPtr;
884 typedef typename extract_lg_tag<Tag>::type TagType;
885 typedef typename property_map<Graph, TagType>::type PMap;
886 typedef typename property_map<Graph, TagType>::const_type const_PMap;
887 public:
888 typedef subgraph_local_property_map<SubGraphPtr, PMap, TagType> type;
889 typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, TagType>
890 const_type;
891 };
892 };
893
894 // These metafunctions select the corresponding metafunctions above, and
895 // are used by the choose_pmap metafunction below to specialize the choice
896 // of local/global property map. By default, we defer to the global
897 // property.
898 template <class Tag>
899 struct subgraph_choose_pmap_helper {
900 typedef subgraph_global_pmap type;
901 };
902 template <class Tag>
903 struct subgraph_choose_pmap_helper< local_property<Tag> > {
904 typedef subgraph_local_pmap type;
905 };
906 template <class Tag>
907 struct subgraph_choose_pmap_helper< global_property<Tag> > {
908 typedef subgraph_global_pmap type;
909 };
910
911 // As above, unless we're requesting vertex_index_t. Then it's always a
912 // local property map. This enables the correct translation of descriptors
913 // between local and global layers.
914 template <>
915 struct subgraph_choose_pmap_helper<vertex_index_t> {
916 typedef subgraph_local_pmap type;
917 };
918 template <>
919 struct subgraph_choose_pmap_helper< local_property<vertex_index_t> > {
920 typedef subgraph_local_pmap type;
921 };
922 template <>
923 struct subgraph_choose_pmap_helper< global_property<vertex_index_t> > {
924 typedef subgraph_local_pmap type;
925 };
926
927 // Determine the kind of property. If SameType<Tag, vertex_index_t>, then
928 // the property lookup is always local. Otherwise, the lookup is global.
929 // NOTE: Property parameter is basically unused.
930 template <class Tag, class Graph, class Property>
931 struct subgraph_choose_pmap {
932 typedef typename subgraph_choose_pmap_helper<Tag>::type Helper;
933 typedef typename Helper::template bind_<Tag, Graph, Property> Bind;
934 typedef typename Bind::type type;
935 typedef typename Bind::const_type const_type;
936 };
937
938 // Used by the vertex/edge property selectors to determine the kind(s) of
939 // property maps used by the property_map type generator.
940 struct subgraph_property_generator {
941 template <class SubGraph, class Property, class Tag>
942 struct bind_ {
943 typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice;
944 typedef typename Choice::type type;
945 typedef typename Choice::const_type const_type;
946 };
947 };
948
949 } // namespace detail
950
951template <>
952struct vertex_property_selector<subgraph_tag> {
953 typedef detail::subgraph_property_generator type;
954};
955
956template <>
957struct edge_property_selector<subgraph_tag> {
958 typedef detail::subgraph_property_generator type;
959};
960
961// ==================================================
962// get(p, g), get(p, g, k), and put(p, g, k, v)
963// ==================================================
964template <typename G, typename Property>
965typename property_map<subgraph<G>, Property>::type
966get(Property p, subgraph<G>& g) {
967 typedef typename property_map< subgraph<G>, Property>::type PMap;
968 return PMap(&g, p);
969}
970
971template <typename G, typename Property>
972typename property_map<subgraph<G>, Property>::const_type
973get(Property p, const subgraph<G>& g) {
974 typedef typename property_map< subgraph<G>, Property>::const_type PMap;
975 return PMap(&g, p);
976}
977
978template <typename G, typename Property, typename Key>
979typename property_traits<
980 typename property_map<subgraph<G>, Property>::const_type
981>::value_type
982get(Property p, const subgraph<G>& g, const Key& k) {
983 typedef typename property_map< subgraph<G>, Property>::const_type PMap;
984 PMap pmap(&g, p);
985 return pmap[k];
986}
987
988template <typename G, typename Property, typename Key, typename Value>
989void put(Property p, subgraph<G>& g, const Key& k, const Value& val) {
990 typedef typename property_map< subgraph<G>, Property>::type PMap;
991 PMap pmap(&g, p);
992 pmap[k] = val;
993}
994
995// ==================================================
996// get(global(p), g)
997// NOTE: get(global(p), g, k) and put(global(p), g, k, v) not supported
998// ==================================================
999template <typename G, typename Property>
1000typename property_map<subgraph<G>, global_property<Property> >::type
1001get(global_property<Property> p, subgraph<G>& g) {
1002 typedef typename property_map<
1003 subgraph<G>, global_property<Property>
1004 >::type Map;
1005 return Map(&g, p.value);
1006}
1007
1008template <typename G, typename Property>
1009typename property_map<subgraph<G>, global_property<Property> >::const_type
1010get(global_property<Property> p, const subgraph<G>& g) {
1011 typedef typename property_map<
1012 subgraph<G>, global_property<Property>
1013 >::const_type Map;
1014 return Map(&g, p.value);
1015}
1016
1017// ==================================================
1018// get(local(p), g)
1019// NOTE: get(local(p), g, k) and put(local(p), g, k, v) not supported
1020// ==================================================
1021template <typename G, typename Property>
1022typename property_map<subgraph<G>, local_property<Property> >::type
1023get(local_property<Property> p, subgraph<G>& g) {
1024 typedef typename property_map<
1025 subgraph<G>, local_property<Property>
1026 >::type Map;
1027 return Map(&g, p.value);
1028}
1029
1030template <typename G, typename Property>
1031typename property_map<subgraph<G>, local_property<Property> >::const_type
1032get(local_property<Property> p, const subgraph<G>& g) {
1033 typedef typename property_map<
1034 subgraph<G>, local_property<Property>
1035 >::const_type Map;
1036 return Map(&g, p.value);
1037}
1038
1039template <typename G, typename Tag>
1040inline typename graph_property<G, Tag>::type&
1041get_property(subgraph<G>& g, Tag tag) {
1042 return get_property(g.m_graph, tag);
1043}
1044
1045template <typename G, typename Tag>
1046inline const typename graph_property<G, Tag>::type&
1047get_property(const subgraph<G>& g, Tag tag) {
1048 return get_property(g.m_graph, tag);
1049}
1050
1051//===========================================================================
1052// Miscellaneous Functions
1053
1054template <typename G>
1055typename subgraph<G>::vertex_descriptor
1056vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g)
1057{ return vertex(n, g.m_graph); }
1058
1059//===========================================================================
1060// Mutability Traits
1061// Just pull the mutability traits form the underlying graph. Note that this
1062// will probably fail (badly) for labeled graphs.
1063template <typename G>
1064struct graph_mutability_traits< subgraph<G> > {
1065 typedef typename graph_mutability_traits<G>::category category;
1066};
1067
1068} // namespace boost
1069
1070#endif // BOOST_SUBGRAPH_HPP