path: root/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::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