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)
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
12 #ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
13 #define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
16 #include <boost/config.hpp>
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>
45 struct bridges_visitor: public default_dfs_visitor
53 ): mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer)
56 template <typename Vertex, typename Graph>
57 void initialize_vertex(const Vertex& u, const Graph& g)
63 template <typename Vertex, typename Graph>
64 void discover_vertex(const Vertex& u, const Graph& g)
66 put(mDist, u, ++mNum);
67 put(mLow, u, get(mDist, u));
70 template <typename Edge, typename Graph>
71 void tree_edge(const Edge& e, const Graph& g)
73 put(mPred, target(e, g), source(e, g));
74 put(mTree, target(e, g), e);
77 template <typename Edge, typename Graph>
78 void back_edge(const Edge& e, const Graph& g)
80 put(mLow, source(e, g),
81 (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g))));
84 template <typename Vertex, typename Graph>
85 void finish_vertex(const Vertex& u, const Graph& g)
87 Vertex parent = get(mPred, u);
88 if(get(mLow, u) > get(mDist, parent))
89 mBuffer.push(get(mTree, u));
91 (std::min)(get(mLow, parent), get(mLow, u)));
103 template <typename Buffer>
104 struct cycle_finder: public base_visitor< cycle_finder<Buffer> >
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)
120 template <typename DeletedMap>
121 struct deleted_edge_status
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)); }
132 template <typename InLMap>
133 struct inL_edge_status
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); }
150 void rec_two_graphs_common_spanning_trees
155 bimaps::set_of< typename graph_traits<Graph>::edge_descriptor >
162 bimaps::set_of< typename graph_traits<Graph>::edge_descriptor >
170 typedef graph_traits<Graph> GraphTraits;
172 typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
173 typedef typename GraphTraits::edge_descriptor edge_descriptor;
175 typedef typename Seq::size_type seq_size_type;
177 int edges = num_vertices(iG) - 1;
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.
186 // Here is proposed the previous guard (that was wrong):
187 // for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i)
190 for(seq_size_type i = 0; i < inL.size(); ++i)
198 bool is_tree = (edges == 0);
202 std::map<vertex_descriptor, default_color_type> vertex_color;
203 std::map<edge_descriptor, default_color_type> edge_color;
205 std::stack<edge_descriptor> iG_buf, vG_buf;
209 for(seq_size_type j = 0; j < inL.size() && !found; ++j) {
211 && !get(diG, iG_bimap.left.at(j))
212 && !get(dvG, vG_bimap.left.at(j)))
214 put(aiG_inL, iG_bimap.left.at(j), true);
215 put(avG_inL, vG_bimap.left.at(j), true);
218 make_filtered_graph(iG,
219 detail::inL_edge_status< associative_property_map<
220 std::map<edge_descriptor, bool> > >(aiG_inL)),
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)
229 make_filtered_graph(vG,
230 detail::inL_edge_status< associative_property_map<
231 std::map<edge_descriptor, bool> > >(avG_inL)),
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)
240 if(iG_buf.empty() && vG_buf.empty()) {
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);
255 std::stack<edge_descriptor> iG_buf_copy, vG_buf_copy;
256 for(seq_size_type j = 0; j < inL.size(); ++j) {
258 && !get(diG, iG_bimap.left.at(j))
259 && !get(dvG, vG_bimap.left.at(j)))
262 put(aiG_inL, iG_bimap.left.at(j), true);
263 put(avG_inL, vG_bimap.left.at(j), true);
266 make_filtered_graph(iG,
267 detail::inL_edge_status< associative_property_map<
268 std::map<edge_descriptor, bool> > >(aiG_inL)),
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)
278 make_filtered_graph(vG,
279 detail::inL_edge_status< associative_property_map<
280 std::map<edge_descriptor, bool> > >(avG_inL)),
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)
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));
299 put(aiG_inL, iG_bimap.left.at(j), false);
300 put(avG_inL, vG_bimap.left.at(j), false);
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);
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);
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);
322 put(aiG_inL, iG_bimap.left.at(m), false);
323 put(avG_inL, vG_bimap.left.at(m), false);
325 put(diG, iG_bimap.left.at(m), true);
326 put(dvG, vG_bimap.left.at(m), true);
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;
332 detail::bridges_visitor<
333 associative_property_map<
334 std::map<vertex_descriptor, edge_descriptor>
336 associative_property_map<
337 std::map<vertex_descriptor, vertex_descriptor>
339 associative_property_map< std::map<vertex_descriptor, int> >,
340 associative_property_map< std::map<vertex_descriptor, int> >,
341 std::stack<edge_descriptor>
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),
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),
366 undirected_dfs(make_filtered_graph(iG,
367 detail::deleted_edge_status< associative_property_map<
368 std::map<edge_descriptor, bool> > >(diG)),
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)
375 undirected_dfs(make_filtered_graph(vG,
376 detail::deleted_edge_status< associative_property_map<
377 std::map<edge_descriptor, bool> > >(dvG)),
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)
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);
394 make_filtered_graph(iG,
395 detail::inL_edge_status< associative_property_map<
396 std::map<edge_descriptor, bool> > >(aiG_inL)),
398 detail::cycle_finder<
399 std::stack<edge_descriptor> > (&iG_buf_tmp)),
400 associative_property_map<
402 vertex_descriptor, default_color_type> >(vertex_color),
403 associative_property_map<
404 std::map<edge_descriptor, default_color_type> >(edge_color)
407 make_filtered_graph(vG,
408 detail::inL_edge_status< associative_property_map<
409 std::map<edge_descriptor, bool> > >(avG_inL)),
411 detail::cycle_finder<
412 std::stack<edge_descriptor> > (&vG_buf_tmp)),
413 associative_property_map<
415 vertex_descriptor, default_color_type> >(vertex_color),
416 associative_property_map<
417 std::map<edge_descriptor, default_color_type> >(edge_color)
420 if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) {
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());
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);
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);
441 make_filtered_graph(iG,
442 detail::inL_edge_status< associative_property_map<
443 std::map<edge_descriptor, bool> > >(aiG_inL)),
445 detail::cycle_finder<
446 std::stack<edge_descriptor> > (&iG_buf_tmp)),
447 associative_property_map<
449 vertex_descriptor, default_color_type> >(vertex_color),
450 associative_property_map<
451 std::map<edge_descriptor, default_color_type> >(edge_color)
454 make_filtered_graph(vG,
455 detail::inL_edge_status< associative_property_map<
456 std::map<edge_descriptor, bool> > >(avG_inL)),
458 detail::cycle_finder<
459 std::stack<edge_descriptor> > (&vG_buf_tmp)),
460 associative_property_map<
462 vertex_descriptor, default_color_type> >(vertex_color),
463 associative_property_map<
464 std::map<edge_descriptor, default_color_type> >(edge_color)
467 if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) {
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());
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);
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());
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());
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);
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);
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);
523 put(diG, iG_bimap.left.at(m), false);
524 put(dvG, vG_bimap.left.at(m), false);
530 } // namespace detail
534 template <typename Coll, typename Seq>
535 struct tree_collector
539 BOOST_CONCEPT_ASSERT((BackInsertionSequence<Coll>));
540 BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>));
541 BOOST_CONCEPT_ASSERT((CopyConstructible<Seq>));
543 typedef typename Coll::value_type coll_value_type;
544 typedef typename Seq::value_type seq_value_type;
546 BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value));
547 BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
549 tree_collector(Coll& seqs): mSeqs(seqs) { }
551 inline void operator()(Seq seq)
552 { mSeqs.push_back(seq); }
567 BOOST_CONCEPT_REQUIRES(
568 ((RandomAccessContainer<Order>))
569 ((IncidenceGraphConcept<Graph>))
570 ((UnaryFunction<Func, void, Seq>))
571 ((Mutable_RandomAccessContainer<Seq>))
572 ((VertexAndEdgeListGraphConcept<Graph>)),
575 two_graphs_common_spanning_trees
585 typedef graph_traits<Graph> GraphTraits;
587 typedef typename GraphTraits::directed_category directed_category;
588 typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
589 typedef typename GraphTraits::edge_descriptor edge_descriptor;
591 typedef typename GraphTraits::edges_size_type edges_size_type;
592 typedef typename GraphTraits::edge_iterator edge_iterator;
594 typedef typename Seq::value_type seq_value_type;
595 typedef typename Seq::size_type seq_size_type;
597 typedef typename Order::value_type order_value_type;
598 typedef typename Order::size_type order_size_type;
600 BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value));
601 BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>));
603 BOOST_CONCEPT_ASSERT((Convertible<seq_size_type, edges_size_type>));
604 BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
606 BOOST_STATIC_ASSERT((is_same<directed_category, undirected_tag>::value));
608 if(num_vertices(iG) != num_vertices(vG))
611 if(inL.size() != num_edges(iG)
612 || inL.size() != num_edges(vG))
615 if(iG_map.size() != num_edges(iG)
616 || vG_map.size() != num_edges(vG))
619 typedef bimaps::bimap<
620 bimaps::set_of< int >,
621 bimaps::set_of< order_value_type >
623 typedef typename bimap_type::value_type bimap_value;
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]));
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())
636 boost::tuples::tie(current, last) = edges(vG);
637 for(; current != last; ++current)
638 if(vG_bimap.right.find(*current) == vG_bimap.right.end())
641 std::stack<edge_descriptor> iG_buf, vG_buf;
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;
647 detail::bridges_visitor<
648 associative_property_map<
649 std::map<vertex_descriptor, edge_descriptor>
651 associative_property_map<
652 std::map<vertex_descriptor, vertex_descriptor>
654 associative_property_map< std::map<vertex_descriptor, int> >,
655 associative_property_map< std::map<vertex_descriptor, int> >,
656 std::stack<edge_descriptor>
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),
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),
677 std::map<vertex_descriptor, default_color_type> vertex_color;
678 std::map<edge_descriptor, default_color_type> edge_color;
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)
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)
693 while(!iG_buf.empty()) {
694 inL[iG_bimap.right.at(iG_buf.top())] = true;
697 while(!vG_buf.empty()) {
698 inL[vG_bimap.right.at(vG_buf.top())] = true;
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);
706 for(seq_size_type i = 0; i < inL.size(); ++i)
709 put(aiG_inL, iG_bimap.left.at(i), true);
710 put(avG_inL, vG_bimap.left.at(i), true);
712 put(aiG_inL, iG_bimap.left.at(i), false);
713 put(avG_inL, vG_bimap.left.at(i), false);
718 make_filtered_graph(iG,
719 detail::inL_edge_status< associative_property_map<
720 std::map<edge_descriptor, bool> > >(aiG_inL)),
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)
729 make_filtered_graph(vG,
730 detail::inL_edge_status< associative_property_map<
731 std::map<edge_descriptor, bool> > >(avG_inL)),
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)
740 if(iG_buf.empty() && vG_buf.empty()) {
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);
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);
753 for(seq_size_type j = 0; j < inL.size(); ++j) {
755 put(aiG_inL, iG_bimap.left.at(j), true);
756 put(avG_inL, vG_bimap.left.at(j), true);
759 make_filtered_graph(iG,
760 detail::inL_edge_status< associative_property_map<
761 std::map<edge_descriptor, bool> > >(aiG_inL)),
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)
770 make_filtered_graph(vG,
771 detail::inL_edge_status< associative_property_map<
772 std::map<edge_descriptor, bool> > >(avG_inL)),
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)
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);
788 put(aiG_inL, iG_bimap.left.at(j), false);
789 put(avG_inL, vG_bimap.left.at(j), false);
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)
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)
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);
827 BOOST_CONCEPT_REQUIRES(
828 ((IncidenceGraphConcept<Graph>))
829 ((EdgeListGraphConcept<Graph>)),
832 two_graphs_common_spanning_trees
840 typedef graph_traits<Graph> GraphTraits;
842 typedef typename GraphTraits::edge_descriptor edge_descriptor;
843 typedef typename GraphTraits::edge_iterator edge_iterator;
845 std::vector<edge_descriptor> iGO, vGO;
846 edge_iterator curr, last;
848 boost::tuples::tie(curr, last) = edges(iG);
849 for(; curr != last; ++curr)
850 iGO.push_back(*curr);
852 boost::tuples::tie(curr, last) = edges(vG);
853 for(; curr != last; ++curr)
854 vGO.push_back(*curr);
856 two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL);
863 #endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP