]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2012, Michele Caini. |
2 | // Distributed under the Boost Software License, Version 1.0. | |
3 | // (See accompanying file LICENSE_1_0.txt or copy at | |
4 | // http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | // Two Graphs Common Spanning Trees Algorithm | |
7 | // Based on academic article of Mint, Read and Tarjan | |
8 | // Efficient Algorithm for Common Spanning Tree Problem | |
9 | // Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347 | |
10 | ||
11 | ||
12 | #ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP | |
13 | #define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP | |
14 | ||
15 | ||
16 | #include <boost/config.hpp> | |
17 | ||
18 | #include <boost/bimap.hpp> | |
19 | #include <boost/type_traits.hpp> | |
20 | #include <boost/concept/requires.hpp> | |
21 | #include <boost/graph/graph_traits.hpp> | |
22 | #include <boost/graph/undirected_dfs.hpp> | |
23 | #include <boost/graph/connected_components.hpp> | |
24 | #include <boost/graph/filtered_graph.hpp> | |
25 | #include <vector> | |
26 | #include <stack> | |
27 | #include <map> | |
28 | ||
29 | ||
30 | namespace boost | |
31 | { | |
32 | ||
33 | ||
34 | namespace detail { | |
35 | ||
36 | ||
37 | template | |
38 | < | |
39 | typename TreeMap, | |
40 | typename PredMap, | |
41 | typename DistMap, | |
42 | typename LowMap, | |
43 | typename Buffer | |
44 | > | |
45 | struct bridges_visitor: public default_dfs_visitor | |
46 | { | |
47 | bridges_visitor( | |
48 | TreeMap tree, | |
49 | PredMap pred, | |
50 | DistMap dist, | |
51 | LowMap low, | |
52 | Buffer& buffer | |
53 | ): mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer) | |
54 | { mNum = -1; } | |
55 | ||
56 | template <typename Vertex, typename Graph> | |
57 | void initialize_vertex(const Vertex& u, const Graph& g) | |
58 | { | |
59 | put(mPred, u, u); | |
60 | put(mDist, u, -1); | |
61 | } | |
62 | ||
63 | template <typename Vertex, typename Graph> | |
64 | void discover_vertex(const Vertex& u, const Graph& g) | |
65 | { | |
66 | put(mDist, u, ++mNum); | |
67 | put(mLow, u, get(mDist, u)); | |
68 | } | |
69 | ||
70 | template <typename Edge, typename Graph> | |
71 | void tree_edge(const Edge& e, const Graph& g) | |
72 | { | |
73 | put(mPred, target(e, g), source(e, g)); | |
74 | put(mTree, target(e, g), e); | |
75 | } | |
76 | ||
77 | template <typename Edge, typename Graph> | |
78 | void back_edge(const Edge& e, const Graph& g) | |
79 | { | |
80 | put(mLow, source(e, g), | |
81 | (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g)))); | |
82 | } | |
83 | ||
84 | template <typename Vertex, typename Graph> | |
85 | void finish_vertex(const Vertex& u, const Graph& g) | |
86 | { | |
87 | Vertex parent = get(mPred, u); | |
88 | if(get(mLow, u) > get(mDist, parent)) | |
89 | mBuffer.push(get(mTree, u)); | |
90 | put(mLow, parent, | |
91 | (std::min)(get(mLow, parent), get(mLow, u))); | |
92 | } | |
93 | ||
94 | TreeMap mTree; | |
95 | PredMap mPred; | |
96 | DistMap mDist; | |
97 | LowMap mLow; | |
98 | Buffer& mBuffer; | |
99 | int mNum; | |
100 | }; | |
101 | ||
102 | ||
103 | template <typename Buffer> | |
104 | struct cycle_finder: public base_visitor< cycle_finder<Buffer> > | |
105 | { | |
106 | typedef on_back_edge event_filter; | |
107 | cycle_finder(): mBuffer(0) { } | |
108 | cycle_finder(Buffer* buffer) | |
109 | : mBuffer(buffer) { } | |
110 | template <typename Edge, typename Graph> | |
111 | void operator()(const Edge& e, const Graph& g) | |
112 | { | |
113 | if(mBuffer) | |
114 | mBuffer->push(e); | |
115 | } | |
116 | Buffer* mBuffer; | |
117 | }; | |
118 | ||
119 | ||
120 | template <typename DeletedMap> | |
121 | struct deleted_edge_status | |
122 | { | |
123 | deleted_edge_status() { } | |
124 | deleted_edge_status(DeletedMap map): mMap(map) { } | |
125 | template <typename Edge> | |
126 | bool operator()(const Edge& e) const | |
127 | { return (!get(mMap, e)); } | |
128 | DeletedMap mMap; | |
129 | }; | |
130 | ||
131 | ||
132 | template <typename InLMap> | |
133 | struct inL_edge_status | |
134 | { | |
135 | inL_edge_status() { } | |
136 | inL_edge_status(InLMap map): mMap(map) { } | |
137 | template <typename Edge> | |
138 | bool operator()(const Edge& e) const | |
139 | { return get(mMap, e); } | |
140 | InLMap mMap; | |
141 | }; | |
142 | ||
143 | ||
144 | template < | |
145 | typename Graph, | |
146 | typename Func, | |
147 | typename Seq, | |
148 | typename Map | |
149 | > | |
150 | void rec_two_graphs_common_spanning_trees | |
151 | ( | |
152 | const Graph& iG, | |
153 | bimap< | |
154 | bimaps::set_of<int>, | |
155 | bimaps::set_of< typename graph_traits<Graph>::edge_descriptor > | |
156 | > iG_bimap, | |
157 | Map aiG_inL, | |
158 | Map diG, | |
159 | const Graph& vG, | |
160 | bimap< | |
161 | bimaps::set_of<int>, | |
162 | bimaps::set_of< typename graph_traits<Graph>::edge_descriptor > | |
163 | > vG_bimap, | |
164 | Map avG_inL, | |
165 | Map dvG, | |
166 | Func func, | |
167 | Seq inL | |
168 | ) | |
169 | { | |
170 | typedef graph_traits<Graph> GraphTraits; | |
171 | ||
172 | typedef typename GraphTraits::vertex_descriptor vertex_descriptor; | |
173 | typedef typename GraphTraits::edge_descriptor edge_descriptor; | |
174 | ||
175 | typedef typename Seq::size_type seq_size_type; | |
176 | ||
177 | int edges = num_vertices(iG) - 1; | |
178 | // | |
179 | // [ Michele Caini ] | |
180 | // | |
181 | // Using the condition (edges != 0) leads to the accidental submission of | |
182 | // sub-graphs ((V-1+1)-fake-tree, named here fat-tree). | |
183 | // Remove this condition is a workaround for the problem of fat-trees. | |
184 | // Please do not add that condition, even if it improves performance. | |
185 | // | |
186 | // Here is proposed the previous guard (that was wrong): | |
187 | // for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i) | |
188 | // | |
189 | { | |
190 | for(seq_size_type i = 0; i < inL.size(); ++i) | |
191 | if(inL[i]) | |
192 | --edges; | |
193 | ||
194 | if(edges < 0) | |
195 | return; | |
196 | } | |
197 | ||
198 | bool is_tree = (edges == 0); | |
199 | if(is_tree) { | |
200 | func(inL); | |
201 | } else { | |
202 | std::map<vertex_descriptor, default_color_type> vertex_color; | |
203 | std::map<edge_descriptor, default_color_type> edge_color; | |
204 | ||
205 | std::stack<edge_descriptor> iG_buf, vG_buf; | |
206 | bool found = false; | |
207 | ||
208 | seq_size_type m; | |
209 | for(seq_size_type j = 0; j < inL.size() && !found; ++j) { | |
210 | if(!inL[j] | |
211 | && !get(diG, iG_bimap.left.at(j)) | |
212 | && !get(dvG, vG_bimap.left.at(j))) | |
213 | { | |
214 | put(aiG_inL, iG_bimap.left.at(j), true); | |
215 | put(avG_inL, vG_bimap.left.at(j), true); | |
216 | ||
217 | undirected_dfs( | |
218 | make_filtered_graph(iG, | |
219 | detail::inL_edge_status< associative_property_map< | |
220 | std::map<edge_descriptor, bool> > >(aiG_inL)), | |
221 | make_dfs_visitor( | |
222 | detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), | |
223 | associative_property_map< | |
224 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
225 | associative_property_map< | |
226 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
227 | ); | |
228 | undirected_dfs( | |
229 | make_filtered_graph(vG, | |
230 | detail::inL_edge_status< associative_property_map< | |
231 | std::map<edge_descriptor, bool> > >(avG_inL)), | |
232 | make_dfs_visitor( | |
233 | detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), | |
234 | associative_property_map< | |
235 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
236 | associative_property_map< | |
237 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
238 | ); | |
239 | ||
240 | if(iG_buf.empty() && vG_buf.empty()) { | |
241 | inL[j] = true; | |
242 | found = true; | |
243 | m = j; | |
244 | } else { | |
245 | while(!iG_buf.empty()) iG_buf.pop(); | |
246 | while(!vG_buf.empty()) vG_buf.pop(); | |
247 | put(aiG_inL, iG_bimap.left.at(j), false); | |
248 | put(avG_inL, vG_bimap.left.at(j), false); | |
249 | } | |
250 | } | |
251 | } | |
252 | ||
253 | if(found) { | |
254 | ||
255 | std::stack<edge_descriptor> iG_buf_copy, vG_buf_copy; | |
256 | for(seq_size_type j = 0; j < inL.size(); ++j) { | |
257 | if(!inL[j] | |
258 | && !get(diG, iG_bimap.left.at(j)) | |
259 | && !get(dvG, vG_bimap.left.at(j))) | |
260 | { | |
261 | ||
262 | put(aiG_inL, iG_bimap.left.at(j), true); | |
263 | put(avG_inL, vG_bimap.left.at(j), true); | |
264 | ||
265 | undirected_dfs( | |
266 | make_filtered_graph(iG, | |
267 | detail::inL_edge_status< associative_property_map< | |
268 | std::map<edge_descriptor, bool> > >(aiG_inL)), | |
269 | make_dfs_visitor( | |
270 | detail::cycle_finder< | |
271 | std::stack<edge_descriptor> > (&iG_buf)), | |
272 | associative_property_map< std::map< | |
273 | vertex_descriptor, default_color_type> >(vertex_color), | |
274 | associative_property_map< | |
275 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
276 | ); | |
277 | undirected_dfs( | |
278 | make_filtered_graph(vG, | |
279 | detail::inL_edge_status< associative_property_map< | |
280 | std::map<edge_descriptor, bool> > >(avG_inL)), | |
281 | make_dfs_visitor( | |
282 | detail::cycle_finder< | |
283 | std::stack<edge_descriptor> > (&vG_buf)), | |
284 | associative_property_map< std::map< | |
285 | vertex_descriptor, default_color_type> >(vertex_color), | |
286 | associative_property_map< | |
287 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
288 | ); | |
289 | ||
290 | if(!iG_buf.empty() || !vG_buf.empty()) { | |
291 | while(!iG_buf.empty()) iG_buf.pop(); | |
292 | while(!vG_buf.empty()) vG_buf.pop(); | |
293 | put(diG, iG_bimap.left.at(j), true); | |
294 | put(dvG, vG_bimap.left.at(j), true); | |
295 | iG_buf_copy.push(iG_bimap.left.at(j)); | |
296 | vG_buf_copy.push(vG_bimap.left.at(j)); | |
297 | } | |
298 | ||
299 | put(aiG_inL, iG_bimap.left.at(j), false); | |
300 | put(avG_inL, vG_bimap.left.at(j), false); | |
301 | } | |
302 | } | |
303 | ||
304 | // REC | |
305 | detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, Map> | |
306 | (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); | |
307 | ||
308 | while(!iG_buf_copy.empty()) { | |
309 | put(diG, iG_buf_copy.top(), false); | |
310 | put(dvG, vG_bimap.left.at( | |
311 | iG_bimap.right.at(iG_buf_copy.top())), false); | |
312 | iG_buf_copy.pop(); | |
313 | } | |
314 | while(!vG_buf_copy.empty()) { | |
315 | put(dvG, vG_buf_copy.top(), false); | |
316 | put(diG, iG_bimap.left.at( | |
317 | vG_bimap.right.at(vG_buf_copy.top())), false); | |
318 | vG_buf_copy.pop(); | |
319 | } | |
320 | ||
321 | inL[m] = false; | |
322 | put(aiG_inL, iG_bimap.left.at(m), false); | |
323 | put(avG_inL, vG_bimap.left.at(m), false); | |
324 | ||
325 | put(diG, iG_bimap.left.at(m), true); | |
326 | put(dvG, vG_bimap.left.at(m), true); | |
327 | ||
328 | std::map<vertex_descriptor, edge_descriptor> tree_map; | |
329 | std::map<vertex_descriptor, vertex_descriptor> pred_map; | |
330 | std::map<vertex_descriptor, int> dist_map, low_map; | |
331 | ||
332 | detail::bridges_visitor< | |
333 | associative_property_map< | |
334 | std::map<vertex_descriptor, edge_descriptor> | |
335 | >, | |
336 | associative_property_map< | |
337 | std::map<vertex_descriptor, vertex_descriptor> | |
338 | >, | |
339 | associative_property_map< std::map<vertex_descriptor, int> >, | |
340 | associative_property_map< std::map<vertex_descriptor, int> >, | |
341 | std::stack<edge_descriptor> | |
342 | > | |
343 | iG_vis( | |
344 | associative_property_map< | |
345 | std::map< vertex_descriptor, edge_descriptor> >(tree_map), | |
346 | associative_property_map< | |
347 | std::map< vertex_descriptor, vertex_descriptor> >(pred_map), | |
348 | associative_property_map< | |
349 | std::map< vertex_descriptor, int> >(dist_map), | |
350 | associative_property_map< | |
351 | std::map< vertex_descriptor, int> >(low_map), | |
352 | iG_buf | |
353 | ), | |
354 | vG_vis( | |
355 | associative_property_map< | |
356 | std::map< vertex_descriptor, edge_descriptor> >(tree_map), | |
357 | associative_property_map< | |
358 | std::map< vertex_descriptor, vertex_descriptor> >(pred_map), | |
359 | associative_property_map< | |
360 | std::map< vertex_descriptor, int> >(dist_map), | |
361 | associative_property_map< | |
362 | std::map< vertex_descriptor, int> >(low_map), | |
363 | vG_buf | |
364 | ); | |
365 | ||
366 | undirected_dfs(make_filtered_graph(iG, | |
367 | detail::deleted_edge_status< associative_property_map< | |
368 | std::map<edge_descriptor, bool> > >(diG)), | |
369 | iG_vis, | |
370 | associative_property_map< | |
371 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
372 | associative_property_map< | |
373 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
374 | ); | |
375 | undirected_dfs(make_filtered_graph(vG, | |
376 | detail::deleted_edge_status< associative_property_map< | |
377 | std::map<edge_descriptor, bool> > >(dvG)), | |
378 | vG_vis, | |
379 | associative_property_map< | |
380 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
381 | associative_property_map< | |
382 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
383 | ); | |
384 | ||
385 | found = false; | |
386 | std::stack<edge_descriptor> iG_buf_tmp, vG_buf_tmp; | |
387 | while(!iG_buf.empty() && !found) { | |
388 | if(!inL[iG_bimap.right.at(iG_buf.top())]) { | |
389 | put(aiG_inL, iG_buf.top(), true); | |
390 | put(avG_inL, vG_bimap.left.at( | |
391 | iG_bimap.right.at(iG_buf.top())), true); | |
392 | ||
393 | undirected_dfs( | |
394 | make_filtered_graph(iG, | |
395 | detail::inL_edge_status< associative_property_map< | |
396 | std::map<edge_descriptor, bool> > >(aiG_inL)), | |
397 | make_dfs_visitor( | |
398 | detail::cycle_finder< | |
399 | std::stack<edge_descriptor> > (&iG_buf_tmp)), | |
400 | associative_property_map< | |
401 | std::map< | |
402 | vertex_descriptor, default_color_type> >(vertex_color), | |
403 | associative_property_map< | |
404 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
405 | ); | |
406 | undirected_dfs( | |
407 | make_filtered_graph(vG, | |
408 | detail::inL_edge_status< associative_property_map< | |
409 | std::map<edge_descriptor, bool> > >(avG_inL)), | |
410 | make_dfs_visitor( | |
411 | detail::cycle_finder< | |
412 | std::stack<edge_descriptor> > (&vG_buf_tmp)), | |
413 | associative_property_map< | |
414 | std::map< | |
415 | vertex_descriptor, default_color_type> >(vertex_color), | |
416 | associative_property_map< | |
417 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
418 | ); | |
419 | ||
420 | if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { | |
421 | found = true; | |
422 | } else { | |
423 | while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); | |
424 | while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); | |
425 | iG_buf_copy.push(iG_buf.top()); | |
426 | } | |
427 | ||
428 | put(aiG_inL, iG_buf.top(), false); | |
429 | put(avG_inL, vG_bimap.left.at( | |
430 | iG_bimap.right.at(iG_buf.top())), false); | |
431 | } | |
432 | iG_buf.pop(); | |
433 | } | |
434 | while(!vG_buf.empty() && !found) { | |
435 | if(!inL[vG_bimap.right.at(vG_buf.top())]) { | |
436 | put(avG_inL, vG_buf.top(), true); | |
437 | put(aiG_inL, iG_bimap.left.at( | |
438 | vG_bimap.right.at(vG_buf.top())), true); | |
439 | ||
440 | undirected_dfs( | |
441 | make_filtered_graph(iG, | |
442 | detail::inL_edge_status< associative_property_map< | |
443 | std::map<edge_descriptor, bool> > >(aiG_inL)), | |
444 | make_dfs_visitor( | |
445 | detail::cycle_finder< | |
446 | std::stack<edge_descriptor> > (&iG_buf_tmp)), | |
447 | associative_property_map< | |
448 | std::map< | |
449 | vertex_descriptor, default_color_type> >(vertex_color), | |
450 | associative_property_map< | |
451 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
452 | ); | |
453 | undirected_dfs( | |
454 | make_filtered_graph(vG, | |
455 | detail::inL_edge_status< associative_property_map< | |
456 | std::map<edge_descriptor, bool> > >(avG_inL)), | |
457 | make_dfs_visitor( | |
458 | detail::cycle_finder< | |
459 | std::stack<edge_descriptor> > (&vG_buf_tmp)), | |
460 | associative_property_map< | |
461 | std::map< | |
462 | vertex_descriptor, default_color_type> >(vertex_color), | |
463 | associative_property_map< | |
464 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
465 | ); | |
466 | ||
467 | if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { | |
468 | found = true; | |
469 | } else { | |
470 | while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); | |
471 | while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); | |
472 | vG_buf_copy.push(vG_buf.top()); | |
473 | } | |
474 | ||
475 | put(avG_inL, vG_buf.top(), false); | |
476 | put(aiG_inL, iG_bimap.left.at( | |
477 | vG_bimap.right.at(vG_buf.top())), false); | |
478 | } | |
479 | vG_buf.pop(); | |
480 | } | |
481 | ||
482 | if(!found) { | |
483 | ||
484 | while(!iG_buf_copy.empty()) { | |
485 | inL[iG_bimap.right.at(iG_buf_copy.top())] = true; | |
486 | put(aiG_inL, iG_buf_copy.top(), true); | |
487 | put(avG_inL, vG_bimap.left.at( | |
488 | iG_bimap.right.at(iG_buf_copy.top())), true); | |
489 | iG_buf.push(iG_buf_copy.top()); | |
490 | iG_buf_copy.pop(); | |
491 | } | |
492 | while(!vG_buf_copy.empty()) { | |
493 | inL[vG_bimap.right.at(vG_buf_copy.top())] = true; | |
494 | put(avG_inL, vG_buf_copy.top(), true); | |
495 | put(aiG_inL, iG_bimap.left.at( | |
496 | vG_bimap.right.at(vG_buf_copy.top())), true); | |
497 | vG_buf.push(vG_buf_copy.top()); | |
498 | vG_buf_copy.pop(); | |
499 | } | |
500 | ||
501 | // REC | |
502 | detail::rec_two_graphs_common_spanning_trees< | |
503 | Graph, Func, Seq, Map> | |
504 | (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); | |
505 | ||
506 | while(!iG_buf.empty()) { | |
507 | inL[iG_bimap.right.at(iG_buf.top())] = false; | |
508 | put(aiG_inL, iG_buf.top(), false); | |
509 | put(avG_inL, vG_bimap.left.at( | |
510 | iG_bimap.right.at(iG_buf.top())), false); | |
511 | iG_buf.pop(); | |
512 | } | |
513 | while(!vG_buf.empty()) { | |
514 | inL[vG_bimap.right.at(vG_buf.top())] = false; | |
515 | put(avG_inL, vG_buf.top(), false); | |
516 | put(aiG_inL, iG_bimap.left.at( | |
517 | vG_bimap.right.at(vG_buf.top())), false); | |
518 | vG_buf.pop(); | |
519 | } | |
520 | ||
521 | } | |
522 | ||
523 | put(diG, iG_bimap.left.at(m), false); | |
524 | put(dvG, vG_bimap.left.at(m), false); | |
525 | ||
526 | } | |
527 | } | |
528 | } | |
529 | ||
530 | } // namespace detail | |
531 | ||
532 | ||
533 | ||
534 | template <typename Coll, typename Seq> | |
535 | struct tree_collector | |
536 | { | |
537 | ||
538 | public: | |
539 | BOOST_CONCEPT_ASSERT((BackInsertionSequence<Coll>)); | |
540 | BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>)); | |
541 | BOOST_CONCEPT_ASSERT((CopyConstructible<Seq>)); | |
542 | ||
543 | typedef typename Coll::value_type coll_value_type; | |
544 | typedef typename Seq::value_type seq_value_type; | |
545 | ||
546 | BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value)); | |
547 | BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); | |
548 | ||
549 | tree_collector(Coll& seqs): mSeqs(seqs) { } | |
550 | ||
551 | inline void operator()(Seq seq) | |
552 | { mSeqs.push_back(seq); } | |
553 | ||
554 | private: | |
555 | Coll& mSeqs; | |
556 | ||
557 | }; | |
558 | ||
559 | ||
560 | ||
561 | template < | |
562 | typename Graph, | |
563 | typename Order, | |
564 | typename Func, | |
565 | typename Seq | |
566 | > | |
567 | BOOST_CONCEPT_REQUIRES( | |
568 | ((RandomAccessContainer<Order>)) | |
569 | ((IncidenceGraphConcept<Graph>)) | |
570 | ((UnaryFunction<Func, void, Seq>)) | |
571 | ((Mutable_RandomAccessContainer<Seq>)) | |
572 | ((VertexAndEdgeListGraphConcept<Graph>)), | |
573 | (void) | |
574 | ) | |
575 | two_graphs_common_spanning_trees | |
576 | ( | |
577 | const Graph& iG, | |
578 | Order iG_map, | |
579 | const Graph& vG, | |
580 | Order vG_map, | |
581 | Func func, | |
582 | Seq inL | |
583 | ) | |
584 | { | |
585 | typedef graph_traits<Graph> GraphTraits; | |
586 | ||
587 | typedef typename GraphTraits::directed_category directed_category; | |
588 | typedef typename GraphTraits::vertex_descriptor vertex_descriptor; | |
589 | typedef typename GraphTraits::edge_descriptor edge_descriptor; | |
590 | ||
591 | typedef typename GraphTraits::edges_size_type edges_size_type; | |
592 | typedef typename GraphTraits::edge_iterator edge_iterator; | |
593 | ||
594 | typedef typename Seq::value_type seq_value_type; | |
595 | typedef typename Seq::size_type seq_size_type; | |
596 | ||
597 | typedef typename Order::value_type order_value_type; | |
598 | typedef typename Order::size_type order_size_type; | |
599 | ||
600 | BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value)); | |
601 | BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>)); | |
602 | ||
603 | BOOST_CONCEPT_ASSERT((Convertible<seq_size_type, edges_size_type>)); | |
604 | BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); | |
605 | ||
606 | BOOST_STATIC_ASSERT((is_same<directed_category, undirected_tag>::value)); | |
607 | ||
608 | if(num_vertices(iG) != num_vertices(vG)) | |
609 | return; | |
610 | ||
611 | if(inL.size() != num_edges(iG) | |
612 | || inL.size() != num_edges(vG)) | |
613 | return; | |
614 | ||
615 | if(iG_map.size() != num_edges(iG) | |
616 | || vG_map.size() != num_edges(vG)) | |
617 | return; | |
618 | ||
619 | typedef bimaps::bimap< | |
620 | bimaps::set_of< int >, | |
621 | bimaps::set_of< order_value_type > | |
622 | > bimap_type; | |
623 | typedef typename bimap_type::value_type bimap_value; | |
624 | ||
625 | bimap_type iG_bimap, vG_bimap; | |
626 | for(order_size_type i = 0; i < iG_map.size(); ++i) | |
627 | iG_bimap.insert(bimap_value(i, iG_map[i])); | |
628 | for(order_size_type i = 0; i < vG_map.size(); ++i) | |
629 | vG_bimap.insert(bimap_value(i, vG_map[i])); | |
630 | ||
631 | edge_iterator current, last; | |
632 | boost::tuples::tie(current, last) = edges(iG); | |
633 | for(; current != last; ++current) | |
634 | if(iG_bimap.right.find(*current) == iG_bimap.right.end()) | |
635 | return; | |
636 | boost::tuples::tie(current, last) = edges(vG); | |
637 | for(; current != last; ++current) | |
638 | if(vG_bimap.right.find(*current) == vG_bimap.right.end()) | |
639 | return; | |
640 | ||
641 | std::stack<edge_descriptor> iG_buf, vG_buf; | |
642 | ||
643 | std::map<vertex_descriptor, edge_descriptor> tree_map; | |
644 | std::map<vertex_descriptor, vertex_descriptor> pred_map; | |
645 | std::map<vertex_descriptor, int> dist_map, low_map; | |
646 | ||
647 | detail::bridges_visitor< | |
648 | associative_property_map< | |
649 | std::map<vertex_descriptor, edge_descriptor> | |
650 | >, | |
651 | associative_property_map< | |
652 | std::map<vertex_descriptor, vertex_descriptor> | |
653 | >, | |
654 | associative_property_map< std::map<vertex_descriptor, int> >, | |
655 | associative_property_map< std::map<vertex_descriptor, int> >, | |
656 | std::stack<edge_descriptor> | |
657 | > | |
658 | iG_vis( | |
659 | associative_property_map< | |
660 | std::map< vertex_descriptor, edge_descriptor> >(tree_map), | |
661 | associative_property_map< | |
662 | std::map< vertex_descriptor, vertex_descriptor> >(pred_map), | |
663 | associative_property_map<std::map< vertex_descriptor, int> >(dist_map), | |
664 | associative_property_map<std::map< vertex_descriptor, int> >(low_map), | |
665 | iG_buf | |
666 | ), | |
667 | vG_vis( | |
668 | associative_property_map< | |
669 | std::map< vertex_descriptor, edge_descriptor> >(tree_map), | |
670 | associative_property_map< | |
671 | std::map< vertex_descriptor, vertex_descriptor> >(pred_map), | |
672 | associative_property_map<std::map< vertex_descriptor, int> >(dist_map), | |
673 | associative_property_map<std::map< vertex_descriptor, int> >(low_map), | |
674 | vG_buf | |
675 | ); | |
676 | ||
677 | std::map<vertex_descriptor, default_color_type> vertex_color; | |
678 | std::map<edge_descriptor, default_color_type> edge_color; | |
679 | ||
680 | undirected_dfs(iG, iG_vis, | |
681 | associative_property_map< | |
682 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
683 | associative_property_map< | |
684 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
685 | ); | |
686 | undirected_dfs(vG, vG_vis, | |
687 | associative_property_map< | |
688 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
689 | associative_property_map< | |
690 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
691 | ); | |
692 | ||
693 | while(!iG_buf.empty()) { | |
694 | inL[iG_bimap.right.at(iG_buf.top())] = true; | |
695 | iG_buf.pop(); | |
696 | } | |
697 | while(!vG_buf.empty()) { | |
698 | inL[vG_bimap.right.at(vG_buf.top())] = true; | |
699 | vG_buf.pop(); | |
700 | } | |
701 | ||
702 | std::map<edge_descriptor, bool> iG_inL, vG_inL; | |
703 | associative_property_map< std::map<edge_descriptor, bool> > | |
704 | aiG_inL(iG_inL), avG_inL(vG_inL); | |
705 | ||
706 | for(seq_size_type i = 0; i < inL.size(); ++i) | |
707 | { | |
708 | if(inL[i]) { | |
709 | put(aiG_inL, iG_bimap.left.at(i), true); | |
710 | put(avG_inL, vG_bimap.left.at(i), true); | |
711 | } else { | |
712 | put(aiG_inL, iG_bimap.left.at(i), false); | |
713 | put(avG_inL, vG_bimap.left.at(i), false); | |
714 | } | |
715 | } | |
716 | ||
717 | undirected_dfs( | |
718 | make_filtered_graph(iG, | |
719 | detail::inL_edge_status< associative_property_map< | |
720 | std::map<edge_descriptor, bool> > >(aiG_inL)), | |
721 | make_dfs_visitor( | |
722 | detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), | |
723 | associative_property_map< | |
724 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
725 | associative_property_map< | |
726 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
727 | ); | |
728 | undirected_dfs( | |
729 | make_filtered_graph(vG, | |
730 | detail::inL_edge_status< associative_property_map< | |
731 | std::map<edge_descriptor, bool> > >(avG_inL)), | |
732 | make_dfs_visitor( | |
733 | detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), | |
734 | associative_property_map< | |
735 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
736 | associative_property_map< | |
737 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
738 | ); | |
739 | ||
740 | if(iG_buf.empty() && vG_buf.empty()) { | |
741 | ||
742 | std::map<edge_descriptor, bool> iG_deleted, vG_deleted; | |
743 | associative_property_map< std::map<edge_descriptor, bool> > diG(iG_deleted); | |
744 | associative_property_map< std::map<edge_descriptor, bool> > dvG(vG_deleted); | |
745 | ||
746 | boost::tuples::tie(current, last) = edges(iG); | |
747 | for(; current != last; ++current) | |
748 | put(diG, *current, false); | |
749 | boost::tuples::tie(current, last) = edges(vG); | |
750 | for(; current != last; ++current) | |
751 | put(dvG, *current, false); | |
752 | ||
753 | for(seq_size_type j = 0; j < inL.size(); ++j) { | |
754 | if(!inL[j]) { | |
755 | put(aiG_inL, iG_bimap.left.at(j), true); | |
756 | put(avG_inL, vG_bimap.left.at(j), true); | |
757 | ||
758 | undirected_dfs( | |
759 | make_filtered_graph(iG, | |
760 | detail::inL_edge_status< associative_property_map< | |
761 | std::map<edge_descriptor, bool> > >(aiG_inL)), | |
762 | make_dfs_visitor( | |
763 | detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), | |
764 | associative_property_map< | |
765 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
766 | associative_property_map< | |
767 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
768 | ); | |
769 | undirected_dfs( | |
770 | make_filtered_graph(vG, | |
771 | detail::inL_edge_status< associative_property_map< | |
772 | std::map<edge_descriptor, bool> > >(avG_inL)), | |
773 | make_dfs_visitor( | |
774 | detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), | |
775 | associative_property_map< | |
776 | std::map<vertex_descriptor, default_color_type> >(vertex_color), | |
777 | associative_property_map< | |
778 | std::map<edge_descriptor, default_color_type> >(edge_color) | |
779 | ); | |
780 | ||
781 | if(!iG_buf.empty() || !vG_buf.empty()) { | |
782 | while(!iG_buf.empty()) iG_buf.pop(); | |
783 | while(!vG_buf.empty()) vG_buf.pop(); | |
784 | put(diG, iG_bimap.left.at(j), true); | |
785 | put(dvG, vG_bimap.left.at(j), true); | |
786 | } | |
787 | ||
788 | put(aiG_inL, iG_bimap.left.at(j), false); | |
789 | put(avG_inL, vG_bimap.left.at(j), false); | |
790 | } | |
791 | } | |
792 | ||
793 | int cc = 0; | |
794 | ||
795 | std::map<vertex_descriptor, int> com_map; | |
796 | cc += connected_components( | |
797 | make_filtered_graph(iG, | |
798 | detail::deleted_edge_status<associative_property_map< | |
799 | std::map<edge_descriptor, bool> > >(diG)), | |
800 | associative_property_map<std::map<vertex_descriptor, int> >(com_map) | |
801 | ); | |
802 | cc += connected_components( | |
803 | make_filtered_graph(vG, | |
804 | detail::deleted_edge_status<associative_property_map< | |
805 | std::map<edge_descriptor, bool> > >(dvG)), | |
806 | associative_property_map< std::map<vertex_descriptor, int> >(com_map) | |
807 | ); | |
808 | ||
809 | if(cc != 2) | |
810 | return; | |
811 | ||
812 | // REC | |
813 | detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, | |
814 | associative_property_map< std::map<edge_descriptor, bool> > > | |
815 | (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); | |
816 | ||
817 | } | |
818 | ||
819 | } | |
820 | ||
821 | ||
822 | template < | |
823 | typename Graph, | |
824 | typename Func, | |
825 | typename Seq | |
826 | > | |
827 | BOOST_CONCEPT_REQUIRES( | |
828 | ((IncidenceGraphConcept<Graph>)) | |
829 | ((EdgeListGraphConcept<Graph>)), | |
830 | (void) | |
831 | ) | |
832 | two_graphs_common_spanning_trees | |
833 | ( | |
834 | const Graph& iG, | |
835 | const Graph& vG, | |
836 | Func func, | |
837 | Seq inL | |
838 | ) | |
839 | { | |
840 | typedef graph_traits<Graph> GraphTraits; | |
841 | ||
842 | typedef typename GraphTraits::edge_descriptor edge_descriptor; | |
843 | typedef typename GraphTraits::edge_iterator edge_iterator; | |
844 | ||
845 | std::vector<edge_descriptor> iGO, vGO; | |
846 | edge_iterator curr, last; | |
847 | ||
848 | boost::tuples::tie(curr, last) = edges(iG); | |
849 | for(; curr != last; ++curr) | |
850 | iGO.push_back(*curr); | |
851 | ||
852 | boost::tuples::tie(curr, last) = edges(vG); | |
853 | for(; curr != last; ++curr) | |
854 | vGO.push_back(*curr); | |
855 | ||
856 | two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL); | |
857 | } | |
858 | ||
859 | ||
860 | } // namespace boost | |
861 | ||
862 | ||
863 | #endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP |