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