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