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/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 {
edge_copierboost::detail::edge_copier60       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>
operator ()boost::detail::edge_copier65       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>
make_edge_copier(const Graph1 & g1,Graph2 & g2)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 {
vertex_copierboost::detail::vertex_copier80       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>
operator ()boost::detail::vertex_copier85       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>
make_vertex_copier(const Graph1 & g1,Graph2 & g2)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>
applyboost::detail::copy_graph_impl111       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 (boost::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 (boost::tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) {
124           typename graph_traits<MutableGraph>::edge_descriptor new_e;
125           bool inserted;
126           boost::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>
applyboost::detail::copy_graph_impl140       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 (boost::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 (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
152           typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
153           for (boost::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             boost::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>
applyboost::detail::copy_graph_impl171       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 (boost::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 (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
187           typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
188           for (boost::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               boost::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;
applyboost::detail::choose_copier_parameter::bind_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;
applyboost::detail::choose_default_edge_copier::bind_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
choose_edge_copier(const Param & params,const G1 & g_in,G2 & g_out)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;
applyboost::detail::choose_default_vertex_copier::bind_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
choose_vertex_copier(const Param & params,const G1 & g_in,G2 & g_out)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>
copy_graph(const VertexListGraph & g_in,MutableGraph & g_out)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>
copy_graph(const VertexListGraph & g_in,MutableGraph & g_out,const bgl_named_params<P,T,R> & params)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     {
graph_copy_visitorboost::detail::graph_copy_visitor348       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>
copy_one_vertexboost::detail::graph_copy_visitor353       typename graph_traits<NewGraph>::vertex_descriptor copy_one_vertex(Vertex u) 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         return new_u;
359       }
360 
361       template <class Edge, class Graph>
tree_edgeboost::detail::graph_copy_visitor362       void tree_edge(Edge e, const Graph& g_in) const {
363         // For a tree edge, the target vertex has not been copied yet.
364         typename graph_traits<NewGraph>::edge_descriptor new_e;
365         bool inserted;
366         boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)),
367                                                this->copy_one_vertex(target(e, g_in)),
368                                                g_out);
369         copy_edge(e, new_e);
370       }
371 
372       template <class Edge, class Graph>
non_tree_edgeboost::detail::graph_copy_visitor373       void non_tree_edge(Edge e, const Graph& g_in) const {
374         // For a non-tree edge, the target vertex has already been copied.
375         typename graph_traits<NewGraph>::edge_descriptor new_e;
376         bool inserted;
377         boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)),
378                                                get(orig2copy, target(e, g_in)),
379                                                g_out);
380         copy_edge(e, new_e);
381       }
382     private:
383       NewGraph& g_out;
384       Copy2OrigIndexMap orig2copy;
385       CopyVertex copy_vertex;
386       CopyEdge copy_edge;
387     };
388 
389     template <typename Graph, typename MutableGraph,
390               typename CopyVertex, typename CopyEdge,
391               typename Orig2CopyVertexIndexMap, typename Params>
392     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)393     copy_component_impl
394       (const Graph& g_in,
395        typename graph_traits<Graph>::vertex_descriptor src,
396        MutableGraph& g_out,
397        CopyVertex copy_vertex, CopyEdge copy_edge,
398        Orig2CopyVertexIndexMap orig2copy,
399        const Params& params)
400     {
401       graph_copy_visitor<MutableGraph, Orig2CopyVertexIndexMap,
402         CopyVertex, CopyEdge> vis(g_out, orig2copy, copy_vertex, copy_edge);
403       typename graph_traits<MutableGraph>::vertex_descriptor src_copy
404         = vis.copy_one_vertex(src);
405       breadth_first_search(g_in, src, params.visitor(vis));
406       return src_copy;
407     }
408 
409   } // namespace detail
410 
411 
412   // Copy all the vertices and edges of graph g_in that are reachable
413   // from the source vertex into graph g_out. Return the vertex
414   // in g_out that matches the source vertex of g_in.
415   template <typename IncidenceGraph, typename MutableGraph,
416            typename P, typename T, typename R>
417   typename graph_traits<MutableGraph>::vertex_descriptor
copy_component(IncidenceGraph & g_in,typename graph_traits<IncidenceGraph>::vertex_descriptor src,MutableGraph & g_out,const bgl_named_params<P,T,R> & params)418   copy_component(IncidenceGraph& g_in,
419                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
420                  MutableGraph& g_out,
421                  const bgl_named_params<P, T, R>& params)
422   {
423     typename std::vector<T>::size_type n;
424       n = is_default_param(get_param(params, orig_to_copy_t()))
425         ? num_vertices(g_in) : 1;
426     std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
427       orig2copy(n);
428 
429     return detail::copy_component_impl
430       (g_in, src, g_out,
431        detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
432                                     g_in, g_out),
433        detail::choose_edge_copier(get_param(params, edge_copy_t()),
434                                   g_in, g_out),
435        choose_param(get_param(params, orig_to_copy_t()),
436                     make_iterator_property_map
437                     (orig2copy.begin(),
438                      choose_pmap(get_param(params, vertex_index),
439                                  g_in, vertex_index), orig2copy[0])),
440        params
441        );
442   }
443 
444   template <typename IncidenceGraph, typename MutableGraph>
445   typename graph_traits<MutableGraph>::vertex_descriptor
copy_component(IncidenceGraph & g_in,typename graph_traits<IncidenceGraph>::vertex_descriptor src,MutableGraph & g_out)446   copy_component(IncidenceGraph& g_in,
447                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
448                  MutableGraph& g_out)
449   {
450     std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
451       orig2copy(num_vertices(g_in));
452 
453     return detail::copy_component_impl
454       (g_in, src, g_out,
455        make_vertex_copier(g_in, g_out),
456        make_edge_copier(g_in, g_out),
457        make_iterator_property_map(orig2copy.begin(),
458                                   get(vertex_index, g_in), orig2copy[0]),
459        bgl_named_params<char,char>('x') // dummy param object
460        );
461   }
462 
463 } // namespace boost
464 
465 #endif // BOOST_GRAPH_COPY_HPP
466