Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / copy.hpp
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