//=======================================================================

// Copyright 2001 University of Notre Dame.

// Authors: Jeremy G. Siek and Lie-Quan Lee

//

// 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)

//=======================================================================

#ifndef BOOST_SUBGRAPH_HPP

#define BOOST_SUBGRAPH_HPP

// UNDER CONSTRUCTION

#include <boost/config.hpp>

#include <list>

#include <vector>

#include <map>

#include <cassert>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/properties.hpp>

#include <boost/iterator/indirect_iterator.hpp>

#include <boost/static_assert.hpp>

#include <boost/type_traits/is_same.hpp>

namespace boost {

  struct subgraph_tag { };

  // Invariants of an induced subgraph:

  //   - If vertex u is in subgraph g, then u must be in g.parent().

  //   - If edge e is in subgraph g, then e must be in g.parent().

  //   - If edge e=(u,v) is in the root graph, then edge e

  //     is also in any subgraph that contains both vertex u and v.

  // The Graph template parameter must have a vertex_index

  // and edge_index internal property. It is assumed that

  // the vertex indices are assigned automatically by the

  // graph during a call to add_vertex(). It is not

  // assumed that the edge vertices are assigned automatically,

  // they are explicitly assigned here.

  template <typename Graph>

  class subgraph {

    typedef graph_traits<Graph> Traits;

    typedef std::list<subgraph<Graph>*> ChildrenList;

  public:

    // Graph requirements

    typedef typename Traits::vertex_descriptor         vertex_descriptor;

    typedef typename Traits::edge_descriptor           edge_descriptor;

    typedef typename Traits::directed_category         directed_category;

    typedef typename Traits::edge_parallel_category    edge_parallel_category;

    typedef typename Traits::traversal_category        traversal_category;

    static vertex_descriptor null_vertex()

    {

      return Traits::null_vertex();

    }

    // IncidenceGraph requirements

    typedef typename Traits::out_edge_iterator         out_edge_iterator;

    typedef typename Traits::degree_size_type          degree_size_type;

    // AdjacencyGraph requirements

    typedef typename Traits::adjacency_iterator        adjacency_iterator;

    // VertexListGraph requirements

    typedef typename Traits::vertex_iterator           vertex_iterator;

    typedef typename Traits::vertices_size_type        vertices_size_type;

    // EdgeListGraph requirements

    typedef typename Traits::edge_iterator             edge_iterator;

    typedef typename Traits::edges_size_type           edges_size_type;

    typedef typename Traits::in_edge_iterator          in_edge_iterator;

    typedef typename Graph::edge_property_type         edge_property_type;

    typedef typename Graph::vertex_property_type       vertex_property_type;

    typedef subgraph_tag                               graph_tag;

    typedef Graph                                      graph_type;

    typedef typename Graph::graph_property_type        graph_property_type;

    // Constructors

    // Create the main graph, the root of the subgraph tree

    subgraph()

      : m_parent(0), m_edge_counter(0)

    { }

    subgraph(const graph_property_type& p)

      : m_graph(p), m_parent(0), m_edge_counter(0)

    { }

    subgraph(vertices_size_type n,

             const graph_property_type& p = graph_property_type())

      : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)

    {

      typename Graph::vertex_iterator v, v_end;

      vertices_size_type i = 0;

      for (tie(v, v_end) = vertices(m_graph); v != v_end; ++v)

        m_global_vertex[i++] = *v;

    }

    // copy constructor

    subgraph(const subgraph& x)

      : m_graph(x.m_graph), m_parent(x.m_parent),

      m_edge_counter(x.m_edge_counter),

      m_global_vertex(x.m_global_vertex),

      m_global_edge(x.m_global_edge)

    {

      // Do a deep copy

      for (typename ChildrenList::const_iterator i = x.m_children.begin();

           i != x.m_children.end(); ++i)

        m_children.push_back(new subgraph<Graph>( **i ));

    }

    ~subgraph() {

      for (typename ChildrenList::iterator i = m_children.begin();

           i != m_children.end(); ++i)

        delete *i;

    }

    // Create a subgraph

    subgraph<Graph>& create_subgraph() {

      m_children.push_back(new subgraph<Graph>());

      m_children.back()->m_parent = this;

      return *m_children.back();

    }

    // Create a subgraph with the specified vertex set.

    template <typename VertexIterator>

    subgraph<Graph>& create_subgraph(VertexIterator first,

                                     VertexIterator last)

