1//
2//=======================================================================
3// Copyright 1997-2001 University of Notre Dame.
4// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
5//
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//=======================================================================
10//
11
12/*
13 This file implements the following functions:
14
15
16 template <typename VertexListGraph, typename MutableGraph>
17 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
18
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)
23
24
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,
29 MutableGraph& g_out)
30
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,
36 MutableGraph& g_out,
37 const bgl_named_params<P, T, R>& params)
38 */
39
40
41#ifndef BOOST_GRAPH_COPY_HPP
42#define BOOST_GRAPH_COPY_HPP
43
44#include <boost/config.hpp>
45#include <vector>
46#include <boost/graph/graph_traits.hpp>
47#include <boost/graph/reverse_graph.hpp>
48#include <boost/property_map/property_map.hpp>
49#include <boost/graph/named_function_params.hpp>
50#include <boost/graph/breadth_first_search.hpp>
51#include <boost/type_traits/conversion_traits.hpp>
52
53namespace boost {
54
55 namespace detail {
56
57 // Hack to make transpose_graph work with the same interface as before
58 template <typename Graph, typename Desc>
59 struct remove_reverse_edge_descriptor {
60 typedef Desc type;
61 static Desc convert(const Desc& d, const Graph&) {return d;}
62 };
63
64 template <typename Graph, typename Desc>
65 struct remove_reverse_edge_descriptor<Graph, reverse_graph_edge_descriptor<Desc> > {
66 typedef Desc type;
67 static Desc convert(const reverse_graph_edge_descriptor<Desc>& d, const Graph& g) {
68 return get(edge_underlying, g, d);
69 }
70 };
71
72 // Add a reverse_graph_edge_descriptor wrapper if the Graph is a
73 // reverse_graph but the edge descriptor is from the original graph (this
74 // case comes from the fact that transpose_graph uses reverse_graph
75 // internally but doesn't expose the different edge descriptor type to the
76 // user).
77 template <typename Desc, typename Graph>
78 struct add_reverse_edge_descriptor {
79 typedef Desc type;
80 static Desc convert(const Desc& d) {return d;}
81 };
82
83 template <typename Desc, typename G, typename GR>
84 struct add_reverse_edge_descriptor<Desc, boost::reverse_graph<G, GR> > {
85 typedef reverse_graph_edge_descriptor<Desc> type;
86 static reverse_graph_edge_descriptor<Desc> convert(const Desc& d) {
87 return reverse_graph_edge_descriptor<Desc>(d);
88 }
89 };
90
91 template <typename Desc, typename G, typename GR>
92 struct add_reverse_edge_descriptor<reverse_graph_edge_descriptor<Desc>, boost::reverse_graph<G, GR> > {
93 typedef reverse_graph_edge_descriptor<Desc> type;
94 static reverse_graph_edge_descriptor<Desc> convert(const reverse_graph_edge_descriptor<Desc>& d) {
95 return d;
96 }
97 };
98
99 // Default edge and vertex property copiers
100
101 template <typename Graph1, typename Graph2>
102 struct edge_copier {
103 edge_copier(const Graph1& g1, Graph2& g2)
104 : edge_all_map1(get(edge_all, g1)),
105 edge_all_map2(get(edge_all, g2)) { }
106
107 template <typename Edge1, typename Edge2>
108 void operator()(const Edge1& e1, Edge2& e2) const {
109 put(edge_all_map2, e2, get(edge_all_map1, add_reverse_edge_descriptor<Edge1, Graph1>::convert(e1)));
110 }
111 typename property_map<Graph1, edge_all_t>::const_type edge_all_map1;
112 mutable typename property_map<Graph2, edge_all_t>::type edge_all_map2;
113 };
114 template <typename Graph1, typename Graph2>
115 inline edge_copier<Graph1,Graph2>
116 make_edge_copier(const Graph1& g1, Graph2& g2)
117 {
118 return edge_copier<Graph1,Graph2>(g1, g2);
119 }
120
121 template <typename Graph1, typename Graph2>
122 struct vertex_copier {
123 vertex_copier(const Graph1& g1, Graph2& g2)
124 : vertex_all_map1(get(vertex_all, g1)),
125 vertex_all_map2(get(vertex_all, g2)) { }
126
127 template <typename Vertex1, typename Vertex2>
128 void operator()(const Vertex1& v1, Vertex2& v2) const {
129 put(vertex_all_map2, v2, get(vertex_all_map1, v1));
130 }
131 typename property_map<Graph1, vertex_all_t>::const_type vertex_all_map1;
132 mutable typename property_map<Graph2, vertex_all_t>::type
133 vertex_all_map2;
134 };
135 template <typename Graph1, typename Graph2>
136 inline vertex_copier<Graph1,Graph2>
137 make_vertex_copier(const Graph1& g1, Graph2& g2)
138 {
139 return vertex_copier<Graph1,Graph2>(g1, g2);
140 }
141
142 // Copy all the vertices and edges of graph g_in into graph g_out.
143 // The copy_vertex and copy_edge function objects control how vertex
144 // and edge properties are copied.
145
146 template <int Version>
147 struct copy_graph_impl { };
148
149 template <> struct copy_graph_impl<0>
150 {
151 template <typename Graph, typename MutableGraph,
152 typename CopyVertex, typename CopyEdge, typename IndexMap,
153 typename Orig2CopyVertexIndexMap>
154 static void apply(const Graph& g_in, MutableGraph& g_out,
155 CopyVertex copy_vertex, CopyEdge copy_edge,
156 Orig2CopyVertexIndexMap orig2copy, IndexMap)
157 {
158 typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt;
159 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
160 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
161 typename graph_traits<MutableGraph>::vertex_descriptor
162 new_v = add_vertex(g_out);
163 put(orig2copy, *vi, new_v);
164 copy_vertex(*vi, new_v);
165 }
166 typename graph_traits<Graph>::edge_iterator ei, ei_end;
167 for (boost::tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) {
168 typename graph_traits<MutableGraph>::edge_descriptor new_e;
169 bool inserted;
170 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
171 get(orig2copy, target(*ei, g_in)),
172 g_out);
173 copy_edge(cvt::convert(*ei, g_in), new_e);
174 }
175 }
176 };
177
178 // for directed graphs
179 template <> struct copy_graph_impl<1>
180 {
181 template <typename Graph, typename MutableGraph,
182 typename CopyVertex, typename CopyEdge, typename IndexMap,
183 typename Orig2CopyVertexIndexMap>
184 static void apply(const Graph& g_in, MutableGraph& g_out,
185 CopyVertex copy_vertex, CopyEdge copy_edge,
186 Orig2CopyVertexIndexMap orig2copy, IndexMap)
187 {
188 typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt;
189 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
190 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
191 typename graph_traits<MutableGraph>::vertex_descriptor
192 new_v = add_vertex(g_out);
193 put(orig2copy, *vi, new_v);
194 copy_vertex(*vi, new_v);
195 }
196 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
197 typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
198 for (boost::tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
199 typename graph_traits<MutableGraph>::edge_descriptor new_e;
200 bool inserted;
201 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
202 get(orig2copy, target(*ei, g_in)),
203 g_out);
204 copy_edge(cvt::convert(*ei, g_in), new_e);
205 }
206 }
207 }
208 };
209
210 // for undirected graphs
211 template <> struct copy_graph_impl<2>
212 {
213 template <typename Graph, typename MutableGraph,
214 typename CopyVertex, typename CopyEdge, typename IndexMap,
215 typename Orig2CopyVertexIndexMap>
216 static void apply(const Graph& g_in, MutableGraph& g_out,
217 CopyVertex copy_vertex, CopyEdge copy_edge,
218 Orig2CopyVertexIndexMap orig2copy,
219 IndexMap index_map)
220 {
221 typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt;
222 typedef color_traits<default_color_type> Color;
223 std::vector<default_color_type>
224 color(num_vertices(g_in), Color::white());
225 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
226 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
227 typename graph_traits<MutableGraph>::vertex_descriptor
228 new_v = add_vertex(g_out);
229 put(orig2copy, *vi, new_v);
230 copy_vertex(*vi, new_v);
231 }
232 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
233 typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
234 for (boost::tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
235 typename graph_traits<MutableGraph>::edge_descriptor new_e;
236 bool inserted;
237 if (color[get(index_map, target(*ei, g_in))] == Color::white()) {
238 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei,g_in)),
239 get(orig2copy, target(*ei,g_in)),
240 g_out);
241 copy_edge(cvt::convert(*ei, g_in), new_e);
242 }
243 }
244 color[get(index_map, *vi)] = Color::black();
245 }
246 }
247 };
248
249 template <class Graph>
250 struct choose_graph_copy {
251 typedef typename Graph::traversal_category Trv;
252 typedef typename Graph::directed_category Dr;
253 enum { algo =
254 (is_convertible<Trv, vertex_list_graph_tag>::value
255 && is_convertible<Trv, edge_list_graph_tag>::value)
256 ? 0 : is_convertible<Dr, directed_tag>::value ? 1 : 2 };
257 typedef copy_graph_impl<algo> type;
258 };
259
260 //-------------------------------------------------------------------------
261 struct choose_copier_parameter {
262 template <class P, class G1, class G2>
263 struct bind_ {
264 typedef const P& result_type;
265 static result_type apply(const P& p, const G1&, G2&)
266 { return p; }
267 };
268 };
269 struct choose_default_edge_copier {
270 template <class P, class G1, class G2>
271 struct bind_ {
272 typedef edge_copier<G1, G2> result_type;
273 static result_type apply(const P&, const G1& g1, G2& g2) {
274 return result_type(g1, g2);
275 }
276 };
277 };
278 template <class Param>
279 struct choose_edge_copy {
280 typedef choose_copier_parameter type;
281 };
282 template <>
283 struct choose_edge_copy<param_not_found> {
284 typedef choose_default_edge_copier type;
285 };
286 template <class Param, class G1, class G2>
287 struct choose_edge_copier_helper {
288 typedef typename choose_edge_copy<Param>::type Selector;
289 typedef typename Selector:: template bind_<Param, G1, G2> Bind;
290 typedef Bind type;
291 typedef typename Bind::result_type result_type;
292 };
293 template <typename Param, typename G1, typename G2>
294 typename detail::choose_edge_copier_helper<Param,G1,G2>::result_type
295 choose_edge_copier(const Param& params, const G1& g_in, G2& g_out)
296 {
297 typedef typename
298 detail::choose_edge_copier_helper<Param,G1,G2>::type Choice;
299 return Choice::apply(params, g_in, g_out);
300 }
301
302
303 struct choose_default_vertex_copier {
304 template <class P, class G1, class G2>
305 struct bind_ {
306 typedef vertex_copier<G1, G2> result_type;
307 static result_type apply(const P&, const G1& g1, G2& g2) {
308 return result_type(g1, g2);
309 }
310 };
311 };
312 template <class Param>
313 struct choose_vertex_copy {
314 typedef choose_copier_parameter type;
315 };
316 template <>
317 struct choose_vertex_copy<param_not_found> {
318 typedef choose_default_vertex_copier type;
319 };
320 template <class Param, class G1, class G2>
321 struct choose_vertex_copier_helper {
322 typedef typename choose_vertex_copy<Param>::type Selector;
323 typedef typename Selector:: template bind_<Param, G1, G2> Bind;
324 typedef Bind type;
325 typedef typename Bind::result_type result_type;
326 };
327 template <typename Param, typename G1, typename G2>
328 typename detail::choose_vertex_copier_helper<Param,G1,G2>::result_type
329 choose_vertex_copier(const Param& params, const G1& g_in, G2& g_out)
330 {
331 typedef typename
332 detail::choose_vertex_copier_helper<Param,G1,G2>::type Choice;
333 return Choice::apply(params, g_in, g_out);
334 }
335
336 } // namespace detail
337
338
339 template <typename VertexListGraph, typename MutableGraph>
340 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
341 {
342 if (num_vertices(g_in) == 0)
343 return;
344 typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
345 std::vector<vertex_t> orig2copy(num_vertices(g_in));
346 typedef typename detail::choose_graph_copy<VertexListGraph>::type
347 copy_impl;
348 copy_impl::apply
349 (g_in, g_out,
350 detail::make_vertex_copier(g_in, g_out),
351 detail::make_edge_copier(g_in, g_out),
352 make_iterator_property_map(orig2copy.begin(),
353 get(vertex_index, g_in), orig2copy[0]),
354 get(vertex_index, g_in)
355 );
356 }
357
358 template <typename VertexListGraph, typename MutableGraph,
359 class P, class T, class R>
360 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out,
361 const bgl_named_params<P, T, R>& params)
362 {
363 typename std::vector<T>::size_type n;
364 n = is_default_param(get_param(params, orig_to_copy_t()))
365 ? num_vertices(g_in) : 1;
366 if (n == 0)
367 return;
368 std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor>
369 orig2copy(n);
370
371 typedef typename detail::choose_graph_copy<VertexListGraph>::type
372 copy_impl;
373 copy_impl::apply
374 (g_in, g_out,
375 detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
376 g_in, g_out),
377 detail::choose_edge_copier(get_param(params, edge_copy_t()),
378 g_in, g_out),
379 choose_param(get_param(params, orig_to_copy_t()),
380 make_iterator_property_map
381 (orig2copy.begin(),
382 choose_const_pmap(get_param(params, vertex_index),
383 g_in, vertex_index), orig2copy[0])),
384 choose_const_pmap(get_param(params, vertex_index), g_in, vertex_index)
385 );
386 }
387
388 namespace detail {
389
390 template <class NewGraph, class Copy2OrigIndexMap,
391 class CopyVertex, class CopyEdge>
392 struct graph_copy_visitor : public bfs_visitor<>
393 {
394 graph_copy_visitor(NewGraph& graph, Copy2OrigIndexMap c,
395 CopyVertex cv, CopyEdge ce)
396 : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce) { }
397
398 template <class Vertex, class Graph>
399 typename graph_traits<NewGraph>::vertex_descriptor copy_one_vertex(Vertex u) const {
400 typename graph_traits<NewGraph>::vertex_descriptor
401 new_u = add_vertex(g_out);
402 put(orig2copy, u, new_u);
403 copy_vertex(u, new_u);
404 return new_u;
405 }
406
407 template <class Edge, class Graph>
408 void tree_edge(Edge e, const Graph& g_in) const {
409 // For a tree edge, the target vertex has not been copied yet.
410 typename graph_traits<NewGraph>::edge_descriptor new_e;
411 bool inserted;
412 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)),
413 this->copy_one_vertex(target(e, g_in)),
414 g_out);
415 copy_edge(e, new_e);
416 }
417
418 template <class Edge, class Graph>
419 void non_tree_edge(Edge e, const Graph& g_in) const {
420 // For a non-tree edge, the target vertex has already been copied.
421 typename graph_traits<NewGraph>::edge_descriptor new_e;
422 bool inserted;
423 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)),
424 get(orig2copy, target(e, g_in)),
425 g_out);
426 copy_edge(e, new_e);
427 }
428 private:
429 NewGraph& g_out;
430 Copy2OrigIndexMap orig2copy;
431 CopyVertex copy_vertex;
432 CopyEdge copy_edge;
433 };
434
435 template <typename Graph, typename MutableGraph,
436 typename CopyVertex, typename CopyEdge,
437 typename Orig2CopyVertexIndexMap, typename Params>
438 typename graph_traits<MutableGraph>::vertex_descriptor
439 copy_component_impl
440 (const Graph& g_in,
441 typename graph_traits<Graph>::vertex_descriptor src,
442 MutableGraph& g_out,
443 CopyVertex copy_vertex, CopyEdge copy_edge,
444 Orig2CopyVertexIndexMap orig2copy,
445 const Params& params)
446 {
447 graph_copy_visitor<MutableGraph, Orig2CopyVertexIndexMap,
448 CopyVertex, CopyEdge> vis(g_out, orig2copy, copy_vertex, copy_edge);
449 typename graph_traits<MutableGraph>::vertex_descriptor src_copy
450 = vis.copy_one_vertex(src);
451 breadth_first_search(g_in, src, params.visitor(vis));
452 return src_copy;
453 }
454
455 } // namespace detail
456
457
458 // Copy all the vertices and edges of graph g_in that are reachable
459 // from the source vertex into graph g_out. Return the vertex
460 // in g_out that matches the source vertex of g_in.
461 template <typename IncidenceGraph, typename MutableGraph,
462 typename P, typename T, typename R>
463 typename graph_traits<MutableGraph>::vertex_descriptor
464 copy_component(IncidenceGraph& g_in,
465 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
466 MutableGraph& g_out,
467 const bgl_named_params<P, T, R>& params)
468 {
469 typename std::vector<T>::size_type n;
470 n = is_default_param(get_param(params, orig_to_copy_t()))
471 ? num_vertices(g_in) : 1;
472 std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
473 orig2copy(n);
474
475 return detail::copy_component_impl
476 (g_in, src, g_out,
477 detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
478 g_in, g_out),
479 detail::choose_edge_copier(get_param(params, edge_copy_t()),
480 g_in, g_out),
481 choose_param(get_param(params, orig_to_copy_t()),
482 make_iterator_property_map
483 (orig2copy.begin(),
484 choose_pmap(get_param(params, vertex_index),
485 g_in, vertex_index), orig2copy[0])),
486 params
487 );
488 }
489
490 template <typename IncidenceGraph, typename MutableGraph>
491 typename graph_traits<MutableGraph>::vertex_descriptor
492 copy_component(IncidenceGraph& g_in,
493 typename graph_traits<IncidenceGraph>::vertex_descriptor src,
494 MutableGraph& g_out)
495 {
496 std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
497 orig2copy(num_vertices(g_in));
498
499 return detail::copy_component_impl
500 (g_in, src, g_out,
501 make_vertex_copier(g_in, g_out),
502 make_edge_copier(g_in, g_out),
503 make_iterator_property_map(orig2copy.begin(),
504 get(vertex_index, g_in), orig2copy[0]),
505 bgl_named_params<char,char>('x') // dummy param object
506 );
507 }
508
509} // namespace boost
510
511#endif // BOOST_GRAPH_COPY_HPP
512

source code of boost/boost/graph/copy.hpp