copy.hpp

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

//
//=======================================================================
// Copyright 1997-2001 University of Notre Dame.
// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
//
// 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.
//=======================================================================
//

/*
  This file implements the following functions:


  template <typename VertexListGraph, typename MutableGraph>
  void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)

  template <typename VertexListGraph, typename MutableGraph, 
    class P, class T, class R>
  void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out, 
                  const bgl_named_params<P, T, R>& params)


  template <typename IncidenceGraph, typename MutableGraph>
  typename graph_traits<MutableGraph>::vertex_descriptor
  copy_component(IncidenceGraph& g_in, 
                 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
                 MutableGraph& g_out)

  template <typename IncidenceGraph, typename MutableGraph, 
           typename P, typename T, typename R>
  typename graph_traits<MutableGraph>::vertex_descriptor
  copy_component(IncidenceGraph& g_in, 
                 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
                 MutableGraph& g_out, 
                 const bgl_named_params<P, T, R>& params)
 */


#ifndef BOOST_GRAPH_COPY_HPP
#define BOOST_GRAPH_COPY_HPP

#include <boost/config.hpp>
#include <vector>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/type_traits/conversion_traits.hpp>

namespace boost {

  namespace detail {

    // Default edge and vertex property copiers

    template <typename Graph1, typename Graph2>
    struct edge_copier {
      edge_copier(const Graph1& g1, Graph2& g2)
        : edge_all_map1(get(edge_all, g1)), 
          edge_all_map2(get(edge_all, g2)) { }

      template <typename Edge1, typename Edge2>
      void operator()(const Edge1& e1, Edge2& e2) const {
        put(edge_all_map2, e2, get(edge_all_map1, e1));
      }
      typename property_map<Graph1, edge_all_t>::const_type edge_all_map1;
      mutable typename property_map<Graph2, edge_all_t>::type edge_all_map2;
    };
    template <typename Graph1, typename Graph2>
    inline edge_copier<Graph1,Graph2>
    make_edge_copier(const Graph1& g1, Graph2& g2)
    {
      return edge_copier<Graph1,Graph2>(g1, g2);
    }

    template <typename Graph1, typename Graph2>
    struct vertex_copier {
      vertex_copier(const Graph1& g1, Graph2& g2)
        : vertex_all_map1(get(vertex_all, g1)), 
          vertex_all_map2(get(vertex_all, g2)) { }

      template <typename Vertex1, typename Vertex2>
      void operator()(const Vertex1& v1, Vertex2& v2) const {
        put(vertex_all_map2, v2, get(vertex_all_map1, v1));
      }
      typename property_map<Graph1, vertex_all_t>::const_type vertex_all_map1;
      mutable typename property_map<Graph2, vertex_all_t>::type
        vertex_all_map2;
    };
    template <typename Graph1, typename Graph2>
    inline vertex_copier<Graph1,Graph2>
    make_vertex_copier(const Graph1& g1, Graph2& g2)
    {
      return vertex_copier<Graph1,Graph2>(g1, g2);
    }

    // Copy all the vertices and edges of graph g_in into graph g_out.
    // The copy_vertex and copy_edge function objects control how vertex
    // and edge properties are copied.

    template <int Version>
    struct copy_graph_impl { };

    template <> struct copy_graph_impl<0>
    {
      template <typename Graph, typename MutableGraph, 
        typename CopyVertex, typename CopyEdge, typename IndexMap,
        typename Orig2CopyVertexIndexMap>
      static void apply(const Graph& g_in, MutableGraph& g_out, 
                        CopyVertex copy_vertex, CopyEdge copy_edge,
                        Orig2CopyVertexIndexMap orig2copy, IndexMap)
      {
        typename graph_traits<Graph>::vertex_iterator vi, vi_end;
        for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
          typename graph_traits<MutableGraph>::vertex_descriptor
            new_v = add_vertex(g_out);
          put(orig2copy, *vi, new_v);
          copy_vertex(*vi, new_v);
        }
        typename graph_traits<Graph>::edge_iterator ei, ei_end;
        for (tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) {
          typename graph_traits<MutableGraph>::edge_descriptor new_e;
          bool inserted;
          tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), 
                                          get(orig2copy, target(*ei, g_in)),
                                          g_out);
          copy_edge(*ei, new_e);
        }
      }
    };

    // for directed graphs
    template <> struct copy_graph_impl<1>
    {
      template <typename Graph, typename MutableGraph, 
        typename CopyVertex, typename CopyEdge, typename IndexMap,
        typename Orig2CopyVertexIndexMap>
      static void apply(const Graph& g_in, MutableGraph& g_out, 
                        CopyVertex copy_vertex, CopyEdge copy_edge,
                        Orig2CopyVertexIndexMap orig2copy, IndexMap)
      {
        typename graph_traits<Graph>::vertex_iterator vi, vi_end;
        for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
          typename graph_traits<MutableGraph>::vertex_descriptor
            new_v = add_vertex(g_out);
          put(orig2copy, *vi, new_v);
          copy_vertex(*vi, new_v);
        }
        for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
          typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
          for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
            typename graph_traits<MutableGraph>::edge_descriptor new_e;
            bool inserted;
            tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), 
                                            get(orig2copy, target(*ei, g_in)),
                                            g_out);
            copy_edge(*ei, new_e);
          }
        }
      }
    };

    // for undirected graphs
    template <> struct copy_graph_impl<2>
    {
      template <typename Graph, typename MutableGraph, 
        typename CopyVertex, typename CopyEdge, typename IndexMap,
        typename Orig2CopyVertexIndexMap>
      static void apply(const Graph& g_in, MutableGraph& g_out, 
                        CopyVertex copy_vertex, CopyEdge copy_edge,
                        Orig2CopyVertexIndexMap orig2copy,
                        IndexMap index_map)
      {
        typedef color_traits<default_color_type> Color;
        std::vector<default_color_type> 
          color(num_vertices(g_in), Color::white());
        typename graph_traits<Graph>::vertex_iterator vi, vi_end;
        for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
          typename graph_traits<MutableGraph>::vertex_descriptor
            new_v = add_vertex(g_out);
          put(orig2copy, *vi, new_v);
          copy_vertex(*vi, new_v);
        }
        for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
          typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
          for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
            typename graph_traits<MutableGraph>::edge_descriptor new_e;
            bool inserted;
            if (color[get(index_map, target(*ei, g_in))] == Color::white()) {
              tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei,g_in)),
                                              get(orig2copy, target(*ei,g_in)),
                                              g_out);
              copy_edge(*ei, new_e);
            }
          }
          color[get(index_map, *vi)] = Color::black();
        }
      }
    };

    template <class Graph>
    struct choose_graph_copy {
      typedef typename Graph::traversal_category Trv;
      typedef typename Graph::directed_category Dr;
      enum { algo = 
             (is_convertible<Trv, vertex_list_graph_tag>::value
              && is_convertible<Trv, edge_list_graph_tag>::value)
             ? 0 : is_convertible<Dr, directed_tag>::value ? 1 : 2 };
      typedef copy_graph_impl<algo> type;
    };

    //-------------------------------------------------------------------------
    struct choose_copier_parameter {
      template <class P, class G1, class G2>
      struct bind_ {
        typedef const P& result_type;