subgraph.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 862 行 · 第 1/2 页

//=======================================================================
// Copyright 2001 University of Notre Dame.
// Authors: Jeremy G. Siek and Lie-Quan Lee
//
// This file is part of the Boost Graph Library
//
// You should have received a copy of the License Agreement for the
// Boost Graph Library along with the software; see the file LICENSE.
// If not, contact Office of Research, University of Notre Dame, Notre
// Dame, IN 46556.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//=======================================================================

#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(); }

    //  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;
    }

  };

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