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