]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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) | |
92f5a8d4 | 134 | : m_parent(x.m_parent), m_edge_counter(0) |
7c673cae FG |
135 | { |
136 | if(x.is_root()) | |
137 | { | |
92f5a8d4 TL |
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 | } | |
7c673cae FG |
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) | |
92f5a8d4 TL |
159 | { |
160 | m_children.push_back(new subgraph<Graph>(*i)); | |
161 | m_children.back()->m_parent = this; | |
162 | } | |
7c673cae FG |
163 | } |
164 | ||
165 | ||
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. | |
175 | static vertex_descriptor null_vertex() | |
176 | { return Traits::null_vertex(); } | |
177 | ||
178 | ||
179 | // Create a 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> | |
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 | |
198 | vertex_descriptor local_to_global(vertex_descriptor u_local) const | |
199 | { return is_root() ? u_local : m_global_vertex[u_local]; } | |
200 | ||
201 | 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 | ||
209 | 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 | ||
212 | 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> | |
218 | 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> | |
228 | 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. | |
237 | subgraph& parent() { return *m_parent; } | |
238 | const subgraph& parent() const { return *m_parent; } | |
239 | ||
240 | // Return true if this is the root subgraph | |
241 | bool is_root() const { return m_parent == 0; } | |
242 | ||
243 | // Return the root graph of the subgraph tree. | |
244 | subgraph& root() | |
245 | { return is_root() ? *this : m_parent->root(); } | |
246 | ||
247 | 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 | ||
267 | 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 | ||
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 | ||
277 | 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& | |
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& | |
288 | 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& | |
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& | |
299 | 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& | |
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& | |
312 | 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 | ||
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 | |
377 | add_vertex(typename subgraph<G>::vertex_descriptor u_global, | |
378 | subgraph<G>& g) | |
379 | { | |
92f5a8d4 TL |
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); | |
7c673cae | 407 | } |
92f5a8d4 TL |
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; | |
7c673cae FG |
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> | |
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 | |
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 | |
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 | |
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> | |
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 | |
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 | |
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> | |
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> | |
490 | vertices(const subgraph<G>& g) | |
491 | { return vertices(g.m_graph); } | |
492 | ||
493 | template <typename G> | |
494 | typename subgraph<G>::vertices_size_type | |
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> | |
504 | edges(const subgraph<G>& g) | |
505 | { return edges(g.m_graph); } | |
506 | ||
507 | template <typename G> | |
508 | typename subgraph<G>::edges_size_type | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | ||
804 | subgraph_global_property_map() | |
805 | { } | |
806 | ||
807 | subgraph_global_property_map(GraphPtr g, Tag tag) | |
808 | : m_g(g), m_tag(tag) | |
809 | { } | |
810 | ||
811 | 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 | ||
846 | subgraph_local_property_map() | |
847 | { } | |
848 | ||
849 | subgraph_local_property_map(GraphPtr g, Tag tag) | |
850 | : m_g(g), m_tag(tag) | |
851 | { } | |
852 | ||
853 | 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 | |
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 | |
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 | |
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> | |
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 | |
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 | |
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 | |
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 | |
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& | |
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& | |
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 | |
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 |