williamr@2: //
williamr@2: //=======================================================================
williamr@2: // Copyright 1997-2001 University of Notre Dame.
williamr@2: // Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: //
williamr@2: 
williamr@2: /*
williamr@2:   This file implements the following functions:
williamr@2: 
williamr@2: 
williamr@2:   template <typename VertexListGraph, typename MutableGraph>
williamr@2:   void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
williamr@2: 
williamr@2:   template <typename VertexListGraph, typename MutableGraph, 
williamr@2:     class P, class T, class R>
williamr@2:   void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out, 
williamr@2:                   const bgl_named_params<P, T, R>& params)
williamr@2: 
williamr@2: 
williamr@2:   template <typename IncidenceGraph, typename MutableGraph>
williamr@2:   typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:   copy_component(IncidenceGraph& g_in, 
williamr@2:                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
williamr@2:                  MutableGraph& g_out)
williamr@2: 
williamr@2:   template <typename IncidenceGraph, typename MutableGraph, 
williamr@2:            typename P, typename T, typename R>
williamr@2:   typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:   copy_component(IncidenceGraph& g_in, 
williamr@2:                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
williamr@2:                  MutableGraph& g_out, 
williamr@2:                  const bgl_named_params<P, T, R>& params)
williamr@2:  */
williamr@2: 
williamr@2: 
williamr@2: #ifndef BOOST_GRAPH_COPY_HPP
williamr@2: #define BOOST_GRAPH_COPY_HPP
williamr@2: 
williamr@2: #include <boost/config.hpp>
williamr@2: #include <vector>
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/property_map.hpp>
williamr@2: #include <boost/graph/named_function_params.hpp>
williamr@2: #include <boost/graph/breadth_first_search.hpp>
williamr@2: #include <boost/type_traits/conversion_traits.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   namespace detail {
williamr@2: 
williamr@2:     // Default edge and vertex property copiers
williamr@2: 
williamr@2:     template <typename Graph1, typename Graph2>
williamr@2:     struct edge_copier {
williamr@2:       edge_copier(const Graph1& g1, Graph2& g2)
williamr@2:         : edge_all_map1(get(edge_all, g1)), 
williamr@2:           edge_all_map2(get(edge_all, g2)) { }
williamr@2: 
williamr@2:       template <typename Edge1, typename Edge2>
williamr@2:       void operator()(const Edge1& e1, Edge2& e2) const {
williamr@2:         put(edge_all_map2, e2, get(edge_all_map1, e1));
williamr@2:       }
williamr@2:       typename property_map<Graph1, edge_all_t>::const_type edge_all_map1;
williamr@2:       mutable typename property_map<Graph2, edge_all_t>::type edge_all_map2;
williamr@2:     };
williamr@2:     template <typename Graph1, typename Graph2>
williamr@2:     inline edge_copier<Graph1,Graph2>
williamr@2:     make_edge_copier(const Graph1& g1, Graph2& g2)
williamr@2:     {
williamr@2:       return edge_copier<Graph1,Graph2>(g1, g2);
williamr@2:     }
williamr@2: 
williamr@2:     template <typename Graph1, typename Graph2>
williamr@2:     struct vertex_copier {
williamr@2:       vertex_copier(const Graph1& g1, Graph2& g2)
williamr@2:         : vertex_all_map1(get(vertex_all, g1)), 
williamr@2:           vertex_all_map2(get(vertex_all, g2)) { }
williamr@2: 
williamr@2:       template <typename Vertex1, typename Vertex2>
williamr@2:       void operator()(const Vertex1& v1, Vertex2& v2) const {
williamr@2:         put(vertex_all_map2, v2, get(vertex_all_map1, v1));
williamr@2:       }
williamr@2:       typename property_map<Graph1, vertex_all_t>::const_type vertex_all_map1;
williamr@2:       mutable typename property_map<Graph2, vertex_all_t>::type
williamr@2:         vertex_all_map2;
williamr@2:     };
williamr@2:     template <typename Graph1, typename Graph2>
williamr@2:     inline vertex_copier<Graph1,Graph2>
williamr@2:     make_vertex_copier(const Graph1& g1, Graph2& g2)
williamr@2:     {
williamr@2:       return vertex_copier<Graph1,Graph2>(g1, g2);
williamr@2:     }
williamr@2: 
williamr@2:     // Copy all the vertices and edges of graph g_in into graph g_out.
williamr@2:     // The copy_vertex and copy_edge function objects control how vertex
williamr@2:     // and edge properties are copied.
williamr@2: 
williamr@2:     template <int Version>
williamr@2:     struct copy_graph_impl { };
williamr@2: 
williamr@2:     template <> struct copy_graph_impl<0>
williamr@2:     {
williamr@2:       template <typename Graph, typename MutableGraph, 
williamr@2:         typename CopyVertex, typename CopyEdge, typename IndexMap,
williamr@2:         typename Orig2CopyVertexIndexMap>
williamr@2:       static void apply(const Graph& g_in, MutableGraph& g_out, 
williamr@2:                         CopyVertex copy_vertex, CopyEdge copy_edge,
williamr@2:                         Orig2CopyVertexIndexMap orig2copy, IndexMap)
williamr@2:       {
williamr@2:         typename graph_traits<Graph>::vertex_iterator vi, vi_end;
williamr@2:         for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
williamr@2:           typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:             new_v = add_vertex(g_out);
williamr@2:           put(orig2copy, *vi, new_v);
williamr@2:           copy_vertex(*vi, new_v);
williamr@2:         }
williamr@2:         typename graph_traits<Graph>::edge_iterator ei, ei_end;
williamr@2:         for (tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) {
williamr@2:           typename graph_traits<MutableGraph>::edge_descriptor new_e;
williamr@2:           bool inserted;
williamr@2:           tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), 
williamr@2:                                           get(orig2copy, target(*ei, g_in)),
williamr@2:                                           g_out);
williamr@2:           copy_edge(*ei, new_e);
williamr@2:         }
williamr@2:       }
williamr@2:     };
williamr@2: 
williamr@2:     // for directed graphs
williamr@2:     template <> struct copy_graph_impl<1>
williamr@2:     {
williamr@2:       template <typename Graph, typename MutableGraph, 
williamr@2:         typename CopyVertex, typename CopyEdge, typename IndexMap,
williamr@2:         typename Orig2CopyVertexIndexMap>
williamr@2:       static void apply(const Graph& g_in, MutableGraph& g_out, 
williamr@2:                         CopyVertex copy_vertex, CopyEdge copy_edge,
williamr@2:                         Orig2CopyVertexIndexMap orig2copy, IndexMap)
williamr@2:       {
williamr@2:         typename graph_traits<Graph>::vertex_iterator vi, vi_end;
williamr@2:         for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
williamr@2:           typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:             new_v = add_vertex(g_out);
williamr@2:           put(orig2copy, *vi, new_v);
williamr@2:           copy_vertex(*vi, new_v);
williamr@2:         }
williamr@2:         for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
williamr@2:           typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
williamr@2:           for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
williamr@2:             typename graph_traits<MutableGraph>::edge_descriptor new_e;
williamr@2:             bool inserted;
williamr@2:             tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), 
williamr@2:                                             get(orig2copy, target(*ei, g_in)),
williamr@2:                                             g_out);
williamr@2:             copy_edge(*ei, new_e);
williamr@2:           }
williamr@2:         }
williamr@2:       }
williamr@2:     };
williamr@2: 
williamr@2:     // for undirected graphs
williamr@2:     template <> struct copy_graph_impl<2>
williamr@2:     {
williamr@2:       template <typename Graph, typename MutableGraph, 
williamr@2:         typename CopyVertex, typename CopyEdge, typename IndexMap,
williamr@2:         typename Orig2CopyVertexIndexMap>
williamr@2:       static void apply(const Graph& g_in, MutableGraph& g_out, 
williamr@2:                         CopyVertex copy_vertex, CopyEdge copy_edge,
williamr@2:                         Orig2CopyVertexIndexMap orig2copy,
williamr@2:                         IndexMap index_map)
williamr@2:       {
williamr@2:         typedef color_traits<default_color_type> Color;
williamr@2:         std::vector<default_color_type> 
williamr@2:           color(num_vertices(g_in), Color::white());
williamr@2:         typename graph_traits<Graph>::vertex_iterator vi, vi_end;
williamr@2:         for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
williamr@2:           typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:             new_v = add_vertex(g_out);
williamr@2:           put(orig2copy, *vi, new_v);
williamr@2:           copy_vertex(*vi, new_v);
williamr@2:         }
williamr@2:         for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
williamr@2:           typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
williamr@2:           for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
williamr@2:             typename graph_traits<MutableGraph>::edge_descriptor new_e;
williamr@2:             bool inserted;
williamr@2:             if (color[get(index_map, target(*ei, g_in))] == Color::white()) {
williamr@2:               tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei,g_in)),
williamr@2:                                               get(orig2copy, target(*ei,g_in)),
williamr@2:                                               g_out);
williamr@2:               copy_edge(*ei, new_e);
williamr@2:             }
williamr@2:           }
williamr@2:           color[get(index_map, *vi)] = Color::black();
williamr@2:         }
williamr@2:       }
williamr@2:     };
williamr@2: 
williamr@2:     template <class Graph>
williamr@2:     struct choose_graph_copy {
williamr@2:       typedef typename Graph::traversal_category Trv;
williamr@2:       typedef typename Graph::directed_category Dr;
williamr@2:       enum { algo = 
williamr@2:              (is_convertible<Trv, vertex_list_graph_tag>::value
williamr@2:               && is_convertible<Trv, edge_list_graph_tag>::value)
williamr@2:              ? 0 : is_convertible<Dr, directed_tag>::value ? 1 : 2 };
williamr@2:       typedef copy_graph_impl<algo> type;
williamr@2:     };
williamr@2: 
williamr@2:     //-------------------------------------------------------------------------
williamr@2:     struct choose_copier_parameter {
williamr@2:       template <class P, class G1, class G2>
williamr@2:       struct bind_ {
williamr@2:         typedef const P& result_type;
williamr@2:         static result_type apply(const P& p, const G1&, G2&)
williamr@2:         { return p; }
williamr@2:       };
williamr@2:     };
williamr@2:     struct choose_default_edge_copier {
williamr@2:       template <class P, class G1, class G2>
williamr@2:       struct bind_ {
williamr@2:         typedef edge_copier<G1, G2> result_type;
williamr@2:         static result_type apply(const P&, const G1& g1, G2& g2) { 
williamr@2:           return result_type(g1, g2);
williamr@2:         }
williamr@2:       };
williamr@2:     };
williamr@2:     template <class Param>
williamr@2:     struct choose_edge_copy {
williamr@2:       typedef choose_copier_parameter type;
williamr@2:     };
williamr@2:     template <>
williamr@2:     struct choose_edge_copy<detail::error_property_not_found> {
williamr@2:       typedef choose_default_edge_copier type;
williamr@2:     };
williamr@2:     template <class Param, class G1, class G2>
williamr@2:     struct choose_edge_copier_helper {
williamr@2:       typedef typename choose_edge_copy<Param>::type Selector;
williamr@2:       typedef typename Selector:: template bind_<Param, G1, G2> Bind;
williamr@2:       typedef Bind type;
williamr@2:       typedef typename Bind::result_type result_type;
williamr@2:     };
williamr@2:     template <typename Param, typename G1, typename G2>
williamr@2:     typename detail::choose_edge_copier_helper<Param,G1,G2>::result_type
williamr@2:     choose_edge_copier(const Param& params, const G1& g_in, G2& g_out)
williamr@2:     {
williamr@2:       typedef typename 
williamr@2:         detail::choose_edge_copier_helper<Param,G1,G2>::type Choice;
williamr@2:       return Choice::apply(params, g_in, g_out);
williamr@2:     }
williamr@2: 
williamr@2: 
williamr@2:     struct choose_default_vertex_copier {
williamr@2:       template <class P, class G1, class G2>
williamr@2:       struct bind_ {
williamr@2:         typedef vertex_copier<G1, G2> result_type;
williamr@2:         static result_type apply(const P&, const G1& g1, G2& g2) { 
williamr@2:           return result_type(g1, g2);
williamr@2:         }
williamr@2:       };
williamr@2:     };
williamr@2:     template <class Param>
williamr@2:     struct choose_vertex_copy {
williamr@2:       typedef choose_copier_parameter type;
williamr@2:     };
williamr@2:     template <>
williamr@2:     struct choose_vertex_copy<detail::error_property_not_found> {
williamr@2:       typedef choose_default_vertex_copier type;
williamr@2:     };
williamr@2:     template <class Param, class G1, class G2>
williamr@2:     struct choose_vertex_copier_helper {
williamr@2:       typedef typename choose_vertex_copy<Param>::type Selector;
williamr@2:       typedef typename Selector:: template bind_<Param, G1, G2> Bind;
williamr@2:       typedef Bind type;
williamr@2:       typedef typename Bind::result_type result_type;
williamr@2:     };
williamr@2:     template <typename Param, typename G1, typename G2>
williamr@2:     typename detail::choose_vertex_copier_helper<Param,G1,G2>::result_type
williamr@2:     choose_vertex_copier(const Param& params, const G1& g_in, G2& g_out)
williamr@2:     {
williamr@2:       typedef typename 
williamr@2:         detail::choose_vertex_copier_helper<Param,G1,G2>::type Choice;
williamr@2:       return Choice::apply(params, g_in, g_out);
williamr@2:     }
williamr@2: 
williamr@2:   } // namespace detail
williamr@2: 
williamr@2: 
williamr@2:   template <typename VertexListGraph, typename MutableGraph>
williamr@2:   void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
williamr@2:   {
williamr@2:     if (num_vertices(g_in) == 0)
williamr@2:       return;
williamr@2:     typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
williamr@2:     std::vector<vertex_t> orig2copy(num_vertices(g_in));
williamr@2:     typedef typename detail::choose_graph_copy<VertexListGraph>::type 
williamr@2:       copy_impl;
williamr@2:     copy_impl::apply
williamr@2:       (g_in, g_out, 
williamr@2:        detail::make_vertex_copier(g_in, g_out), 
williamr@2:        detail::make_edge_copier(g_in, g_out), 
williamr@2:        make_iterator_property_map(orig2copy.begin(), 
williamr@2:                                   get(vertex_index, g_in), orig2copy[0]),
williamr@2:        get(vertex_index, g_in)
williamr@2:        );
williamr@2:   }
williamr@2: 
williamr@2:   template <typename VertexListGraph, typename MutableGraph, 
williamr@2:     class P, class T, class R>
williamr@2:   void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out, 
williamr@2:                   const bgl_named_params<P, T, R>& params)
williamr@2:   {
williamr@2:     typename std::vector<T>::size_type n;
williamr@2:       n = is_default_param(get_param(params, orig_to_copy_t()))
williamr@2:         ? num_vertices(g_in) : 1;
williamr@2:     if (n == 0)
williamr@2:       return;
williamr@2:     std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor> 
williamr@2:       orig2copy(n);
williamr@2: 
williamr@2:     typedef typename detail::choose_graph_copy<VertexListGraph>::type 
williamr@2:       copy_impl;
williamr@2:     copy_impl::apply
williamr@2:       (g_in, g_out,
williamr@2:        detail::choose_vertex_copier(get_param(params, vertex_copy_t()), 
williamr@2:                                     g_in, g_out),
williamr@2:        detail::choose_edge_copier(get_param(params, edge_copy_t()), 
williamr@2:                                   g_in, g_out),
williamr@2:        choose_param(get_param(params, orig_to_copy_t()),
williamr@2:                     make_iterator_property_map
williamr@2:                     (orig2copy.begin(), 
williamr@2:                      choose_const_pmap(get_param(params, vertex_index), 
williamr@2:                                  g_in, vertex_index), orig2copy[0])),
williamr@2:        choose_const_pmap(get_param(params, vertex_index), g_in, vertex_index)
williamr@2:        );
williamr@2:   }
williamr@2: 
williamr@2:   namespace detail {
williamr@2:     
williamr@2:     template <class NewGraph, class Copy2OrigIndexMap, 
williamr@2:       class CopyVertex, class CopyEdge>
williamr@2:     struct graph_copy_visitor : public bfs_visitor<>
williamr@2:     {
williamr@2:       graph_copy_visitor(NewGraph& graph, Copy2OrigIndexMap c,
williamr@2:                          CopyVertex cv, CopyEdge ce)
williamr@2:         : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce) { }
williamr@2: 
williamr@2:       template <class Vertex, class Graph>
williamr@2:       void examine_vertex(Vertex u, const Graph& g_in) const {
williamr@2:         typename graph_traits<NewGraph>::vertex_descriptor
williamr@2:           new_u = add_vertex(g_out);
williamr@2:         put(orig2copy, u, new_u);
williamr@2:         copy_vertex(u, new_u);
williamr@2:       }
williamr@2:       
williamr@2:       template <class Edge, class Graph>
williamr@2:       void examine_edge(Edge e, const Graph& g_in) const {
williamr@2:         typename graph_traits<NewGraph>::edge_descriptor new_e;
williamr@2:         bool inserted;
williamr@2:         tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)), 
williamr@2:                                         get(orig2copy, target(e, g_in)),
williamr@2:                                         g_out);
williamr@2:         copy_edge(e, new_e);
williamr@2:       }
williamr@2:     private:
williamr@2:       NewGraph& g_out;
williamr@2:       Copy2OrigIndexMap orig2copy;
williamr@2:       CopyVertex copy_vertex;
williamr@2:       CopyEdge copy_edge;
williamr@2:     };
williamr@2: 
williamr@2:     template <typename Graph, typename MutableGraph, 
williamr@2:               typename CopyVertex, typename CopyEdge, 
williamr@2:               typename Orig2CopyVertexIndexMap, typename Params>
williamr@2:     typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:     copy_component_impl
williamr@2:       (const Graph& g_in, 
williamr@2:        typename graph_traits<Graph>::vertex_descriptor src,
williamr@2:        MutableGraph& g_out, 
williamr@2:        CopyVertex copy_vertex, CopyEdge copy_edge,
williamr@2:        Orig2CopyVertexIndexMap orig2copy,
williamr@2:        const Params& params)
williamr@2:     {
williamr@2:       graph_copy_visitor<MutableGraph, Orig2CopyVertexIndexMap, 
williamr@2:         CopyVertex, CopyEdge> vis(g_out, orig2copy, copy_vertex, copy_edge);
williamr@2:       breadth_first_search(g_in, src, params.visitor(vis));
williamr@2:       return get(orig2copy, src);
williamr@2:     }
williamr@2: 
williamr@2:   } // namespace detail
williamr@2:   
williamr@2:   
williamr@2:   // Copy all the vertices and edges of graph g_in that are reachable
williamr@2:   // from the source vertex into graph g_out. Return the vertex
williamr@2:   // in g_out that matches the source vertex of g_in.
williamr@2:   template <typename IncidenceGraph, typename MutableGraph, 
williamr@2:            typename P, typename T, typename R>
williamr@2:   typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:   copy_component(IncidenceGraph& g_in, 
williamr@2:                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
williamr@2:                  MutableGraph& g_out, 
williamr@2:                  const bgl_named_params<P, T, R>& params)
williamr@2:   {
williamr@2:     typename std::vector<T>::size_type n;
williamr@2:       n = is_default_param(get_param(params, orig_to_copy_t()))
williamr@2:         ? num_vertices(g_in) : 1;
williamr@2:     std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor> 
williamr@2:       orig2copy(n);
williamr@2:     
williamr@2:     return detail::copy_component_impl
williamr@2:       (g_in, src, g_out,
williamr@2:        detail::choose_vertex_copier(get_param(params, vertex_copy_t()), 
williamr@2:                                     g_in, g_out),
williamr@2:        detail::choose_edge_copier(get_param(params, edge_copy_t()), 
williamr@2:                                   g_in, g_out),
williamr@2:        choose_param(get_param(params, orig_to_copy_t()),
williamr@2:                     make_iterator_property_map
williamr@2:                     (orig2copy.begin(), 
williamr@2:                      choose_pmap(get_param(params, vertex_index), 
williamr@2:                                  g_in, vertex_index), orig2copy[0])),
williamr@2:        params
williamr@2:        );
williamr@2:   }
williamr@2: 
williamr@2:   template <typename IncidenceGraph, typename MutableGraph>
williamr@2:   typename graph_traits<MutableGraph>::vertex_descriptor
williamr@2:   copy_component(IncidenceGraph& g_in, 
williamr@2:                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
williamr@2:                  MutableGraph& g_out)
williamr@2:   {
williamr@2:     std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor> 
williamr@2:       orig2copy(num_vertices(g_in));
williamr@2:     
williamr@2:     return detail::copy_component_impl
williamr@2:       (g_in, src, g_out,
williamr@2:        make_vertex_copier(g_in, g_out), 
williamr@2:        make_edge_copier(g_in, g_out), 
williamr@2:        make_iterator_property_map(orig2copy.begin(), 
williamr@2:                                   get(vertex_index, g_in), orig2copy[0]),
williamr@2:        bgl_named_params<char,char>('x') // dummy param object
williamr@2:        );
williamr@2:   }
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_COPY_HPP