diff options
Diffstat (limited to 'boost/graph/two_graphs_common_spanning_trees.hpp')
| -rw-r--r-- | boost/graph/two_graphs_common_spanning_trees.hpp | 870 |
1 files changed, 870 insertions, 0 deletions
diff --git a/boost/graph/two_graphs_common_spanning_trees.hpp b/boost/graph/two_graphs_common_spanning_trees.hpp new file mode 100644 index 0000000000..86d57ece07 --- /dev/null +++ b/boost/graph/two_graphs_common_spanning_trees.hpp @@ -0,0 +1,870 @@ +// 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::const_iterator seq_const_iterator; + typedef typename Seq::difference_type seq_diff_type; + typedef typename Seq::value_type seq_value_type; + typedef typename Seq::size_type seq_size_type; + typedef typename Seq::iterator seq_iterator; + + typedef typename Order::const_iterator order_const_iterator; + typedef typename Order::difference_type order_diff_type; + typedef typename Order::value_type order_value_type; + typedef typename Order::size_type order_size_type; + typedef typename Order::iterator order_iterator; + + 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::edges_size_type edges_size_type; + 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 |