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