epoc32/include/stdapis/boost/graph/copy.hpp
branchSymbian2
changeset 2 2fe1408b6811
     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