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 |
864 | |