copy.hpp

来自「support vector clustering for vc++」· HPP 代码 · 共 451 行 · 第 1/2 页

        static result_type apply(const P&, const G1& g1, G2& g2) { 
          return result_type(g1, g2);
        }
      };
    };
    template <class Param>
    struct choose_edge_copy {
      typedef choose_copier_parameter type;
    };
    template <>
    struct choose_edge_copy<detail::error_property_not_found> {
      typedef choose_default_edge_copier type;
    };
    template <class Param, class G1, class G2>
    struct choose_edge_copier_helper {
      typedef typename choose_edge_copy<Param>::type Selector;
      typedef typename Selector:: template bind_<Param, G1, G2> Bind;
      typedef Bind type;
      typedef typename Bind::result_type result_type;
    };
    template <typename Param, typename G1, typename G2>
    typename detail::choose_edge_copier_helper<Param,G1,G2>::result_type
    choose_edge_copier(const Param& params, const G1& g_in, G2& g_out)
    {
      typedef typename 
        detail::choose_edge_copier_helper<Param,G1,G2>::type Choice;
      return Choice::apply(params, g_in, g_out);
    }


    struct choose_default_vertex_copier {
      template <class P, class G1, class G2>
      struct bind_ {
        typedef vertex_copier<G1, G2> result_type;
        static result_type apply(const P&, const G1& g1, G2& g2) { 
          return result_type(g1, g2);
        }
      };
    };
    template <class Param>
    struct choose_vertex_copy {
      typedef choose_copier_parameter type;
    };
    template <>
    struct choose_vertex_copy<detail::error_property_not_found> {
      typedef choose_default_vertex_copier type;
    };
    template <class Param, class G1, class G2>
    struct choose_vertex_copier_helper {
      typedef typename choose_vertex_copy<Param>::type Selector;
      typedef typename Selector:: template bind_<Param, G1, G2> Bind;
      typedef Bind type;
      typedef typename Bind::result_type result_type;
    };
    template <typename Param, typename G1, typename G2>
    typename detail::choose_vertex_copier_helper<Param,G1,G2>::result_type
    choose_vertex_copier(const Param& params, const G1& g_in, G2& g_out)
    {
      typedef typename 
        detail::choose_vertex_copier_helper<Param,G1,G2>::type Choice;
      return Choice::apply(params, g_in, g_out);
    }

  } // namespace detail


  template <typename VertexListGraph, typename MutableGraph>
  void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
  {
    if (num_vertices(g_in) == 0)
      return;
    typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
    std::vector<vertex_t> orig2copy(num_vertices(g_in));
    typedef typename detail::choose_graph_copy<VertexListGraph>::type 
      copy_impl;
    copy_impl::apply
      (g_in, g_out, 
       detail::make_vertex_copier(g_in, g_out), 
       detail::make_edge_copier(g_in, g_out), 
       make_iterator_property_map(orig2copy.begin(), 
                                  get(vertex_index, g_in), orig2copy[0]),
       get(vertex_index, g_in)
       );
  }

  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)
  {
    typename std::vector<T>::size_type n;
      n = is_default_param(get_param(params, orig_to_copy_t()))
        ? num_vertices(g_in) : 1;
    if (n == 0)
      return;
    std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor> 
      orig2copy(n);

    typedef typename detail::choose_graph_copy<VertexListGraph>::type 
      copy_impl;
    copy_impl::apply
      (g_in, g_out,
       detail::choose_vertex_copier(get_param(params, vertex_copy_t()), 
                                    g_in, g_out),
       detail::choose_edge_copier(get_param(params, edge_copy_t()), 
                                  g_in, g_out),
       choose_param(get_param(params, orig_to_copy_t()),
                    make_iterator_property_map
                    (orig2copy.begin(), 
                     choose_const_pmap(get_param(params, vertex_index), 
                                 g_in, vertex_index), orig2copy[0])),
       choose_const_pmap(get_param(params, vertex_index), g_in, vertex_index)
       );
  }

  namespace detail {
    
    template <class NewGraph, class Copy2OrigIndexMap, 
      class CopyVertex, class CopyEdge>
    struct graph_copy_visitor : public bfs_visitor<>
    {
      graph_copy_visitor(NewGraph& graph, Copy2OrigIndexMap c,
                         CopyVertex cv, CopyEdge ce)
        : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce) { }

      template <class Vertex, class Graph>
      void examine_vertex(Vertex u, const Graph& g_in) const {
        typename graph_traits<NewGraph>::vertex_descriptor
          new_u = add_vertex(g_out);
        put(orig2copy, u, new_u);
        copy_vertex(u, new_u);
      }
      
      template <class Edge, class Graph>
      void examine_edge(Edge e, const Graph& g_in) const {
        typename graph_traits<NewGraph>::edge_descriptor new_e;
        bool inserted;
        tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)), 
                                        get(orig2copy, target(e, g_in)),
                                        g_out);
        copy_edge(e, new_e);
      }
    private:
      NewGraph& g_out;
      Copy2OrigIndexMap orig2copy;
      CopyVertex copy_vertex;
      CopyEdge copy_edge;
    };

    template <typename Graph, typename MutableGraph, 
              typename CopyVertex, typename CopyEdge, 
              typename Orig2CopyVertexIndexMap, typename Params>
    typename graph_traits<MutableGraph>::vertex_descriptor
    copy_component_impl
      (const Graph& g_in, 
       typename graph_traits<Graph>::vertex_descriptor src,
       MutableGraph& g_out, 
       CopyVertex copy_vertex, CopyEdge copy_edge,
       Orig2CopyVertexIndexMap orig2copy,
       const Params& params)
    {
      graph_copy_visitor<MutableGraph, Orig2CopyVertexIndexMap, 
        CopyVertex, CopyEdge> vis(g_out, orig2copy, copy_vertex, copy_edge);
      breadth_first_search(g_in, src, params.visitor(vis));
      return get(orig2copy, src);
    }

  } // namespace detail
  
  
  // Copy all the vertices and edges of graph g_in that are reachable
  // from the source vertex into graph g_out. Return the vertex
  // in g_out that matches the source vertex of g_in.
  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)
  {
    typename std::vector<T>::size_type n;
      n = is_default_param(get_param(params, orig_to_copy_t()))
        ? num_vertices(g_in) : 1;
    std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor> 
      orig2copy(n);
    
    return detail::copy_component_impl
      (g_in, src, g_out,
       detail::choose_vertex_copier(get_param(params, vertex_copy_t()), 
                                    g_in, g_out),
       detail::choose_edge_copier(get_param(params, edge_copy_t()), 
                                  g_in, g_out),
       choose_param(get_param(params, orig_to_copy_t()),
                    make_iterator_property_map
                    (orig2copy.begin(), 
                     choose_pmap(get_param(params, vertex_index), 
                                 g_in, vertex_index), orig2copy[0])),
       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)
  {
    std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor> 
      orig2copy(num_vertices(g_in));
    
    return detail::copy_component_impl
      (g_in, src, g_out,
       make_vertex_copier(g_in, g_out), 
       make_edge_copier(g_in, g_out), 
       make_iterator_property_map(orig2copy.begin(), 
                                  get(vertex_index, g_in), orig2copy[0]),
       bgl_named_params<char,char>('x') // dummy param object
       );
  }

} // namespace boost

#endif // BOOST_GRAPH_COPY_HPP