//

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

 // Copyright 1997-2001 University of Notre Dame.

 // Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine

 //

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

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

 //

 /*

   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;

         static result_type apply(const P& p, const G1&, G2&)

         { return p; }

       };

     };

     struct choose_default_edge_copier {

       template <class P, class G1, class G2>

       struct bind_ {

         typedef edge_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_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