1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/copy.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,450 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 1997-2001 University of Notre Dame.
1.7 +// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +
1.15 +/*
1.16 + This file implements the following functions:
1.17 +
1.18 +
1.19 + template <typename VertexListGraph, typename MutableGraph>
1.20 + void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
1.21 +
1.22 + template <typename VertexListGraph, typename MutableGraph,
1.23 + class P, class T, class R>
1.24 + void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out,
1.25 + const bgl_named_params<P, T, R>& params)
1.26 +
1.27 +
1.28 + template <typename IncidenceGraph, typename MutableGraph>
1.29 + typename graph_traits<MutableGraph>::vertex_descriptor
1.30 + copy_component(IncidenceGraph& g_in,
1.31 + typename graph_traits<IncidenceGraph>::vertex_descriptor src,
1.32 + MutableGraph& g_out)
1.33 +
1.34 + template <typename IncidenceGraph, typename MutableGraph,
1.35 + typename P, typename T, typename R>
1.36 + typename graph_traits<MutableGraph>::vertex_descriptor
1.37 + copy_component(IncidenceGraph& g_in,
1.38 + typename graph_traits<IncidenceGraph>::vertex_descriptor src,
1.39 + MutableGraph& g_out,
1.40 + const bgl_named_params<P, T, R>& params)
1.41 + */
1.42 +
1.43 +
1.44 +#ifndef BOOST_GRAPH_COPY_HPP
1.45 +#define BOOST_GRAPH_COPY_HPP
1.46 +
1.47 +#include <boost/config.hpp>
1.48 +#include <vector>
1.49 +#include <boost/graph/graph_traits.hpp>
1.50 +#include <boost/property_map.hpp>
1.51 +#include <boost/graph/named_function_params.hpp>
1.52 +#include <boost/graph/breadth_first_search.hpp>
1.53 +#include <boost/type_traits/conversion_traits.hpp>
1.54 +
1.55 +namespace boost {
1.56 +
1.57 + namespace detail {
1.58 +
1.59 + // Default edge and vertex property copiers
1.60 +
1.61 + template <typename Graph1, typename Graph2>
1.62 + struct edge_copier {
1.63 + edge_copier(const Graph1& g1, Graph2& g2)
1.64 + : edge_all_map1(get(edge_all, g1)),
1.65 + edge_all_map2(get(edge_all, g2)) { }
1.66 +
1.67 + template <typename Edge1, typename Edge2>
1.68 + void operator()(const Edge1& e1, Edge2& e2) const {
1.69 + put(edge_all_map2, e2, get(edge_all_map1, e1));
1.70 + }
1.71 + typename property_map<Graph1, edge_all_t>::const_type edge_all_map1;
1.72 + mutable typename property_map<Graph2, edge_all_t>::type edge_all_map2;
1.73 + };
1.74 + template <typename Graph1, typename Graph2>
1.75 + inline edge_copier<Graph1,Graph2>
1.76 + make_edge_copier(const Graph1& g1, Graph2& g2)
1.77 + {
1.78 + return edge_copier<Graph1,Graph2>(g1, g2);
1.79 + }
1.80 +
1.81 + template <typename Graph1, typename Graph2>
1.82 + struct vertex_copier {
1.83 + vertex_copier(const Graph1& g1, Graph2& g2)
1.84 + : vertex_all_map1(get(vertex_all, g1)),
1.85 + vertex_all_map2(get(vertex_all, g2)) { }
1.86 +
1.87 + template <typename Vertex1, typename Vertex2>
1.88 + void operator()(const Vertex1& v1, Vertex2& v2) const {
1.89 + put(vertex_all_map2, v2, get(vertex_all_map1, v1));
1.90 + }
1.91 + typename property_map<Graph1, vertex_all_t>::const_type vertex_all_map1;
1.92 + mutable typename property_map<Graph2, vertex_all_t>::type
1.93 + vertex_all_map2;
1.94 + };
1.95 + template <typename Graph1, typename Graph2>
1.96 + inline vertex_copier<Graph1,Graph2>
1.97 + make_vertex_copier(const Graph1& g1, Graph2& g2)
1.98 + {
1.99 + return vertex_copier<Graph1,Graph2>(g1, g2);
1.100 + }
1.101 +
1.102 + // Copy all the vertices and edges of graph g_in into graph g_out.
1.103 + // The copy_vertex and copy_edge function objects control how vertex
1.104 + // and edge properties are copied.
1.105 +
1.106 + template <int Version>
1.107 + struct copy_graph_impl { };
1.108 +
1.109 + template <> struct copy_graph_impl<0>
1.110 + {
1.111 + template <typename Graph, typename MutableGraph,
1.112 + typename CopyVertex, typename CopyEdge, typename IndexMap,
1.113 + typename Orig2CopyVertexIndexMap>
1.114 + static void apply(const Graph& g_in, MutableGraph& g_out,
1.115 + CopyVertex copy_vertex, CopyEdge copy_edge,
1.116 + Orig2CopyVertexIndexMap orig2copy, IndexMap)
1.117 + {
1.118 + typename graph_traits<Graph>::vertex_iterator vi, vi_end;
1.119 + for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
1.120 + typename graph_traits<MutableGraph>::vertex_descriptor
1.121 + new_v = add_vertex(g_out);
1.122 + put(orig2copy, *vi, new_v);
1.123 + copy_vertex(*vi, new_v);
1.124 + }
1.125 + typename graph_traits<Graph>::edge_iterator ei, ei_end;
1.126 + for (tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) {
1.127 + typename graph_traits<MutableGraph>::edge_descriptor new_e;
1.128 + bool inserted;
1.129 + tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
1.130 + get(orig2copy, target(*ei, g_in)),
1.131 + g_out);
1.132 + copy_edge(*ei, new_e);
1.133 + }
1.134 + }
1.135 + };
1.136 +
1.137 + // for directed graphs
1.138 + template <> struct copy_graph_impl<1>
1.139 + {
1.140 + template <typename Graph, typename MutableGraph,
1.141 + typename CopyVertex, typename CopyEdge, typename IndexMap,
1.142 + typename Orig2CopyVertexIndexMap>
1.143 + static void apply(const Graph& g_in, MutableGraph& g_out,
1.144 + CopyVertex copy_vertex, CopyEdge copy_edge,
1.145 + Orig2CopyVertexIndexMap orig2copy, IndexMap)
1.146 + {
1.147 + typename graph_traits<Graph>::vertex_iterator vi, vi_end;
1.148 + for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
1.149 + typename graph_traits<MutableGraph>::vertex_descriptor
1.150 + new_v = add_vertex(g_out);
1.151 + put(orig2copy, *vi, new_v);
1.152 + copy_vertex(*vi, new_v);
1.153 + }
1.154 + for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
1.155 + typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
1.156 + for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
1.157 + typename graph_traits<MutableGraph>::edge_descriptor new_e;
1.158 + bool inserted;
1.159 + tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
1.160 + get(orig2copy, target(*ei, g_in)),
1.161 + g_out);
1.162 + copy_edge(*ei, new_e);
1.163 + }
1.164 + }
1.165 + }
1.166 + };
1.167 +
1.168 + // for undirected graphs
1.169 + template <> struct copy_graph_impl<2>
1.170 + {
1.171 + template <typename Graph, typename MutableGraph,
1.172 + typename CopyVertex, typename CopyEdge, typename IndexMap,
1.173 + typename Orig2CopyVertexIndexMap>
1.174 + static void apply(const Graph& g_in, MutableGraph& g_out,
1.175 + CopyVertex copy_vertex, CopyEdge copy_edge,
1.176 + Orig2CopyVertexIndexMap orig2copy,
1.177 + IndexMap index_map)
1.178 + {
1.179 + typedef color_traits<default_color_type> Color;
1.180 + std::vector<default_color_type>
1.181 + color(num_vertices(g_in), Color::white());
1.182 + typename graph_traits<Graph>::vertex_iterator vi, vi_end;
1.183 + for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
1.184 + typename graph_traits<MutableGraph>::vertex_descriptor
1.185 + new_v = add_vertex(g_out);
1.186 + put(orig2copy, *vi, new_v);
1.187 + copy_vertex(*vi, new_v);
1.188 + }
1.189 + for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
1.190 + typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
1.191 + for (tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) {
1.192 + typename graph_traits<MutableGraph>::edge_descriptor new_e;
1.193 + bool inserted;
1.194 + if (color[get(index_map, target(*ei, g_in))] == Color::white()) {
1.195 + tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei,g_in)),
1.196 + get(orig2copy, target(*ei,g_in)),
1.197 + g_out);
1.198 + copy_edge(*ei, new_e);
1.199 + }
1.200 + }
1.201 + color[get(index_map, *vi)] = Color::black();
1.202 + }
1.203 + }
1.204 + };
1.205 +
1.206 + template <class Graph>
1.207 + struct choose_graph_copy {
1.208 + typedef typename Graph::traversal_category Trv;
1.209 + typedef typename Graph::directed_category Dr;
1.210 + enum { algo =
1.211 + (is_convertible<Trv, vertex_list_graph_tag>::value
1.212 + && is_convertible<Trv, edge_list_graph_tag>::value)
1.213 + ? 0 : is_convertible<Dr, directed_tag>::value ? 1 : 2 };
1.214 + typedef copy_graph_impl<algo> type;
1.215 + };
1.216 +
1.217 + //-------------------------------------------------------------------------
1.218 + struct choose_copier_parameter {
1.219 + template <class P, class G1, class G2>
1.220 + struct bind_ {
1.221 + typedef const P& result_type;
1.222 + static result_type apply(const P& p, const G1&, G2&)
1.223 + { return p; }
1.224 + };
1.225 + };
1.226 + struct choose_default_edge_copier {
1.227 + template <class P, class G1, class G2>
1.228 + struct bind_ {
1.229 + typedef edge_copier<G1, G2> result_type;
1.230 + static result_type apply(const P&, const G1& g1, G2& g2) {
1.231 + return result_type(g1, g2);
1.232 + }
1.233 + };
1.234 + };
1.235 + template <class Param>
1.236 + struct choose_edge_copy {
1.237 + typedef choose_copier_parameter type;
1.238 + };
1.239 + template <>
1.240 + struct choose_edge_copy<detail::error_property_not_found> {
1.241 + typedef choose_default_edge_copier type;
1.242 + };
1.243 + template <class Param, class G1, class G2>
1.244 + struct choose_edge_copier_helper {
1.245 + typedef typename choose_edge_copy<Param>::type Selector;
1.246 + typedef typename Selector:: template bind_<Param, G1, G2> Bind;
1.247 + typedef Bind type;
1.248 + typedef typename Bind::result_type result_type;
1.249 + };
1.250 + template <typename Param, typename G1, typename G2>
1.251 + typename detail::choose_edge_copier_helper<Param,G1,G2>::result_type
1.252 + choose_edge_copier(const Param& params, const G1& g_in, G2& g_out)
1.253 + {
1.254 + typedef typename
1.255 + detail::choose_edge_copier_helper<Param,G1,G2>::type Choice;
1.256 + return Choice::apply(params, g_in, g_out);
1.257 + }
1.258 +
1.259 +
1.260 + struct choose_default_vertex_copier {
1.261 + template <class P, class G1, class G2>
1.262 + struct bind_ {
1.263 + typedef vertex_copier<G1, G2> result_type;
1.264 + static result_type apply(const P&, const G1& g1, G2& g2) {
1.265 + return result_type(g1, g2);
1.266 + }
1.267 + };
1.268 + };
1.269 + template <class Param>
1.270 + struct choose_vertex_copy {
1.271 + typedef choose_copier_parameter type;
1.272 + };
1.273 + template <>
1.274 + struct choose_vertex_copy<detail::error_property_not_found> {
1.275 + typedef choose_default_vertex_copier type;
1.276 + };
1.277 + template <class Param, class G1, class G2>
1.278 + struct choose_vertex_copier_helper {
1.279 + typedef typename choose_vertex_copy<Param>::type Selector;
1.280 + typedef typename Selector:: template bind_<Param, G1, G2> Bind;
1.281 + typedef Bind type;
1.282 + typedef typename Bind::result_type result_type;
1.283 + };
1.284 + template <typename Param, typename G1, typename G2>
1.285 + typename detail::choose_vertex_copier_helper<Param,G1,G2>::result_type
1.286 + choose_vertex_copier(const Param& params, const G1& g_in, G2& g_out)
1.287 + {
1.288 + typedef typename
1.289 + detail::choose_vertex_copier_helper<Param,G1,G2>::type Choice;
1.290 + return Choice::apply(params, g_in, g_out);
1.291 + }
1.292 +
1.293 + } // namespace detail
1.294 +
1.295 +
1.296 + template <typename VertexListGraph, typename MutableGraph>
1.297 + void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
1.298 + {
1.299 + if (num_vertices(g_in) == 0)
1.300 + return;
1.301 + typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
1.302 + std::vector<vertex_t> orig2copy(num_vertices(g_in));
1.303 + typedef typename detail::choose_graph_copy<VertexListGraph>::type
1.304 + copy_impl;
1.305 + copy_impl::apply
1.306 + (g_in, g_out,
1.307 + detail::make_vertex_copier(g_in, g_out),
1.308 + detail::make_edge_copier(g_in, g_out),
1.309 + make_iterator_property_map(orig2copy.begin(),
1.310 + get(vertex_index, g_in), orig2copy[0]),
1.311 + get(vertex_index, g_in)
1.312 + );
1.313 + }
1.314 +
1.315 + template <typename VertexListGraph, typename MutableGraph,
1.316 + class P, class T, class R>
1.317 + void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out,
1.318 + const bgl_named_params<P, T, R>& params)
1.319 + {
1.320 + typename std::vector<T>::size_type n;
1.321 + n = is_default_param(get_param(params, orig_to_copy_t()))
1.322 + ? num_vertices(g_in) : 1;
1.323 + if (n == 0)
1.324 + return;
1.325 + std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor>
1.326 + orig2copy(n);
1.327 +
1.328 + typedef typename detail::choose_graph_copy<VertexListGraph>::type
1.329 + copy_impl;
1.330 + copy_impl::apply
1.331 + (g_in, g_out,
1.332 + detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
1.333 + g_in, g_out),
1.334 + detail::choose_edge_copier(get_param(params, edge_copy_t()),
1.335 + g_in, g_out),
1.336 + choose_param(get_param(params, orig_to_copy_t()),
1.337 + make_iterator_property_map
1.338 + (orig2copy.begin(),
1.339 + choose_const_pmap(get_param(params, vertex_index),
1.340 + g_in, vertex_index), orig2copy[0])),
1.341 + choose_const_pmap(get_param(params, vertex_index), g_in, vertex_index)
1.342 + );
1.343 + }
1.344 +
1.345 + namespace detail {
1.346 +
1.347 + template <class NewGraph, class Copy2OrigIndexMap,
1.348 + class CopyVertex, class CopyEdge>
1.349 + struct graph_copy_visitor : public bfs_visitor<>
1.350 + {
1.351 + graph_copy_visitor(NewGraph& graph, Copy2OrigIndexMap c,
1.352 + CopyVertex cv, CopyEdge ce)
1.353 + : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce) { }
1.354 +
1.355 + template <class Vertex, class Graph>
1.356 + void examine_vertex(Vertex u, const Graph& g_in) const {
1.357 + typename graph_traits<NewGraph>::vertex_descriptor
1.358 + new_u = add_vertex(g_out);
1.359 + put(orig2copy, u, new_u);
1.360 + copy_vertex(u, new_u);
1.361 + }
1.362 +
1.363 + template <class Edge, class Graph>
1.364 + void examine_edge(Edge e, const Graph& g_in) const {
1.365 + typename graph_traits<NewGraph>::edge_descriptor new_e;
1.366 + bool inserted;
1.367 + tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)),
1.368 + get(orig2copy, target(e, g_in)),
1.369 + g_out);
1.370 + copy_edge(e, new_e);
1.371 + }
1.372 + private:
1.373 + NewGraph& g_out;
1.374 + Copy2OrigIndexMap orig2copy;
1.375 + CopyVertex copy_vertex;
1.376 + CopyEdge copy_edge;
1.377 + };
1.378 +
1.379 + template <typename Graph, typename MutableGraph,
1.380 + typename CopyVertex, typename CopyEdge,
1.381 + typename Orig2CopyVertexIndexMap, typename Params>
1.382 + typename graph_traits<MutableGraph>::vertex_descriptor
1.383 + copy_component_impl
1.384 + (const Graph& g_in,
1.385 + typename graph_traits<Graph>::vertex_descriptor src,
1.386 + MutableGraph& g_out,
1.387 + CopyVertex copy_vertex, CopyEdge copy_edge,
1.388 + Orig2CopyVertexIndexMap orig2copy,
1.389 + const Params& params)
1.390 + {
1.391 + graph_copy_visitor<MutableGraph, Orig2CopyVertexIndexMap,
1.392 + CopyVertex, CopyEdge> vis(g_out, orig2copy, copy_vertex, copy_edge);
1.393 + breadth_first_search(g_in, src, params.visitor(vis));
1.394 + return get(orig2copy, src);
1.395 + }
1.396 +
1.397 + } // namespace detail
1.398 +
1.399 +
1.400 + // Copy all the vertices and edges of graph g_in that are reachable
1.401 + // from the source vertex into graph g_out. Return the vertex
1.402 + // in g_out that matches the source vertex of g_in.
1.403 + template <typename IncidenceGraph, typename MutableGraph,
1.404 + typename P, typename T, typename R>
1.405 + typename graph_traits<MutableGraph>::vertex_descriptor
1.406 + copy_component(IncidenceGraph& g_in,
1.407 + typename graph_traits<IncidenceGraph>::vertex_descriptor src,
1.408 + MutableGraph& g_out,
1.409 + const bgl_named_params<P, T, R>& params)
1.410 + {
1.411 + typename std::vector<T>::size_type n;
1.412 + n = is_default_param(get_param(params, orig_to_copy_t()))
1.413 + ? num_vertices(g_in) : 1;
1.414 + std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
1.415 + orig2copy(n);
1.416 +
1.417 + return detail::copy_component_impl
1.418 + (g_in, src, g_out,
1.419 + detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
1.420 + g_in, g_out),
1.421 + detail::choose_edge_copier(get_param(params, edge_copy_t()),
1.422 + g_in, g_out),
1.423 + choose_param(get_param(params, orig_to_copy_t()),
1.424 + make_iterator_property_map
1.425 + (orig2copy.begin(),
1.426 + choose_pmap(get_param(params, vertex_index),
1.427 + g_in, vertex_index), orig2copy[0])),
1.428 + params
1.429 + );
1.430 + }
1.431 +
1.432 + template <typename IncidenceGraph, typename MutableGraph>
1.433 + typename graph_traits<MutableGraph>::vertex_descriptor
1.434 + copy_component(IncidenceGraph& g_in,
1.435 + typename graph_traits<IncidenceGraph>::vertex_descriptor src,
1.436 + MutableGraph& g_out)
1.437 + {
1.438 + std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor>
1.439 + orig2copy(num_vertices(g_in));
1.440 +
1.441 + return detail::copy_component_impl
1.442 + (g_in, src, g_out,
1.443 + make_vertex_copier(g_in, g_out),
1.444 + make_edge_copier(g_in, g_out),
1.445 + make_iterator_property_map(orig2copy.begin(),
1.446 + get(vertex_index, g_in), orig2copy[0]),
1.447 + bgl_named_params<char,char>('x') // dummy param object
1.448 + );
1.449 + }
1.450 +
1.451 +} // namespace boost
1.452 +
1.453 +#endif // BOOST_GRAPH_COPY_HPP