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 | |
53 | namespace 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 | |