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