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
30namespace boost
31{
32
33
34namespace 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
534template <typename Coll, typename Seq>
535struct tree_collector
536{
537
538public:
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
554private:
555 Coll& mSeqs;
556
557};
558
559
560
561template <
562 typename Graph,
563 typename Order,
564 typename Func,
565 typename Seq
566>
567BOOST_CONCEPT_REQUIRES(
568 ((RandomAccessContainer<Order>))
569 ((IncidenceGraphConcept<Graph>))
570 ((UnaryFunction<Func, void, Seq>))
571 ((Mutable_RandomAccessContainer<Seq>))
572 ((VertexAndEdgeListGraphConcept<Graph>)),
573 (void)
574)
575two_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
822template <
823 typename Graph,
824 typename Func,
825 typename Seq
826>
827BOOST_CONCEPT_REQUIRES(
828 ((IncidenceGraphConcept<Graph>))
829 ((EdgeListGraphConcept<Graph>)),
830 (void)
831)
832two_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

source code of boost/boost/graph/two_graphs_common_spanning_trees.hpp