2 //=======================================================================
3 // Copyright 1997-2001 University of Notre Dame.
4 // Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
13 This file implements the following functions:
16 template <typename VertexListGraph, typename MutableGraph>
17 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
19 template <typename VertexListGraph, typename MutableGraph,
20 class P, class T, class R>
21 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out,
22 const bgl_named_params<P, T, R>& params)
25 template <typename IncidenceGraph, typename MutableGraph>
26 typename graph_traits<MutableGraph>::vertex_descriptor
27 copy_component(IncidenceGraph& g_in,
28 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
31 template <typename IncidenceGraph, typename MutableGraph,
32 typename P, typename T, typename R>
33 typename graph_traits<MutableGraph>::vertex_descriptor
34 copy_component(IncidenceGraph& g_in,
35 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
37 const bgl_named_params<P, T, R>& params)
41 #ifndef BOOST_GRAPH_COPY_HPP
42 #define BOOST_GRAPH_COPY_HPP
44 #include <boost/config.hpp>
46 #include <boost/graph/graph_traits.hpp>
47 #include <boost/property_map.hpp>
48 #include <boost/graph/named_function_params.hpp>
49 #include <boost/graph/breadth_first_search.hpp>
50 #include <boost/type_traits/conversion_traits.hpp>
56 // Default edge and vertex property copiers
58 template <typename Graph1, typename Graph2>
60 edge_copier(const Graph1& g1, Graph2& g2)
61 : edge_all_map1(get(edge_all, g1)),
62 edge_all_map2(get(edge_all, g2)) { }
64 template <typename Edge1, typename Edge2>
65 void operator()(const Edge1& e1, Edge2& e2) const {
66 put(edge_all_map2, e2, get(edge_all_map1, e1));
68 typename property_map<Graph1, edge_all_t>::const_type edge_all_map1;
69 mutable typename property_map<Graph2, edge_all_t>::type edge_all_map2;
71 template <typename Graph1, typename Graph2>
72 inline edge_copier<Graph1,Graph2>
73 make_edge_copier(const Graph1& g1, Graph2& g2)
75 return edge_copier<Graph1,Graph2>(g1, g2);
78 template <typename Graph1, typename Graph2>
79 struct vertex_copier {
80 vertex_copier(const Graph1& g1, Graph2& g2)
81 : vertex_all_map1(get(vertex_all, g1)),
82 vertex_all_map2(get(vertex_all, g2)) { }
84 template <typename Vertex1, typename Vertex2>
85 void operator()(const Vertex1& v1, Vertex2& v2) const {
86 put(vertex_all_map2, v2, get(vertex_all_map1, v1));
88 typename property_map<Graph1, vertex_all_t>::const_type vertex_all_map1;
89 mutable typename property_map<Graph2, vertex_all_t>::type
92 template <typename Graph1, typename Graph2>
93 inline vertex_copier<Graph1,Graph2>
94 make_vertex_copier(const Graph1& g1, Graph2& g2)
96 return vertex_copier<Graph1,Graph2>(g1, g2);
99 // Copy all the vertices and edges of graph g_in into graph g_out.
100 // The copy_vertex and copy_edge function objects control how vertex
101 // and edge properties are copied.
103 template <int Version>
104 struct copy_graph_impl { };
106 template <> struct copy_graph_impl<0>
108 template <typename Graph, typename MutableGraph,
109 typename CopyVertex, typename CopyEdge, typename IndexMap,
110 typename Orig2CopyVertexIndexMap>
111 static void apply(const Graph& g_in, MutableGraph& g_out,
112 CopyVertex copy_vertex, CopyEdge copy_edge,
113 Orig2CopyVertexIndexMap orig2copy, IndexMap)
115 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
116 for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
117 typename graph_traits<MutableGraph>::vertex_descriptor
118 new_v = add_vertex(g_out);
119 put(orig2copy, *vi, new_v);
120 copy_vertex(*vi, new_v);
122 typename graph_traits<Graph>::edge_iterator ei, ei_end;
123 for (tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) {
124 typename graph_traits<MutableGraph>::edge_descriptor new_e;
126 tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
127 get(orig2copy, target(*ei, g_in)),
129 copy_edge(*ei, new_e);
134 // for directed graphs
135 template <> struct copy_graph_impl<1>
137 template <typename Graph, typename MutableGraph,
138 typename CopyVertex, typename CopyEdge, typename IndexMap,
139 typename Orig2CopyVertexIndexMap>
140 static void apply(const Graph& g_in, MutableGraph& g_out,
141 CopyVertex copy_vertex, CopyEdge copy_edge,
142 Orig2CopyVertexIndexMap orig2copy, IndexMap)
144 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
145 for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
146 typename graph_traits<MutableGraph>::vertex_descriptor
147 new_v = add_vertex(g_out);
148 put(orig2copy, *vi, new_v);
149 copy_vertex(*vi, new_v);
151 for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
152 typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
153 for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
154 typename graph_traits<MutableGraph>::edge_descriptor new_e;
156 tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
157 get(orig2copy, target(*ei, g_in)),
159 copy_edge(*ei, new_e);
165 // for undirected graphs
166 template <> struct copy_graph_impl<2>
168 template <typename Graph, typename MutableGraph,
169 typename CopyVertex, typename CopyEdge, typename IndexMap,
170 typename Orig2CopyVertexIndexMap>
171 static void apply(const Graph& g_in, MutableGraph& g_out,
172 CopyVertex copy_vertex, CopyEdge copy_edge,
173 Orig2CopyVertexIndexMap orig2copy,
176 typedef color_traits<default_color_type> Color;
177 std::vector<default_color_type>
178 color(num_vertices(g_in), Color::white());
179 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
180 for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
181 typename graph_traits<MutableGraph>::vertex_descriptor
182 new_v = add_vertex(g_out);
183 put(orig2copy, *vi, new_v);
184 copy_vertex(*vi, new_v);
186 for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
187 typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
188 for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
189 typename graph_traits<MutableGraph>::edge_descriptor new_e;
191 if (color[get(index_map, target(*ei, g_in))] == Color::white()) {
192 tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei,g_in)),
193 get(orig2copy, target(*ei,g_in)),
195 copy_edge(*ei, new_e);
198 color[get(index_map, *vi)] = Color::black();
203 template <class Graph>
204 struct choose_graph_copy {
205 typedef typename Graph::traversal_category Trv;
206 typedef typename Graph::directed_category Dr;
208 (is_convertible<Trv, vertex_list_graph_tag>::value
209 && is_convertible<Trv, edge_list_graph_tag>::value)
210 ? 0 : is_convertible<Dr, directed_tag>::value ? 1 : 2 };
211 typedef copy_graph_impl<algo> type;
214 //-------------------------------------------------------------------------
215 struct choose_copier_parameter {
216 template <class P, class G1, class G2>
218 typedef const P& result_type;
219 static result_type apply(const P& p, const G1&, G2&)
223 struct choose_default_edge_copier {
224 template <class P, class G1, class G2>
226 typedef edge_copier<G1, G2> result_type;
227 static result_type apply(const P&, const G1& g1, G2& g2) {
228 return result_type(g1, g2);
232 template <class Param>
233 struct choose_edge_copy {
234 typedef choose_copier_parameter type;
237 struct choose_edge_copy<detail::error_property_not_found> {
238 typedef choose_default_edge_copier type;
240 template <class Param, class G1, class G2>
241 struct choose_edge_copier_helper {
242 typedef typename choose_edge_copy<Param>::type Selector;
243 typedef typename Selector:: template bind_<Param, G1, G2> Bind;
245 typedef typename Bind::result_type result_type;
247 template <typename Param, typename G1, typename G2>
248 typename detail::choose_edge_copier_helper<Param,G1,G2>::result_type
249 choose_edge_copier(const Param& params, const G1& g_in, G2& g_out)
252 detail::choose_edge_copier_helper<Param,G1,G2>::type Choice;
253 return Choice::apply(params, g_in, g_out);
257 struct choose_default_vertex_copier {
258 template <class P, class G1, class G2>
260 typedef vertex_copier<G1, G2> result_type;
261 static result_type apply(const P&, const G1& g1, G2& g2) {
262 return result_type(g1, g2);
266 template <class Param>
267 struct choose_vertex_copy {
268 typedef choose_copier_parameter type;
271 struct choose_vertex_copy<detail::error_property_not_found> {
272 typedef choose_default_vertex_copier type;
274 template <class Param, class G1, class G2>
275 struct choose_vertex_copier_helper {
276 typedef typename choose_vertex_copy<Param>::type Selector;
277 typedef typename Selector:: template bind_<Param, G1, G2> Bind;
279 typedef typename Bind::result_type result_type;
281 template <typename Param, typename G1, typename G2>
282 typename detail::choose_vertex_copier_helper<Param,G1,G2>::result_type
283 choose_vertex_copier(const Param& params, const G1& g_in, G2& g_out)
286 detail::choose_vertex_copier_helper<Param,G1,G2>::type Choice;
287 return Choice::apply(params, g_in, g_out);
290 } // namespace detail
293 template <typename VertexListGraph, typename MutableGraph>
294 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
296 if (num_vertices(g_in) == 0)
298 typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
299 std::vector<vertex_t> orig2copy(num_vertices(g_in));
300 typedef typename detail::choose_graph_copy<VertexListGraph>::type
304 detail::make_vertex_copier(g_in, g_out),
305 detail::make_edge_copier(g_in, g_out),
306 make_iterator_property_map(orig2copy.begin(),
307 get(vertex_index, g_in), orig2copy[0]),
308 get(vertex_index, g_in)
312 template <typename VertexListGraph, typename MutableGraph,
313 class P, class T, class R>
314 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out,
315 const bgl_named_params<P, T, R>& params)
317 typename std::vector<T>::size_type n;
318 n = is_default_param(get_param(params, orig_to_copy_t()))
319 ? num_vertices(g_in) : 1;
322 std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor>
325 typedef typename detail::choose_graph_copy<VertexListGraph>::type
329 detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
331 detail::choose_edge_copier(get_param(params, edge_copy_t()),
333 choose_param(get_param(params, orig_to_copy_t()),
334 make_iterator_property_map
336 choose_const_pmap(get_param(params, vertex_index),
337 g_in, vertex_index), orig2copy[0])),
338 choose_const_pmap(get_param(params, vertex_index), g_in, vertex_index)
344 template <class NewGraph, class Copy2OrigIndexMap,
345 class CopyVertex, class CopyEdge>
346 struct graph_copy_visitor : public bfs_visitor<>
348 graph_copy_visitor(NewGraph& graph, Copy2OrigIndexMap c,
349 CopyVertex cv, CopyEdge ce)
350 : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce) { }
352 template <class Vertex, class Graph>
353 void examine_vertex(Vertex u, const Graph& g_in) const {
354 typename graph_traits<NewGraph>::vertex_descriptor
355 new_u = add_vertex(g_out);
356 put(orig2copy, u, new_u);
357 copy_vertex(u, new_u);
360 template <class Edge, class Graph>
361 void examine_edge(Edge e, const Graph& g_in) const {
362 typename graph_traits<NewGraph>::edge_descriptor new_e;
364 tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)),
365 get(orig2copy, target(e, g_in)),
371 Copy2OrigIndexMap orig2copy;
372 CopyVertex copy_vertex;
376 template <typename Graph, typename MutableGraph,
377 typename CopyVertex, typename CopyEdge,
378 typename Orig2CopyVertexIndexMap, typename Params>
379 typename graph_traits<MutableGraph>::vertex_descriptor
382 typename graph_traits<Graph>::vertex_descriptor src,
384 CopyVertex copy_vertex, CopyEdge copy_edge,
385 Orig2CopyVertexIndexMap orig2copy,
386 const Params& params)
388 graph_copy_visitor<MutableGraph, Orig2CopyVertexIndexMap,
389 CopyVertex, CopyEdge> vis(g_out, orig2copy, copy_vertex, copy_edge);
390 breadth_first_search(g_in, src, params.visitor(vis));
391 return get(orig2copy, src);
394 } // namespace detail
397 // Copy all the vertices and edges of graph g_in that are reachable
398 // from the source vertex into graph g_out. Return the vertex
399 // in g_out that matches the source vertex of g_in.
400 template <typename IncidenceGraph, typename MutableGraph,
401 typename P, typename T, typename R>
402 typename graph_traits<MutableGraph>::vertex_descriptor
403 copy_component(IncidenceGraph& g_in,
404 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
406 const bgl_named_params<P, T, R>& params)
408 typename std::vector<T>::size_type n;
409 n = is_default_param(get_param(params, orig_to_copy_t()))
410 ? num_vertices(g_in) : 1;
411 std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
414 return detail::copy_component_impl
416 detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
418 detail::choose_edge_copier(get_param(params, edge_copy_t()),
420 choose_param(get_param(params, orig_to_copy_t()),
421 make_iterator_property_map
423 choose_pmap(get_param(params, vertex_index),
424 g_in, vertex_index), orig2copy[0])),
429 template <typename IncidenceGraph, typename MutableGraph>
430 typename graph_traits<MutableGraph>::vertex_descriptor
431 copy_component(IncidenceGraph& g_in,
432 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
435 std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
436 orig2copy(num_vertices(g_in));
438 return detail::copy_component_impl
440 make_vertex_copier(g_in, g_out),
441 make_edge_copier(g_in, g_out),
442 make_iterator_property_map(orig2copy.begin(),
443 get(vertex_index, g_in), orig2copy[0]),
444 bgl_named_params<char,char>('x') // dummy param object
450 #endif // BOOST_GRAPH_COPY_HPP