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 williamr@2: void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out) williamr@2: williamr@2: template williamr@2: void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out, williamr@2: const bgl_named_params& params) williamr@2: williamr@2: williamr@2: template williamr@2: typename graph_traits::vertex_descriptor williamr@2: copy_component(IncidenceGraph& g_in, williamr@2: typename graph_traits::vertex_descriptor src, williamr@2: MutableGraph& g_out) williamr@2: williamr@2: template williamr@2: typename graph_traits::vertex_descriptor williamr@2: copy_component(IncidenceGraph& g_in, williamr@2: typename graph_traits::vertex_descriptor src, williamr@2: MutableGraph& g_out, williamr@2: const bgl_named_params& 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 williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include 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 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 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::const_type edge_all_map1; williamr@2: mutable typename property_map::type edge_all_map2; williamr@2: }; williamr@2: template williamr@2: inline edge_copier williamr@2: make_edge_copier(const Graph1& g1, Graph2& g2) williamr@2: { williamr@2: return edge_copier(g1, g2); williamr@2: } williamr@2: williamr@2: template 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 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::const_type vertex_all_map1; williamr@2: mutable typename property_map::type williamr@2: vertex_all_map2; williamr@2: }; williamr@2: template williamr@2: inline vertex_copier williamr@2: make_vertex_copier(const Graph1& g1, Graph2& g2) williamr@2: { williamr@2: return vertex_copier(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 williamr@2: struct copy_graph_impl { }; williamr@2: williamr@2: template <> struct copy_graph_impl<0> williamr@2: { williamr@2: template 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::vertex_iterator vi, vi_end; williamr@2: for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { williamr@2: typename graph_traits::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::edge_iterator ei, ei_end; williamr@2: for (tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) { williamr@2: typename graph_traits::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 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::vertex_iterator vi, vi_end; williamr@2: for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { williamr@2: typename graph_traits::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::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::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 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 Color; williamr@2: std::vector williamr@2: color(num_vertices(g_in), Color::white()); williamr@2: typename graph_traits::vertex_iterator vi, vi_end; williamr@2: for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { williamr@2: typename graph_traits::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::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::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 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::value williamr@2: && is_convertible::value) williamr@2: ? 0 : is_convertible::value ? 1 : 2 }; williamr@2: typedef copy_graph_impl type; williamr@2: }; williamr@2: williamr@2: //------------------------------------------------------------------------- williamr@2: struct choose_copier_parameter { williamr@2: template 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 williamr@2: struct bind_ { williamr@2: typedef edge_copier 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 williamr@2: struct choose_edge_copy { williamr@2: typedef choose_copier_parameter type; williamr@2: }; williamr@2: template <> williamr@2: struct choose_edge_copy { williamr@2: typedef choose_default_edge_copier type; williamr@2: }; williamr@2: template williamr@2: struct choose_edge_copier_helper { williamr@2: typedef typename choose_edge_copy::type Selector; williamr@2: typedef typename Selector:: template bind_ Bind; williamr@2: typedef Bind type; williamr@2: typedef typename Bind::result_type result_type; williamr@2: }; williamr@2: template williamr@2: typename detail::choose_edge_copier_helper::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::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 williamr@2: struct bind_ { williamr@2: typedef vertex_copier 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 williamr@2: struct choose_vertex_copy { williamr@2: typedef choose_copier_parameter type; williamr@2: }; williamr@2: template <> williamr@2: struct choose_vertex_copy { williamr@2: typedef choose_default_vertex_copier type; williamr@2: }; williamr@2: template williamr@2: struct choose_vertex_copier_helper { williamr@2: typedef typename choose_vertex_copy::type Selector; williamr@2: typedef typename Selector:: template bind_ Bind; williamr@2: typedef Bind type; williamr@2: typedef typename Bind::result_type result_type; williamr@2: }; williamr@2: template williamr@2: typename detail::choose_vertex_copier_helper::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::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 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::vertex_descriptor vertex_t; williamr@2: std::vector orig2copy(num_vertices(g_in)); williamr@2: typedef typename detail::choose_graph_copy::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 williamr@2: void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out, williamr@2: const bgl_named_params& params) williamr@2: { williamr@2: typename std::vector::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::vertex_descriptor> williamr@2: orig2copy(n); williamr@2: williamr@2: typedef typename detail::choose_graph_copy::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 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 williamr@2: void examine_vertex(Vertex u, const Graph& g_in) const { williamr@2: typename graph_traits::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 williamr@2: void examine_edge(Edge e, const Graph& g_in) const { williamr@2: typename graph_traits::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 williamr@2: typename graph_traits::vertex_descriptor williamr@2: copy_component_impl williamr@2: (const Graph& g_in, williamr@2: typename graph_traits::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 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 williamr@2: typename graph_traits::vertex_descriptor williamr@2: copy_component(IncidenceGraph& g_in, williamr@2: typename graph_traits::vertex_descriptor src, williamr@2: MutableGraph& g_out, williamr@2: const bgl_named_params& params) williamr@2: { williamr@2: typename std::vector::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::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 williamr@2: typename graph_traits::vertex_descriptor williamr@2: copy_component(IncidenceGraph& g_in, williamr@2: typename graph_traits::vertex_descriptor src, williamr@2: MutableGraph& g_out) williamr@2: { williamr@2: std::vector::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('x') // dummy param object williamr@2: ); williamr@2: } williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #endif // BOOST_GRAPH_COPY_HPP