boost/graph/two_graphs_common_spanning_trees.hpp
// Copyright (C) 2012, Michele Caini. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // Two Graphs Common Spanning Trees Algorithm // Based on academic article of Mint, Read and Tarjan // Efficient Algorithm for Common Spanning Tree Problem // Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347 #ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP #define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP #include <boost/config.hpp> #include <boost/bimap.hpp> #include <boost/type_traits.hpp> #include <boost/concept/requires.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/undirected_dfs.hpp> #include <boost/graph/connected_components.hpp> #include <boost/graph/filtered_graph.hpp> #include <vector> #include <stack> #include <map> namespace boost { namespace detail { template < typename TreeMap, typename PredMap, typename DistMap, typename LowMap, typename Buffer > struct bridges_visitor: public default_dfs_visitor { bridges_visitor( TreeMap tree, PredMap pred, DistMap dist, LowMap low, Buffer& buffer ): mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer) { mNum = -1; } template <typename Vertex, typename Graph> void initialize_vertex(const Vertex& u, const Graph& g) { put(mPred, u, u); put(mDist, u, -1); } template <typename Vertex, typename Graph> void discover_vertex(const Vertex& u, const Graph& g) { put(mDist, u, ++mNum); put(mLow, u, get(mDist, u)); } template <typename Edge, typename Graph> void tree_edge(const Edge& e, const Graph& g) { put(mPred, target(e, g), source(e, g)); put(mTree, target(e, g), e); } template <typename Edge, typename Graph> void back_edge(const Edge& e, const Graph& g) { put(mLow, source(e, g), (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g)))); } template <typename Vertex, typename Graph> void finish_vertex(const Vertex& u, const Graph& g) { Vertex parent = get(mPred, u); if(get(mLow, u) > get(mDist, parent)) mBuffer.push(get(mTree, u)); put(mLow, parent, (std::min)(get(mLow, parent), get(mLow, u))); } TreeMap mTree; PredMap mPred; DistMap mDist; LowMap mLow; Buffer& mBuffer; int mNum; }; template <typename Buffer> struct cycle_finder: public base_visitor< cycle_finder<Buffer> > { typedef on_back_edge event_filter; cycle_finder(): mBuffer(0) { } cycle_finder(Buffer* buffer) : mBuffer(buffer) { } template <typename Edge, typename Graph> void operator()(const Edge& e, const Graph& g) { if(mBuffer) mBuffer->push(e); } Buffer* mBuffer; }; template <typename DeletedMap> struct deleted_edge_status { deleted_edge_status() { } deleted_edge_status(DeletedMap map): mMap(map) { } template <typename Edge> bool operator()(const Edge& e) const { return (!get(mMap, e)); } DeletedMap mMap; }; template <typename InLMap> struct inL_edge_status { inL_edge_status() { } inL_edge_status(InLMap map): mMap(map) { } template <typename Edge> bool operator()(const Edge& e) const { return get(mMap, e); } InLMap mMap; }; template < typename Graph, typename Func, typename Seq, typename Map > void 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 ) { typedef graph_traits<Graph> GraphTraits; typedef typename GraphTraits::vertex_descriptor vertex_descriptor; typedef typename GraphTraits::edge_descriptor edge_descriptor; typedef typename Seq::size_type seq_size_type; int edges = num_vertices(iG) - 1; // // [ Michele Caini ] // // Using the condition (edges != 0) leads to the accidental submission of // sub-graphs ((V-1+1)-fake-tree, named here fat-tree). // Remove this condition is a workaround for the problem of fat-trees. // Please do not add that condition, even if it improves performance. // // Here is proposed the previous guard (that was wrong): // for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i) // { for(seq_size_type i = 0; i < inL.size(); ++i) if(inL[i]) --edges; if(edges < 0) return; } bool is_tree = (edges == 0); if(is_tree) { func(inL); } else { std::map<vertex_descriptor, default_color_type> vertex_color; std::map<edge_descriptor, default_color_type> edge_color; std::stack<edge_descriptor> iG_buf, vG_buf; bool found = false; seq_size_type m; for(seq_size_type j = 0; j < inL.size() && !found; ++j) { if(!inL[j] && !get(diG, iG_bimap.left.at(j)) && !get(dvG, vG_bimap.left.at(j))) { put(aiG_inL, iG_bimap.left.at(j), true); put(avG_inL, vG_bimap.left.at(j), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); if(iG_buf.empty() && vG_buf.empty()) { inL[j] = true; found = true; m = j; } else { while(!iG_buf.empty()) iG_buf.pop(); while(!vG_buf.empty()) vG_buf.pop(); put(aiG_inL, iG_bimap.left.at(j), false); put(avG_inL, vG_bimap.left.at(j), false); } } } if(found) { std::stack<edge_descriptor> iG_buf_copy, vG_buf_copy; for(seq_size_type j = 0; j < inL.size(); ++j) { if(!inL[j] && !get(diG, iG_bimap.left.at(j)) && !get(dvG, vG_bimap.left.at(j))) { put(aiG_inL, iG_bimap.left.at(j), true); put(avG_inL, vG_bimap.left.at(j), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); if(!iG_buf.empty() || !vG_buf.empty()) { while(!iG_buf.empty()) iG_buf.pop(); while(!vG_buf.empty()) vG_buf.pop(); put(diG, iG_bimap.left.at(j), true); put(dvG, vG_bimap.left.at(j), true); iG_buf_copy.push(iG_bimap.left.at(j)); vG_buf_copy.push(vG_bimap.left.at(j)); } put(aiG_inL, iG_bimap.left.at(j), false); put(avG_inL, vG_bimap.left.at(j), false); } } // REC detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, Map> (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); while(!iG_buf_copy.empty()) { put(diG, iG_buf_copy.top(), false); put(dvG, vG_bimap.left.at( iG_bimap.right.at(iG_buf_copy.top())), false); iG_buf_copy.pop(); } while(!vG_buf_copy.empty()) { put(dvG, vG_buf_copy.top(), false); put(diG, iG_bimap.left.at( vG_bimap.right.at(vG_buf_copy.top())), false); vG_buf_copy.pop(); } inL[m] = false; put(aiG_inL, iG_bimap.left.at(m), false); put(avG_inL, vG_bimap.left.at(m), false); put(diG, iG_bimap.left.at(m), true); put(dvG, vG_bimap.left.at(m), true); std::map<vertex_descriptor, edge_descriptor> tree_map; std::map<vertex_descriptor, vertex_descriptor> pred_map; std::map<vertex_descriptor, int> dist_map, low_map; detail::bridges_visitor< associative_property_map< std::map<vertex_descriptor, edge_descriptor> >, associative_property_map< std::map<vertex_descriptor, vertex_descriptor> >, associative_property_map< std::map<vertex_descriptor, int> >, associative_property_map< std::map<vertex_descriptor, int> >, std::stack<edge_descriptor> > iG_vis( associative_property_map< std::map< vertex_descriptor, edge_descriptor> >(tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor> >(pred_map), associative_property_map< std::map< vertex_descriptor, int> >(dist_map), associative_property_map< std::map< vertex_descriptor, int> >(low_map), iG_buf ), vG_vis( associative_property_map< std::map< vertex_descriptor, edge_descriptor> >(tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor> >(pred_map), associative_property_map< std::map< vertex_descriptor, int> >(dist_map), associative_property_map< std::map< vertex_descriptor, int> >(low_map), vG_buf ); undirected_dfs(make_filtered_graph(iG, detail::deleted_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(diG)), iG_vis, associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs(make_filtered_graph(vG, detail::deleted_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(dvG)), vG_vis, associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); found = false; std::stack<edge_descriptor> iG_buf_tmp, vG_buf_tmp; while(!iG_buf.empty() && !found) { if(!inL[iG_bimap.right.at(iG_buf.top())]) { put(aiG_inL, iG_buf.top(), true); put(avG_inL, vG_bimap.left.at( iG_bimap.right.at(iG_buf.top())), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { found = true; } else { while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); iG_buf_copy.push(iG_buf.top()); } put(aiG_inL, iG_buf.top(), false); put(avG_inL, vG_bimap.left.at( iG_bimap.right.at(iG_buf.top())), false); } iG_buf.pop(); } while(!vG_buf.empty() && !found) { if(!inL[vG_bimap.right.at(vG_buf.top())]) { put(avG_inL, vG_buf.top(), true); put(aiG_inL, iG_bimap.left.at( vG_bimap.right.at(vG_buf.top())), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { found = true; } else { while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); vG_buf_copy.push(vG_buf.top()); } put(avG_inL, vG_buf.top(), false); put(aiG_inL, iG_bimap.left.at( vG_bimap.right.at(vG_buf.top())), false); } vG_buf.pop(); } if(!found) { while(!iG_buf_copy.empty()) { inL[iG_bimap.right.at(iG_buf_copy.top())] = true; put(aiG_inL, iG_buf_copy.top(), true); put(avG_inL, vG_bimap.left.at( iG_bimap.right.at(iG_buf_copy.top())), true); iG_buf.push(iG_buf_copy.top()); iG_buf_copy.pop(); } while(!vG_buf_copy.empty()) { inL[vG_bimap.right.at(vG_buf_copy.top())] = true; put(avG_inL, vG_buf_copy.top(), true); put(aiG_inL, iG_bimap.left.at( vG_bimap.right.at(vG_buf_copy.top())), true); vG_buf.push(vG_buf_copy.top()); vG_buf_copy.pop(); } // REC detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq, Map> (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); while(!iG_buf.empty()) { inL[iG_bimap.right.at(iG_buf.top())] = false; put(aiG_inL, iG_buf.top(), false); put(avG_inL, vG_bimap.left.at( iG_bimap.right.at(iG_buf.top())), false); iG_buf.pop(); } while(!vG_buf.empty()) { inL[vG_bimap.right.at(vG_buf.top())] = false; put(avG_inL, vG_buf.top(), false); put(aiG_inL, iG_bimap.left.at( vG_bimap.right.at(vG_buf.top())), false); vG_buf.pop(); } } put(diG, iG_bimap.left.at(m), false); put(dvG, vG_bimap.left.at(m), false); } } } } // namespace detail template <typename Coll, typename Seq> struct tree_collector { public: BOOST_CONCEPT_ASSERT((BackInsertionSequence<Coll>)); BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>)); BOOST_CONCEPT_ASSERT((CopyConstructible<Seq>)); typedef typename Coll::value_type coll_value_type; typedef typename Seq::value_type seq_value_type; BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value)); BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); tree_collector(Coll& seqs): mSeqs(seqs) { } inline void operator()(Seq seq) { mSeqs.push_back(seq); } private: Coll& mSeqs; }; template < typename Graph, typename Order, typename Func, typename Seq > BOOST_CONCEPT_REQUIRES( ((RandomAccessContainer<Order>)) ((IncidenceGraphConcept<Graph>)) ((UnaryFunction<Func, void, Seq>)) ((Mutable_RandomAccessContainer<Seq>)) ((VertexAndEdgeListGraphConcept<Graph>)), (void) ) two_graphs_common_spanning_trees ( const Graph& iG, Order iG_map, const Graph& vG, Order vG_map, Func func, Seq inL ) { typedef graph_traits<Graph> GraphTraits; typedef typename GraphTraits::directed_category directed_category; typedef typename GraphTraits::vertex_descriptor vertex_descriptor; typedef typename GraphTraits::edge_descriptor edge_descriptor; typedef typename GraphTraits::edges_size_type edges_size_type; typedef typename GraphTraits::edge_iterator edge_iterator; typedef typename Seq::value_type seq_value_type; typedef typename Seq::size_type seq_size_type; typedef typename Order::value_type order_value_type; typedef typename Order::size_type order_size_type; BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value)); BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>)); BOOST_CONCEPT_ASSERT((Convertible<seq_size_type, edges_size_type>)); BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); BOOST_STATIC_ASSERT((is_same<directed_category, undirected_tag>::value)); if(num_vertices(iG) != num_vertices(vG)) return; if(inL.size() != num_edges(iG) || inL.size() != num_edges(vG)) return; if(iG_map.size() != num_edges(iG) || vG_map.size() != num_edges(vG)) return; typedef bimaps::bimap< bimaps::set_of< int >, bimaps::set_of< order_value_type > > bimap_type; typedef typename bimap_type::value_type bimap_value; bimap_type iG_bimap, vG_bimap; for(order_size_type i = 0; i < iG_map.size(); ++i) iG_bimap.insert(bimap_value(i, iG_map[i])); for(order_size_type i = 0; i < vG_map.size(); ++i) vG_bimap.insert(bimap_value(i, vG_map[i])); edge_iterator current, last; boost::tuples::tie(current, last) = edges(iG); for(; current != last; ++current) if(iG_bimap.right.find(*current) == iG_bimap.right.end()) return; boost::tuples::tie(current, last) = edges(vG); for(; current != last; ++current) if(vG_bimap.right.find(*current) == vG_bimap.right.end()) return; std::stack<edge_descriptor> iG_buf, vG_buf; std::map<vertex_descriptor, edge_descriptor> tree_map; std::map<vertex_descriptor, vertex_descriptor> pred_map; std::map<vertex_descriptor, int> dist_map, low_map; detail::bridges_visitor< associative_property_map< std::map<vertex_descriptor, edge_descriptor> >, associative_property_map< std::map<vertex_descriptor, vertex_descriptor> >, associative_property_map< std::map<vertex_descriptor, int> >, associative_property_map< std::map<vertex_descriptor, int> >, std::stack<edge_descriptor> > iG_vis( associative_property_map< std::map< vertex_descriptor, edge_descriptor> >(tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor> >(pred_map), associative_property_map<std::map< vertex_descriptor, int> >(dist_map), associative_property_map<std::map< vertex_descriptor, int> >(low_map), iG_buf ), vG_vis( associative_property_map< std::map< vertex_descriptor, edge_descriptor> >(tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor> >(pred_map), associative_property_map<std::map< vertex_descriptor, int> >(dist_map), associative_property_map<std::map< vertex_descriptor, int> >(low_map), vG_buf ); std::map<vertex_descriptor, default_color_type> vertex_color; std::map<edge_descriptor, default_color_type> edge_color; undirected_dfs(iG, iG_vis, associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs(vG, vG_vis, associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); while(!iG_buf.empty()) { inL[iG_bimap.right.at(iG_buf.top())] = true; iG_buf.pop(); } while(!vG_buf.empty()) { inL[vG_bimap.right.at(vG_buf.top())] = true; vG_buf.pop(); } std::map<edge_descriptor, bool> iG_inL, vG_inL; associative_property_map< std::map<edge_descriptor, bool> > aiG_inL(iG_inL), avG_inL(vG_inL); for(seq_size_type i = 0; i < inL.size(); ++i) { if(inL[i]) { put(aiG_inL, iG_bimap.left.at(i), true); put(avG_inL, vG_bimap.left.at(i), true); } else { put(aiG_inL, iG_bimap.left.at(i), false); put(avG_inL, vG_bimap.left.at(i), false); } } undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); if(iG_buf.empty() && vG_buf.empty()) { std::map<edge_descriptor, bool> iG_deleted, vG_deleted; associative_property_map< std::map<edge_descriptor, bool> > diG(iG_deleted); associative_property_map< std::map<edge_descriptor, bool> > dvG(vG_deleted); boost::tuples::tie(current, last) = edges(iG); for(; current != last; ++current) put(diG, *current, false); boost::tuples::tie(current, last) = edges(vG); for(; current != last; ++current) put(dvG, *current, false); for(seq_size_type j = 0; j < inL.size(); ++j) { if(!inL[j]) { put(aiG_inL, iG_bimap.left.at(j), true); put(avG_inL, vG_bimap.left.at(j), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map<edge_descriptor, bool> > >(avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), associative_property_map< std::map<vertex_descriptor, default_color_type> >(vertex_color), associative_property_map< std::map<edge_descriptor, default_color_type> >(edge_color) ); if(!iG_buf.empty() || !vG_buf.empty()) { while(!iG_buf.empty()) iG_buf.pop(); while(!vG_buf.empty()) vG_buf.pop(); put(diG, iG_bimap.left.at(j), true); put(dvG, vG_bimap.left.at(j), true); } put(aiG_inL, iG_bimap.left.at(j), false); put(avG_inL, vG_bimap.left.at(j), false); } } int cc = 0; std::map<vertex_descriptor, int> com_map; cc += connected_components( make_filtered_graph(iG, detail::deleted_edge_status<associative_property_map< std::map<edge_descriptor, bool> > >(diG)), associative_property_map<std::map<vertex_descriptor, int> >(com_map) ); cc += connected_components( make_filtered_graph(vG, detail::deleted_edge_status<associative_property_map< std::map<edge_descriptor, bool> > >(dvG)), associative_property_map< std::map<vertex_descriptor, int> >(com_map) ); if(cc != 2) return; // REC detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, associative_property_map< std::map<edge_descriptor, bool> > > (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); } } template < typename Graph, typename Func, typename Seq > BOOST_CONCEPT_REQUIRES( ((IncidenceGraphConcept<Graph>)) ((EdgeListGraphConcept<Graph>)), (void) ) two_graphs_common_spanning_trees ( const Graph& iG, const Graph& vG, Func func, Seq inL ) { typedef graph_traits<Graph> GraphTraits; typedef typename GraphTraits::edge_descriptor edge_descriptor; typedef typename GraphTraits::edge_iterator edge_iterator; std::vector<edge_descriptor> iGO, vGO; edge_iterator curr, last; boost::tuples::tie(curr, last) = edges(iG); for(; curr != last; ++curr) iGO.push_back(*curr); boost::tuples::tie(curr, last) = edges(vG); for(; curr != last; ++curr) vGO.push_back(*curr); two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL); } } // namespace boost #endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP