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 {
bridges_visitorboost::detail::bridges_visitor37 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 >
initialize_vertexboost::detail::bridges_visitor45 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 >
discover_vertexboost::detail::bridges_visitor52 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 >
tree_edgeboost::detail::bridges_visitor59 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 >
back_edgeboost::detail::bridges_visitor66 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 >
finish_vertexboost::detail::bridges_visitor73 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;
cycle_finderboost::detail::cycle_finder93 cycle_finder() : mBuffer(0) {}
cycle_finderboost::detail::cycle_finder94 cycle_finder(Buffer* buffer) : mBuffer(buffer) {}
95 template < typename Edge, typename Graph >
operator ()boost::detail::cycle_finder96 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 {
deleted_edge_statusboost::detail::deleted_edge_status106 deleted_edge_status() {}
deleted_edge_statusboost::detail::deleted_edge_status107 deleted_edge_status(DeletedMap map) : mMap(map) {}
operator ()boost::detail::deleted_edge_status108 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 {
inL_edge_statusboost::detail::inL_edge_status117 inL_edge_status() {}
inL_edge_statusboost::detail::inL_edge_status118 inL_edge_status(InLMap map) : mMap(map) {}
operator ()boost::detail::inL_edge_status119 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 >
rec_two_graphs_common_spanning_trees(const Graph & iG,bimap<bimaps::set_of<int>,bimaps::set_of<typename graph_traits<Graph>::edge_descriptor>> iG_bimap,Map aiG_inL,Map diG,const Graph & vG,bimap<bimaps::set_of<int>,bimaps::set_of<typename graph_traits<Graph>::edge_descriptor>> vG_bimap,Map avG_inL,Map dvG,Func func,Seq inL)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
tree_collectorboost::tree_collector565 tree_collector(Coll& seqs) : mSeqs(seqs) {}
566
operator ()boost::tree_collector567 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))
two_graphs_common_spanning_trees(const Graph & iG,Order iG_map,const Graph & vG,Order vG_map,Func func,Seq inL)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))
two_graphs_common_spanning_trees(const Graph & iG,const Graph & vG,Func func,Seq inL)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