|
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/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 namespace detail { |
|
55 |
|
56 // Default edge and vertex property copiers |
|
57 |
|
58 template <typename Graph1, typename Graph2> |
|
59 struct edge_copier { |
|
60 edge_copier(const Graph1& g1, Graph2& g2) |
|
61 : edge_all_map1(get(edge_all, g1)), |
|
62 edge_all_map2(get(edge_all, g2)) { } |
|
63 |
|
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)); |
|
67 } |
|
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; |
|
70 }; |
|
71 template <typename Graph1, typename Graph2> |
|
72 inline edge_copier<Graph1,Graph2> |
|
73 make_edge_copier(const Graph1& g1, Graph2& g2) |
|
74 { |
|
75 return edge_copier<Graph1,Graph2>(g1, g2); |
|
76 } |
|
77 |
|
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)) { } |
|
83 |
|
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)); |
|
87 } |
|
88 typename property_map<Graph1, vertex_all_t>::const_type vertex_all_map1; |
|
89 mutable typename property_map<Graph2, vertex_all_t>::type |
|
90 vertex_all_map2; |
|
91 }; |
|
92 template <typename Graph1, typename Graph2> |
|
93 inline vertex_copier<Graph1,Graph2> |
|
94 make_vertex_copier(const Graph1& g1, Graph2& g2) |
|
95 { |
|
96 return vertex_copier<Graph1,Graph2>(g1, g2); |
|
97 } |
|
98 |
|
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. |
|
102 |
|
103 template <int Version> |
|
104 struct copy_graph_impl { }; |
|
105 |
|
106 template <> struct copy_graph_impl<0> |
|
107 { |
|
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) |
|
114 { |
|
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); |
|
121 } |
|
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; |
|
125 bool inserted; |
|
126 tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), |
|
127 get(orig2copy, target(*ei, g_in)), |
|
128 g_out); |
|
129 copy_edge(*ei, new_e); |
|
130 } |
|
131 } |
|
132 }; |
|
133 |
|
134 // for directed graphs |
|
135 template <> struct copy_graph_impl<1> |
|
136 { |
|
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) |
|
143 { |
|
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); |
|
150 } |
|
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; |
|
155 bool inserted; |
|
156 tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), |
|
157 get(orig2copy, target(*ei, g_in)), |
|
158 g_out); |
|
159 copy_edge(*ei, new_e); |
|
160 } |
|
161 } |
|
162 } |
|
163 }; |
|
164 |
|
165 // for undirected graphs |
|
166 template <> struct copy_graph_impl<2> |
|
167 { |
|
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, |
|
174 IndexMap index_map) |
|
175 { |
|
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); |
|
185 } |
|
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; |
|
190 bool inserted; |
|
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)), |
|
194 g_out); |
|
195 copy_edge(*ei, new_e); |
|
196 } |
|
197 } |
|
198 color[get(index_map, *vi)] = Color::black(); |
|
199 } |
|
200 } |
|
201 }; |
|
202 |
|
203 template <class Graph> |
|
204 struct choose_graph_copy { |
|
205 typedef typename Graph::traversal_category Trv; |
|
206 typedef typename Graph::directed_category Dr; |
|
207 enum { algo = |
|
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; |
|
212 }; |
|
213 |
|
214 //------------------------------------------------------------------------- |
|
215 struct choose_copier_parameter { |
|
216 template <class P, class G1, class G2> |
|
217 struct bind_ { |
|
218 typedef const P& result_type; |
|
219 static result_type apply(const P& p, const G1&, G2&) |
|
220 { return p; } |
|
221 }; |
|
222 }; |
|
223 struct choose_default_edge_copier { |
|
224 template <class P, class G1, class G2> |
|
225 struct bind_ { |
|
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); |
|
229 } |
|
230 }; |
|
231 }; |
|
232 template <class Param> |
|
233 struct choose_edge_copy { |
|
234 typedef choose_copier_parameter type; |
|
235 }; |
|
236 template <> |
|
237 struct choose_edge_copy<detail::error_property_not_found> { |
|
238 typedef choose_default_edge_copier type; |
|
239 }; |
|
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; |
|
244 typedef Bind type; |
|
245 typedef typename Bind::result_type result_type; |
|
246 }; |
|
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) |
|
250 { |
|
251 typedef typename |
|
252 detail::choose_edge_copier_helper<Param,G1,G2>::type Choice; |
|
253 return Choice::apply(params, g_in, g_out); |
|
254 } |
|
255 |
|
256 |
|
257 struct choose_default_vertex_copier { |
|
258 template <class P, class G1, class G2> |
|
259 struct bind_ { |
|
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); |
|
263 } |
|
264 }; |
|
265 }; |
|
266 template <class Param> |
|
267 struct choose_vertex_copy { |
|
268 typedef choose_copier_parameter type; |
|
269 }; |
|
270 template <> |
|
271 struct choose_vertex_copy<detail::error_property_not_found> { |
|
272 typedef choose_default_vertex_copier type; |
|
273 }; |
|
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; |
|
278 typedef Bind type; |
|
279 typedef typename Bind::result_type result_type; |
|
280 }; |
|
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) |
|
284 { |
|
285 typedef typename |
|
286 detail::choose_vertex_copier_helper<Param,G1,G2>::type Choice; |
|
287 return Choice::apply(params, g_in, g_out); |
|
288 } |
|
289 |
|
290 } // namespace detail |
|
291 |
|
292 |
|
293 template <typename VertexListGraph, typename MutableGraph> |
|
294 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out) |
|
295 { |
|
296 if (num_vertices(g_in) == 0) |
|
297 return; |
|
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 |
|
301 copy_impl; |
|
302 copy_impl::apply |
|
303 (g_in, g_out, |
|
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) |
|
309 ); |
|
310 } |
|
311 |
|
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) |
|
316 { |
|
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; |
|
320 if (n == 0) |
|
321 return; |
|
322 std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor> |
|
323 orig2copy(n); |
|
324 |
|
325 typedef typename detail::choose_graph_copy<VertexListGraph>::type |
|
326 copy_impl; |
|
327 copy_impl::apply |
|
328 (g_in, g_out, |
|
329 detail::choose_vertex_copier(get_param(params, vertex_copy_t()), |
|
330 g_in, g_out), |
|
331 detail::choose_edge_copier(get_param(params, edge_copy_t()), |
|
332 g_in, g_out), |
|
333 choose_param(get_param(params, orig_to_copy_t()), |
|
334 make_iterator_property_map |
|
335 (orig2copy.begin(), |
|
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) |
|
339 ); |
|
340 } |
|
341 |
|
342 namespace detail { |
|
343 |
|
344 template <class NewGraph, class Copy2OrigIndexMap, |
|
345 class CopyVertex, class CopyEdge> |
|
346 struct graph_copy_visitor : public bfs_visitor<> |
|
347 { |
|
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) { } |
|
351 |
|
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); |
|
358 } |
|
359 |
|
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; |
|
363 bool inserted; |
|
364 tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)), |
|
365 get(orig2copy, target(e, g_in)), |
|
366 g_out); |
|
367 copy_edge(e, new_e); |
|
368 } |
|
369 private: |
|
370 NewGraph& g_out; |
|
371 Copy2OrigIndexMap orig2copy; |
|
372 CopyVertex copy_vertex; |
|
373 CopyEdge copy_edge; |
|
374 }; |
|
375 |
|
376 template <typename Graph, typename MutableGraph, |
|
377 typename CopyVertex, typename CopyEdge, |
|
378 typename Orig2CopyVertexIndexMap, typename Params> |
|
379 typename graph_traits<MutableGraph>::vertex_descriptor |
|
380 copy_component_impl |
|
381 (const Graph& g_in, |
|
382 typename graph_traits<Graph>::vertex_descriptor src, |
|
383 MutableGraph& g_out, |
|
384 CopyVertex copy_vertex, CopyEdge copy_edge, |
|
385 Orig2CopyVertexIndexMap orig2copy, |
|
386 const Params& params) |
|
387 { |
|
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); |
|
392 } |
|
393 |
|
394 } // namespace detail |
|
395 |
|
396 |
|
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, |
|
405 MutableGraph& g_out, |
|
406 const bgl_named_params<P, T, R>& params) |
|
407 { |
|
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> |
|
412 orig2copy(n); |
|
413 |
|
414 return detail::copy_component_impl |
|
415 (g_in, src, g_out, |
|
416 detail::choose_vertex_copier(get_param(params, vertex_copy_t()), |
|
417 g_in, g_out), |
|
418 detail::choose_edge_copier(get_param(params, edge_copy_t()), |
|
419 g_in, g_out), |
|
420 choose_param(get_param(params, orig_to_copy_t()), |
|
421 make_iterator_property_map |
|
422 (orig2copy.begin(), |
|
423 choose_pmap(get_param(params, vertex_index), |
|
424 g_in, vertex_index), orig2copy[0])), |
|
425 params |
|
426 ); |
|
427 } |
|
428 |
|
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, |
|
433 MutableGraph& g_out) |
|
434 { |
|
435 std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor> |
|
436 orig2copy(num_vertices(g_in)); |
|
437 |
|
438 return detail::copy_component_impl |
|
439 (g_in, src, g_out, |
|
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 |
|
445 ); |
|
446 } |
|
447 |
|
448 } // namespace boost |
|
449 |
|
450 #endif // BOOST_GRAPH_COPY_HPP |