    {

      m_children.push_back(new subgraph<Graph>());

      m_children.back()->m_parent = this;

      for (; first != last; ++first)

        add_vertex(*first, *m_children.back());

      return *m_children.back();

    }

    // local <-> global descriptor conversion functions

    vertex_descriptor local_to_global(vertex_descriptor u_local) const

    {

      return m_global_vertex[u_local];

    }

    vertex_descriptor global_to_local(vertex_descriptor u_global) const

    {

      vertex_descriptor u_local; bool in_subgraph;

      tie(u_local, in_subgraph) = this->find_vertex(u_global);

      assert(in_subgraph == true);

      return u_local;

    }

    edge_descriptor local_to_global(edge_descriptor e_local) const

    {

      return m_global_edge[get(get(edge_index, m_graph), e_local)];

    }

    edge_descriptor global_to_local(edge_descriptor e_global) const

    {

      return

        (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second;

    }

    // Is vertex u (of the root graph) contained in this subgraph?

    // If so, return the matching local vertex.

    std::pair<vertex_descriptor, bool>

    find_vertex(vertex_descriptor u_global) const

    {

      typename std::map<vertex_descriptor, vertex_descriptor>::const_iterator

        i = m_local_vertex.find(u_global);

      bool valid = i != m_local_vertex.end();

      return std::make_pair((valid ? (*i).second : null_vertex()), valid);

    }

    // Return the parent graph.

    subgraph& parent() { return *m_parent; }

    const subgraph& parent() const { return *m_parent; }

    bool is_root() const { return m_parent == 0; }

    // Return the root graph of the subgraph tree.

    subgraph& root() {

      if (this->is_root())

        return *this;

      else

        return m_parent->root();

    }

    const subgraph& root() const {

      if (this->is_root())

        return *this;

      else

        return m_parent->root();

    }

    // Return the children subgraphs of this graph/subgraph.

    // Use a list of pointers because the VC++ std::list doesn't like

    // storing incomplete type.

    typedef indirect_iterator<

        typename ChildrenList::const_iterator

      , subgraph<Graph>

      , std::bidirectional_iterator_tag

    >

    children_iterator;

    typedef indirect_iterator<

        typename ChildrenList::const_iterator

      , subgraph<Graph> const

      , std::bidirectional_iterator_tag

    >

    const_children_iterator;

    std::pair<const_children_iterator, const_children_iterator>

    children() const

    {

      return std::make_pair(const_children_iterator(m_children.begin()),

                            const_children_iterator(m_children.end()));

    }

    std::pair<children_iterator, children_iterator>

    children()

    {

      return std::make_pair(children_iterator(m_children.begin()),

                            children_iterator(m_children.end()));

    }

    std::size_t num_children() const { return m_children.size(); }

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    // Bundled properties support

    template<typename Descriptor>

    typename graph::detail::bundled_result<Graph, Descriptor>::type&

    operator[](Descriptor x)

    { 

      if (m_parent == 0) return m_graph[x];

      else return root().m_graph[local_to_global(x)];

    }

    template<typename Descriptor>

    typename graph::detail::bundled_result<Graph, Descriptor>::type const&

    operator[](Descriptor x) const

    { 

      if (m_parent == 0) return m_graph[x];

      else return root().m_graph[local_to_global(x)];

    }

#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    //  private:

    typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap;

    typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type;

    BOOST_STATIC_ASSERT((!is_same<edge_index_type, 

                        boost::detail::error_property_not_found>::value));

    Graph m_graph;

    subgraph<Graph>* m_parent;

    edge_index_type m_edge_counter; // for generating unique edge indices

    ChildrenList m_children;

    std::vector<vertex_descriptor> m_global_vertex; // local -> global

    std::map<vertex_descriptor, vertex_descriptor> m_local_vertex;  // global -> local

    std::vector<edge_descriptor> m_global_edge;              // local -> global

    std::map<edge_index_type, edge_descriptor> m_local_edge; // global -> local

    edge_descriptor

    local_add_edge(vertex_descriptor u_local, vertex_descriptor v_local,

                   edge_descriptor e_global)

    {

      edge_descriptor e_local;

      bool inserted;

      tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);

      put(edge_index, m_graph, e_local, m_edge_counter++);

      m_global_edge.push_back(e_global);

      m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;

      return e_local;

    }

  };

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

  template<typename Graph>

  struct vertex_bundle_type<subgraph<Graph> > : vertex_bundle_type<Graph> { };

  template<typename Graph>

  struct edge_bundle_type<subgraph<Graph> > : edge_bundle_type<Graph> { };

