Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:25 

0001 //
0002 //=======================================================================
0003 // Copyright 1997-2001 University of Notre Dame.
0004 // Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 
0012 /*
0013   This file implements the following functions:
0014 
0015 
0016   template <typename VertexListGraph, typename MutableGraph>
0017   void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
0018 
0019   template <typename VertexListGraph, typename MutableGraph,
0020     class P, class T, class R>
0021   void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out,
0022                   const bgl_named_params<P, T, R>& params)
0023 
0024 
0025   template <typename IncidenceGraph, typename MutableGraph>
0026   typename graph_traits<MutableGraph>::vertex_descriptor
0027   copy_component(IncidenceGraph& g_in,
0028                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
0029                  MutableGraph& g_out)
0030 
0031   template <typename IncidenceGraph, typename MutableGraph,
0032            typename P, typename T, typename R>
0033   typename graph_traits<MutableGraph>::vertex_descriptor
0034   copy_component(IncidenceGraph& g_in,
0035                  typename graph_traits<IncidenceGraph>::vertex_descriptor src,
0036                  MutableGraph& g_out,
0037                  const bgl_named_params<P, T, R>& params)
0038  */
0039 
0040 #ifndef BOOST_GRAPH_COPY_HPP
0041 #define BOOST_GRAPH_COPY_HPP
0042 
0043 #include <boost/config.hpp>
0044 #include <vector>
0045 #include <boost/graph/graph_traits.hpp>
0046 #include <boost/graph/reverse_graph.hpp>
0047 #include <boost/property_map/property_map.hpp>
0048 #include <boost/graph/named_function_params.hpp>
0049 #include <boost/graph/breadth_first_search.hpp>
0050 #include <boost/type_traits/conversion_traits.hpp>
0051 
0052 namespace boost
0053 {
0054 
0055 namespace detail
0056 {
0057 
0058     // Hack to make transpose_graph work with the same interface as before
0059     template < typename Graph, typename Desc >
0060     struct remove_reverse_edge_descriptor
0061     {
0062         typedef Desc type;
0063         static Desc convert(const Desc& d, const Graph&) { return d; }
0064     };
0065 
0066     template < typename Graph, typename Desc >
0067     struct remove_reverse_edge_descriptor< Graph,
0068         reverse_graph_edge_descriptor< Desc > >
0069     {
0070         typedef Desc type;
0071         static Desc convert(
0072             const reverse_graph_edge_descriptor< Desc >& d, const Graph& g)
0073         {
0074             return get(edge_underlying, g, d);
0075         }
0076     };
0077 
0078     // Add a reverse_graph_edge_descriptor wrapper if the Graph is a
0079     // reverse_graph but the edge descriptor is from the original graph (this
0080     // case comes from the fact that transpose_graph uses reverse_graph
0081     // internally but doesn't expose the different edge descriptor type to the
0082     // user).
0083     template < typename Desc, typename Graph >
0084     struct add_reverse_edge_descriptor
0085     {
0086         typedef Desc type;
0087         static Desc convert(const Desc& d) { return d; }
0088     };
0089 
0090     template < typename Desc, typename G, typename GR >
0091     struct add_reverse_edge_descriptor< Desc, boost::reverse_graph< G, GR > >
0092     {
0093         typedef reverse_graph_edge_descriptor< Desc > type;
0094         static reverse_graph_edge_descriptor< Desc > convert(const Desc& d)
0095         {
0096             return reverse_graph_edge_descriptor< Desc >(d);
0097         }
0098     };
0099 
0100     template < typename Desc, typename G, typename GR >
0101     struct add_reverse_edge_descriptor< reverse_graph_edge_descriptor< Desc >,
0102         boost::reverse_graph< G, GR > >
0103     {
0104         typedef reverse_graph_edge_descriptor< Desc > type;
0105         static reverse_graph_edge_descriptor< Desc > convert(
0106             const reverse_graph_edge_descriptor< Desc >& d)
0107         {
0108             return d;
0109         }
0110     };
0111 
0112     // Default edge and vertex property copiers
0113 
0114     template < typename Graph1, typename Graph2 > struct edge_copier
0115     {
0116         edge_copier(const Graph1& g1, Graph2& g2)
0117         : edge_all_map1(get(edge_all, g1)), edge_all_map2(get(edge_all, g2))
0118         {
0119         }
0120 
0121         template < typename Edge1, typename Edge2 >
0122         void operator()(const Edge1& e1, Edge2& e2) const
0123         {
0124             put(edge_all_map2, e2,
0125                 get(edge_all_map1,
0126                     add_reverse_edge_descriptor< Edge1, Graph1 >::convert(e1)));
0127         }
0128         typename property_map< Graph1, edge_all_t >::const_type edge_all_map1;
0129         mutable typename property_map< Graph2, edge_all_t >::type edge_all_map2;
0130     };
0131     template < typename Graph1, typename Graph2 >
0132     inline edge_copier< Graph1, Graph2 > make_edge_copier(
0133         const Graph1& g1, Graph2& g2)
0134     {
0135         return edge_copier< Graph1, Graph2 >(g1, g2);
0136     }
0137 
0138     template < typename Graph1, typename Graph2 > struct vertex_copier
0139     {
0140         vertex_copier(const Graph1& g1, Graph2& g2)
0141         : vertex_all_map1(get(vertex_all, g1))
0142         , vertex_all_map2(get(vertex_all, g2))
0143         {
0144         }
0145 
0146         template < typename Vertex1, typename Vertex2 >
0147         void operator()(const Vertex1& v1, Vertex2& v2) const
0148         {
0149             put(vertex_all_map2, v2, get(vertex_all_map1, v1));
0150         }
0151         typename property_map< Graph1, vertex_all_t >::const_type
0152             vertex_all_map1;
0153         mutable
0154             typename property_map< Graph2, vertex_all_t >::type vertex_all_map2;
0155     };
0156     template < typename Graph1, typename Graph2 >
0157     inline vertex_copier< Graph1, Graph2 > make_vertex_copier(
0158         const Graph1& g1, Graph2& g2)
0159     {
0160         return vertex_copier< Graph1, Graph2 >(g1, g2);
0161     }
0162 
0163     // Copy all the vertices and edges of graph g_in into graph g_out.
0164     // The copy_vertex and copy_edge function objects control how vertex
0165     // and edge properties are copied.
0166 
0167     template < int Version > struct copy_graph_impl
0168     {
0169     };
0170 
0171     template <> struct copy_graph_impl< 0 >
0172     {
0173         template < typename Graph, typename MutableGraph, typename CopyVertex,
0174             typename CopyEdge, typename IndexMap,
0175             typename Orig2CopyVertexIndexMap >
0176         static void apply(const Graph& g_in, MutableGraph& g_out,
0177             CopyVertex copy_vertex, CopyEdge copy_edge,
0178             Orig2CopyVertexIndexMap orig2copy, IndexMap)
0179         {
0180             typedef remove_reverse_edge_descriptor< Graph,
0181                 typename graph_traits< Graph >::edge_descriptor >
0182                 cvt;
0183             typename graph_traits< Graph >::vertex_iterator vi, vi_end;
0184             for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi)
0185             {
0186                 typename graph_traits< MutableGraph >::vertex_descriptor new_v
0187                     = add_vertex(g_out);
0188                 put(orig2copy, *vi, new_v);
0189                 copy_vertex(*vi, new_v);
0190             }
0191             typename graph_traits< Graph >::edge_iterator ei, ei_end;
0192             for (boost::tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei)
0193             {
0194                 typename graph_traits< MutableGraph >::edge_descriptor new_e;
0195                 bool inserted;
0196                 boost::tie(new_e, inserted)
0197                     = add_edge(get(orig2copy, source(*ei, g_in)),
0198                         get(orig2copy, target(*ei, g_in)), g_out);
0199                 copy_edge(cvt::convert(*ei, g_in), new_e);
0200             }
0201         }
0202     };
0203 
0204     // for directed graphs
0205     template <> struct copy_graph_impl< 1 >
0206     {
0207         template < typename Graph, typename MutableGraph, typename CopyVertex,
0208             typename CopyEdge, typename IndexMap,
0209             typename Orig2CopyVertexIndexMap >
0210         static void apply(const Graph& g_in, MutableGraph& g_out,
0211             CopyVertex copy_vertex, CopyEdge copy_edge,
0212             Orig2CopyVertexIndexMap orig2copy, IndexMap)
0213         {
0214             typedef remove_reverse_edge_descriptor< Graph,
0215                 typename graph_traits< Graph >::edge_descriptor >
0216                 cvt;
0217             typename graph_traits< Graph >::vertex_iterator vi, vi_end;
0218             for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi)
0219             {
0220                 typename graph_traits< MutableGraph >::vertex_descriptor new_v
0221                     = add_vertex(g_out);
0222                 put(orig2copy, *vi, new_v);
0223                 copy_vertex(*vi, new_v);
0224             }
0225             for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi)
0226             {
0227                 typename graph_traits< Graph >::out_edge_iterator ei, ei_end;
0228                 for (boost::tie(ei, ei_end) = out_edges(*vi, g_in);
0229                      ei != ei_end; ++ei)
0230                 {
0231                     typename graph_traits< MutableGraph >::edge_descriptor
0232                         new_e;
0233                     bool inserted;
0234                     boost::tie(new_e, inserted)
0235                         = add_edge(get(orig2copy, source(*ei, g_in)),
0236                             get(orig2copy, target(*ei, g_in)), g_out);
0237                     copy_edge(cvt::convert(*ei, g_in), new_e);
0238                 }
0239             }
0240         }
0241     };
0242 
0243     // for undirected graphs
0244     template <> struct copy_graph_impl< 2 >
0245     {
0246         template < typename Graph, typename MutableGraph, typename CopyVertex,
0247             typename CopyEdge, typename IndexMap,
0248             typename Orig2CopyVertexIndexMap >
0249         static void apply(const Graph& g_in, MutableGraph& g_out,
0250             CopyVertex copy_vertex, CopyEdge copy_edge,
0251             Orig2CopyVertexIndexMap orig2copy, IndexMap index_map)
0252         {
0253             typedef remove_reverse_edge_descriptor< Graph,
0254                 typename graph_traits< Graph >::edge_descriptor >
0255                 cvt;
0256             typedef color_traits< default_color_type > Color;
0257             std::vector< default_color_type > color(
0258                 num_vertices(g_in), Color::white());
0259             typename graph_traits< Graph >::vertex_iterator vi, vi_end;
0260             for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi)
0261             {
0262                 typename graph_traits< MutableGraph >::vertex_descriptor new_v
0263                     = add_vertex(g_out);
0264                 put(orig2copy, *vi, new_v);
0265                 copy_vertex(*vi, new_v);
0266             }
0267             for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi)
0268             {
0269                 typename graph_traits< Graph >::out_edge_iterator ei, ei_end;
0270                 for (boost::tie(ei, ei_end) = out_edges(*vi, g_in);
0271                      ei != ei_end; ++ei)
0272                 {
0273                     typename graph_traits< MutableGraph >::edge_descriptor
0274                         new_e;
0275                     bool inserted;
0276                     if (color[get(index_map, target(*ei, g_in))]
0277                         == Color::white())
0278                     {
0279                         boost::tie(new_e, inserted)
0280                             = add_edge(get(orig2copy, source(*ei, g_in)),
0281                                 get(orig2copy, target(*ei, g_in)), g_out);
0282                         copy_edge(cvt::convert(*ei, g_in), new_e);
0283                     }
0284                 }
0285                 color[get(index_map, *vi)] = Color::black();
0286             }
0287         }
0288     };
0289 
0290     template < class Graph > struct choose_graph_copy
0291     {
0292         typedef typename graph_traits< Graph >::traversal_category Trv;
0293         typedef typename graph_traits< Graph >::directed_category Dr;
0294         enum
0295         {
0296             algo = (is_convertible< Trv, vertex_list_graph_tag >::value
0297                        && is_convertible< Trv, edge_list_graph_tag >::value)
0298                 ? 0
0299                 : is_convertible< Dr, directed_tag >::value ? 1 : 2
0300         };
0301         typedef copy_graph_impl< algo > type;
0302     };
0303 
0304     //-------------------------------------------------------------------------
0305     struct choose_copier_parameter
0306     {
0307         template < class P, class G1, class G2 > struct bind_
0308         {
0309             typedef const P& result_type;
0310             static result_type apply(const P& p, const G1&, G2&) { return p; }
0311         };
0312     };
0313     struct choose_default_edge_copier
0314     {
0315         template < class P, class G1, class G2 > struct bind_
0316         {
0317             typedef edge_copier< G1, G2 > result_type;
0318             static result_type apply(const P&, const G1& g1, G2& g2)
0319             {
0320                 return result_type(g1, g2);
0321             }
0322         };
0323     };
0324     template < class Param > struct choose_edge_copy
0325     {
0326         typedef choose_copier_parameter type;
0327     };
0328     template <> struct choose_edge_copy< param_not_found >
0329     {
0330         typedef choose_default_edge_copier type;
0331     };
0332     template < class Param, class G1, class G2 >
0333     struct choose_edge_copier_helper
0334     {
0335         typedef typename choose_edge_copy< Param >::type Selector;
0336         typedef typename Selector::template bind_< Param, G1, G2 > Bind;
0337         typedef Bind type;
0338         typedef typename Bind::result_type result_type;
0339     };
0340     template < typename Param, typename G1, typename G2 >
0341     typename detail::choose_edge_copier_helper< Param, G1, G2 >::result_type
0342     choose_edge_copier(const Param& params, const G1& g_in, G2& g_out)
0343     {
0344         typedef
0345             typename detail::choose_edge_copier_helper< Param, G1, G2 >::type
0346                 Choice;
0347         return Choice::apply(params, g_in, g_out);
0348     }
0349 
0350     struct choose_default_vertex_copier
0351     {
0352         template < class P, class G1, class G2 > struct bind_
0353         {
0354             typedef vertex_copier< G1, G2 > result_type;
0355             static result_type apply(const P&, const G1& g1, G2& g2)
0356             {
0357                 return result_type(g1, g2);
0358             }
0359         };
0360     };
0361     template < class Param > struct choose_vertex_copy
0362     {
0363         typedef choose_copier_parameter type;
0364     };
0365     template <> struct choose_vertex_copy< param_not_found >
0366     {
0367         typedef choose_default_vertex_copier type;
0368     };
0369     template < class Param, class G1, class G2 >
0370     struct choose_vertex_copier_helper
0371     {
0372         typedef typename choose_vertex_copy< Param >::type Selector;
0373         typedef typename Selector::template bind_< Param, G1, G2 > Bind;
0374         typedef Bind type;
0375         typedef typename Bind::result_type result_type;
0376     };
0377     template < typename Param, typename G1, typename G2 >
0378     typename detail::choose_vertex_copier_helper< Param, G1, G2 >::result_type
0379     choose_vertex_copier(const Param& params, const G1& g_in, G2& g_out)
0380     {
0381         typedef
0382             typename detail::choose_vertex_copier_helper< Param, G1, G2 >::type
0383                 Choice;
0384         return Choice::apply(params, g_in, g_out);
0385     }
0386 
0387 } // namespace detail
0388 
0389 template < typename VertexListGraph, typename MutableGraph >
0390 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out)
0391 {
0392     if (num_vertices(g_in) == 0)
0393         return;
0394     typedef typename graph_traits< MutableGraph >::vertex_descriptor vertex_t;
0395     std::vector< vertex_t > orig2copy(num_vertices(g_in));
0396     typedef
0397         typename detail::choose_graph_copy< VertexListGraph >::type copy_impl;
0398     copy_impl::apply(g_in, g_out, detail::make_vertex_copier(g_in, g_out),
0399         detail::make_edge_copier(g_in, g_out),
0400         make_iterator_property_map(
0401             orig2copy.begin(), get(vertex_index, g_in), orig2copy[0]),
0402         get(vertex_index, g_in));
0403 }
0404 
0405 template < typename VertexListGraph, typename MutableGraph, class P, class T,
0406     class R >
0407 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out,
0408     const bgl_named_params< P, T, R >& params)
0409 {
0410     typename std::vector< T >::size_type n;
0411     n = is_default_param(get_param(params, orig_to_copy_t()))
0412         ? num_vertices(g_in)
0413         : 1;
0414     if (n == 0)
0415         return;
0416     std::vector<
0417         BOOST_DEDUCED_TYPENAME graph_traits< MutableGraph >::vertex_descriptor >
0418         orig2copy(n);
0419 
0420     typedef
0421         typename detail::choose_graph_copy< VertexListGraph >::type copy_impl;
0422     copy_impl::apply(g_in, g_out,
0423         detail::choose_vertex_copier(
0424             get_param(params, vertex_copy_t()), g_in, g_out),
0425         detail::choose_edge_copier(
0426             get_param(params, edge_copy_t()), g_in, g_out),
0427         choose_param(get_param(params, orig_to_copy_t()),
0428             make_iterator_property_map(orig2copy.begin(),
0429                 choose_const_pmap(
0430                     get_param(params, vertex_index), g_in, vertex_index),
0431                 orig2copy[0])),
0432         choose_const_pmap(get_param(params, vertex_index), g_in, vertex_index));
0433 }
0434 
0435 namespace detail
0436 {
0437 
0438     template < class NewGraph, class Copy2OrigIndexMap, class CopyVertex,
0439         class CopyEdge >
0440     struct graph_copy_visitor : public bfs_visitor<>
0441     {
0442         graph_copy_visitor(
0443             NewGraph& graph, Copy2OrigIndexMap c, CopyVertex cv, CopyEdge ce)
0444         : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce)
0445         {
0446         }
0447 
0448         template < class Vertex >
0449         typename graph_traits< NewGraph >::vertex_descriptor copy_one_vertex(
0450             Vertex u) const
0451         {
0452             typename graph_traits< NewGraph >::vertex_descriptor new_u
0453                 = add_vertex(g_out);
0454             put(orig2copy, u, new_u);
0455             copy_vertex(u, new_u);
0456             return new_u;
0457         }
0458 
0459         template < class Edge, class Graph >
0460         void tree_edge(Edge e, const Graph& g_in) const
0461         {
0462             // For a tree edge, the target vertex has not been copied yet.
0463             typename graph_traits< NewGraph >::edge_descriptor new_e;
0464             bool inserted;
0465             boost::tie(new_e, inserted)
0466                 = add_edge(get(orig2copy, source(e, g_in)),
0467                     this->copy_one_vertex(target(e, g_in)), g_out);
0468             copy_edge(e, new_e);
0469         }
0470 
0471         template < class Edge, class Graph >
0472         void non_tree_edge(Edge e, const Graph& g_in) const
0473         {
0474             // For a non-tree edge, the target vertex has already been copied.
0475             typename graph_traits< NewGraph >::edge_descriptor new_e;
0476             bool inserted;
0477             boost::tie(new_e, inserted)
0478                 = add_edge(get(orig2copy, source(e, g_in)),
0479                     get(orig2copy, target(e, g_in)), g_out);
0480             copy_edge(e, new_e);
0481         }
0482 
0483     private:
0484         NewGraph& g_out;
0485         Copy2OrigIndexMap orig2copy;
0486         CopyVertex copy_vertex;
0487         CopyEdge copy_edge;
0488     };
0489 
0490     template < typename Graph, typename MutableGraph, typename CopyVertex,
0491         typename CopyEdge, typename Orig2CopyVertexIndexMap, typename Params >
0492     typename graph_traits< MutableGraph >::vertex_descriptor
0493     copy_component_impl(const Graph& g_in,
0494         typename graph_traits< Graph >::vertex_descriptor src,
0495         MutableGraph& g_out, CopyVertex copy_vertex, CopyEdge copy_edge,
0496         Orig2CopyVertexIndexMap orig2copy, const Params& params)
0497     {
0498         graph_copy_visitor< MutableGraph, Orig2CopyVertexIndexMap, CopyVertex,
0499             CopyEdge >
0500             vis(g_out, orig2copy, copy_vertex, copy_edge);
0501         typename graph_traits< MutableGraph >::vertex_descriptor src_copy
0502             = vis.copy_one_vertex(src);
0503         breadth_first_search(g_in, src, params.visitor(vis));
0504         return src_copy;
0505     }
0506 
0507 } // namespace detail
0508 
0509 // Copy all the vertices and edges of graph g_in that are reachable
0510 // from the source vertex into graph g_out. Return the vertex
0511 // in g_out that matches the source vertex of g_in.
0512 template < typename IncidenceGraph, typename MutableGraph, typename P,
0513     typename T, typename R >
0514 typename graph_traits< MutableGraph >::vertex_descriptor copy_component(
0515     IncidenceGraph& g_in,
0516     typename graph_traits< IncidenceGraph >::vertex_descriptor src,
0517     MutableGraph& g_out, const bgl_named_params< P, T, R >& params)
0518 {
0519     typename std::vector< T >::size_type n;
0520     n = is_default_param(get_param(params, orig_to_copy_t()))
0521         ? num_vertices(g_in)
0522         : 1;
0523     std::vector< typename graph_traits< IncidenceGraph >::vertex_descriptor >
0524         orig2copy(n);
0525 
0526     return detail::copy_component_impl(g_in, src, g_out,
0527         detail::choose_vertex_copier(
0528             get_param(params, vertex_copy_t()), g_in, g_out),
0529         detail::choose_edge_copier(
0530             get_param(params, edge_copy_t()), g_in, g_out),
0531         choose_param(get_param(params, orig_to_copy_t()),
0532             make_iterator_property_map(orig2copy.begin(),
0533                 choose_pmap(
0534                     get_param(params, vertex_index), g_in, vertex_index),
0535                 orig2copy[0])),
0536         params);
0537 }
0538 
0539 template < typename IncidenceGraph, typename MutableGraph >
0540 typename graph_traits< MutableGraph >::vertex_descriptor copy_component(
0541     IncidenceGraph& g_in,
0542     typename graph_traits< IncidenceGraph >::vertex_descriptor src,
0543     MutableGraph& g_out)
0544 {
0545     std::vector< typename graph_traits< IncidenceGraph >::vertex_descriptor >
0546         orig2copy(num_vertices(g_in));
0547 
0548     return detail::copy_component_impl(g_in, src, g_out,
0549         make_vertex_copier(g_in, g_out), make_edge_copier(g_in, g_out),
0550         make_iterator_property_map(
0551             orig2copy.begin(), get(vertex_index, g_in), orig2copy[0]),
0552         bgl_named_params< char, char >('x') // dummy param object
0553     );
0554 }
0555 
0556 } // namespace boost
0557 
0558 #endif // BOOST_GRAPH_COPY_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!