#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

  //===========================================================================

  // Functions special to the Subgraph Class

  template <typename G>

  typename subgraph<G>::vertex_descriptor

  add_vertex(typename subgraph<G>::vertex_descriptor u_global,

             subgraph<G>& g)

  {

    assert(!g.is_root());

    typename subgraph<G>::vertex_descriptor u_local, v_global, uu_global;

    typename subgraph<G>::edge_descriptor e_global;

    u_local = add_vertex(g.m_graph);

    g.m_global_vertex.push_back(u_global);

    g.m_local_vertex[u_global] = u_local;

    subgraph<G>& r = g.root();

    // remember edge global and local maps

    {

      typename subgraph<G>::out_edge_iterator ei, ei_end;

      for (tie(ei, ei_end) = out_edges(u_global, r);

           ei != ei_end; ++ei) {

        e_global = *ei;

        v_global = target(e_global, r);

        if (g.find_vertex(v_global).second == true)

          g.local_add_edge(u_local, g.global_to_local(v_global), e_global);

      }

    }

    if (is_directed(g)) { // not necessary for undirected graph

      typename subgraph<G>::vertex_iterator vi, vi_end;

      typename subgraph<G>::out_edge_iterator ei, ei_end;

      for (tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {

        v_global = *vi;

        if (g.find_vertex(v_global).second)

          for (tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {

            e_global = *ei;

            uu_global = target(e_global, r);

            if (uu_global == u_global && g.find_vertex(v_global).second)

              g.local_add_edge(g.global_to_local(v_global), u_local, e_global);

          }

      }

    }

    return u_local;

  }

  //===========================================================================

  // Functions required by the IncidenceGraph concept

  template <typename G>

  std::pair<typename graph_traits<G>::out_edge_iterator,

            typename graph_traits<G>::out_edge_iterator>

  out_edges(typename graph_traits<G>::vertex_descriptor u_local,

            const subgraph<G>& g)

    { return out_edges(u_local, g.m_graph); }

  template <typename G>

  typename graph_traits<G>::degree_size_type

  out_degree(typename graph_traits<G>::vertex_descriptor u_local,

             const subgraph<G>& g)

    { return out_degree(u_local, g.m_graph); }

  template <typename G>

  typename graph_traits<G>::vertex_descriptor

  source(typename graph_traits<G>::edge_descriptor e_local,

         const subgraph<G>& g)

    { return source(e_local, g.m_graph); }

  template <typename G>

  typename graph_traits<G>::vertex_descriptor

  target(typename graph_traits<G>::edge_descriptor e_local,

         const subgraph<G>& g)

    { return target(e_local, g.m_graph); }

  //===========================================================================

  // Functions required by the BidirectionalGraph concept

  template <typename G>

  std::pair<typename graph_traits<G>::in_edge_iterator,

            typename graph_traits<G>::in_edge_iterator>

  in_edges(typename graph_traits<G>::vertex_descriptor u_local,

            const subgraph<G>& g)

    { return in_edges(u_local, g.m_graph); }

  template <typename G>

  typename graph_traits<G>::degree_size_type

  in_degree(typename graph_traits<G>::vertex_descriptor u_local,

             const subgraph<G>& g)

    { return in_degree(u_local, g.m_graph); }

  template <typename G>

  typename graph_traits<G>::degree_size_type

  degree(typename graph_traits<G>::vertex_descriptor u_local,

             const subgraph<G>& g)

    { return degree(u_local, g.m_graph); }

  //===========================================================================

  // Functions required by the AdjacencyGraph concept

  template <typename G>

  std::pair<typename subgraph<G>::adjacency_iterator,

            typename subgraph<G>::adjacency_iterator>

  adjacent_vertices(typename subgraph<G>::vertex_descriptor u_local,

                    const subgraph<G>& g)

    { return adjacent_vertices(u_local, g.m_graph); }

  //===========================================================================

  // Functions required by the VertexListGraph concept

  template <typename G>

  std::pair<typename subgraph<G>::vertex_iterator,

            typename subgraph<G>::vertex_iterator>

  vertices(const subgraph<G>& g)

    { return vertices(g.m_graph); }

  template <typename G>

  typename subgraph<G>::vertices_size_type

  num_vertices(const subgraph<G>& g)

    { return num_vertices(g.m_graph); }

  //===========================================================================

  // Functions required by the EdgeListGraph concept

  template <typename G>

  std::pair<typename subgraph<G>::edge_iterator,

            typename subgraph<G>::edge_iterator>

  edges(const subgraph<G>& g)

    { return edges(g.m_graph); }

  template <typename G>

  typename subgraph<G>::edges_size_type

  num_edges(const subgraph<G>& g)

    { return num_edges(g.m_graph); }

  //===========================================================================

  // Functions required by the AdjacencyMatrix concept

  template <typename G>

  std::pair<typename subgraph<G>::edge_descriptor, bool>

  edge(typename subgraph<G>::vertex_descriptor u_local,

       typename subgraph<G>::vertex_descriptor v_local,

       const subgraph<G>& g)

  {

    return edge(u_local, v_local, g.m_graph);

  }

  //===========================================================================

  // Functions required by the MutableGraph concept

  namespace detail {

    template <typename Vertex, typename Edge, typename Graph>

    void add_edge_recur_down

    (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g);

    template <typename Vertex, typename Edge, typename Children, typename G>

    void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,

                           Children& c, subgraph<G>* orig)

    {

      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)

        if ((*i)->find_vertex(u_global).second

            && (*i)->find_vertex(v_global).second)

          add_edge_recur_down(u_global, v_global, e_global, **i, orig);

    }

    template <typename Vertex, typename Edge, typename Graph>

    void add_edge_recur_down

      (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g,

       subgraph<Graph>* orig)

    {

      if (&g != orig ) {

        // add local edge only if u_global and v_global are in subgraph g

        Vertex u_local, v_local;

        bool u_in_subgraph, v_in_subgraph;

        tie(u_local, u_in_subgraph) = g.find_vertex(u_global);

        tie(v_local, v_in_subgraph) = g.find_vertex(v_global);

        if (u_in_subgraph && v_in_subgraph)

          g.local_add_edge(u_local, v_local, e_global);

      }

      children_add_edge(u_global, v_global, e_global, g.m_children, orig);

    }

    template <typename Vertex, typename Graph>

    std::pair<typename subgraph<Graph>::edge_descriptor, bool>

    add_edge_recur_up(Vertex u_global, Vertex v_global,

                      const typename Graph::edge_property_type& ep,

                      subgraph<Graph>& g, subgraph<Graph>* orig)

    {

      if (g.is_root()) {

        typename subgraph<Graph>::edge_descriptor e_global;

        bool inserted;

        tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);

        put(edge_index, g.m_graph, e_global, g.m_edge_counter++);

        g.m_global_edge.push_back(e_global);

        children_add_edge(u_global, v_global, e_global, g.m_children, orig);

        return std::make_pair(e_global, inserted);

      } else

        return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);

    }

  } // namespace detail

  // Add an edge to the subgraph g, specified by the local vertex

  // descriptors u and v. In addition, the edge will be added to any

  // other subgraphs which contain vertex descriptors u and v.

  template <typename G>

  std::pair<typename subgraph<G>::edge_descriptor, bool>

  add_edge(typename subgraph<G>::vertex_descriptor u_local,

           typename subgraph<G>::vertex_descriptor v_local,

           const typename G::edge_property_type& ep,

           subgraph<G>& g)

  {

    if (g.is_root()) // u_local and v_local are really global

      return detail::add_edge_recur_up(u_local, v_local, ep, g, &g);

    else {

      typename subgraph<G>::edge_descriptor e_local, e_global;

      bool inserted;

      tie(e_global, inserted) = detail::add_edge_recur_up

        (g.local_to_global(u_local), g.local_to_global(v_local), ep, g, &g);

      e_local = g.local_add_edge(u_local, v_local, e_global);

      return std::make_pair(e_local, inserted);

    }

  }

  template <typename G>

  std::pair<typename subgraph<G>::edge_descriptor, bool>

  add_edge(typename subgraph<G>::vertex_descriptor u,

           typename subgraph<G>::vertex_descriptor v,

           subgraph<G>& g)

  {

    typename G::edge_property_type ep;

    return add_edge(u, v, ep, g);

  }

  namespace detail {

    //-------------------------------------------------------------------------

    // implementation of remove_edge(u,v,g)

    template <typename Vertex, typename Graph>