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/graph/reverse_graph.hpp> 48 #include <boost/property_map/property_map.hpp> 49 #include <boost/graph/named_function_params.hpp> 50 #include <boost/graph/breadth_first_search.hpp> 51 #include <boost/type_traits/conversion_traits.hpp> 52 53 namespace boost { 54 55 namespace detail { 56 57 // Hack to make transpose_graph work with the same interface as before 58 template <typename Graph, typename Desc> 59 struct remove_reverse_edge_descriptor { 60 typedef Desc type; convertboost::detail::remove_reverse_edge_descriptor61 static Desc convert(const Desc& d, const Graph&) {return d;} 62 }; 63 64 template <typename Graph, typename Desc> 65 struct remove_reverse_edge_descriptor<Graph, reverse_graph_edge_descriptor<Desc> > { 66 typedef Desc type; convertboost::detail::remove_reverse_edge_descriptor67 static Desc convert(const reverse_graph_edge_descriptor<Desc>& d, const Graph& g) { 68 return get(edge_underlying, g, d); 69 } 70 }; 71 72 // Add a reverse_graph_edge_descriptor wrapper if the Graph is a 73 // reverse_graph but the edge descriptor is from the original graph (this 74 // case comes from the fact that transpose_graph uses reverse_graph 75 // internally but doesn't expose the different edge descriptor type to the 76 // user). 77 template <typename Desc, typename Graph> 78 struct add_reverse_edge_descriptor { 79 typedef Desc type; convertboost::detail::add_reverse_edge_descriptor80 static Desc convert(const Desc& d) {return d;} 81 }; 82 83 template <typename Desc, typename G, typename GR> 84 struct add_reverse_edge_descriptor<Desc, boost::reverse_graph<G, GR> > { 85 typedef reverse_graph_edge_descriptor<Desc> type; convertboost::detail::add_reverse_edge_descriptor86 static reverse_graph_edge_descriptor<Desc> convert(const Desc& d) { 87 return reverse_graph_edge_descriptor<Desc>(d); 88 } 89 }; 90 91 template <typename Desc, typename G, typename GR> 92 struct add_reverse_edge_descriptor<reverse_graph_edge_descriptor<Desc>, boost::reverse_graph<G, GR> > { 93 typedef reverse_graph_edge_descriptor<Desc> type; convertboost::detail::add_reverse_edge_descriptor94 static reverse_graph_edge_descriptor<Desc> convert(const reverse_graph_edge_descriptor<Desc>& d) { 95 return d; 96 } 97 }; 98 99 // Default edge and vertex property copiers 100 101 template <typename Graph1, typename Graph2> 102 struct edge_copier { edge_copierboost::detail::edge_copier103 edge_copier(const Graph1& g1, Graph2& g2) 104 : edge_all_map1(get(edge_all, g1)), 105 edge_all_map2(get(edge_all, g2)) { } 106 107 template <typename Edge1, typename Edge2> operator ()boost::detail::edge_copier108 void operator()(const Edge1& e1, Edge2& e2) const { 109 put(edge_all_map2, e2, get(edge_all_map1, add_reverse_edge_descriptor<Edge1, Graph1>::convert(e1))); 110 } 111 typename property_map<Graph1, edge_all_t>::const_type edge_all_map1; 112 mutable typename property_map<Graph2, edge_all_t>::type edge_all_map2; 113 }; 114 template <typename Graph1, typename Graph2> 115 inline edge_copier<Graph1,Graph2> make_edge_copier(const Graph1 & g1,Graph2 & g2)116 make_edge_copier(const Graph1& g1, Graph2& g2) 117 { 118 return edge_copier<Graph1,Graph2>(g1, g2); 119 } 120 121 template <typename Graph1, typename Graph2> 122 struct vertex_copier { vertex_copierboost::detail::vertex_copier123 vertex_copier(const Graph1& g1, Graph2& g2) 124 : vertex_all_map1(get(vertex_all, g1)), 125 vertex_all_map2(get(vertex_all, g2)) { } 126 127 template <typename Vertex1, typename Vertex2> operator ()boost::detail::vertex_copier128 void operator()(const Vertex1& v1, Vertex2& v2) const { 129 put(vertex_all_map2, v2, get(vertex_all_map1, v1)); 130 } 131 typename property_map<Graph1, vertex_all_t>::const_type vertex_all_map1; 132 mutable typename property_map<Graph2, vertex_all_t>::type 133 vertex_all_map2; 134 }; 135 template <typename Graph1, typename Graph2> 136 inline vertex_copier<Graph1,Graph2> make_vertex_copier(const Graph1 & g1,Graph2 & g2)137 make_vertex_copier(const Graph1& g1, Graph2& g2) 138 { 139 return vertex_copier<Graph1,Graph2>(g1, g2); 140 } 141 142 // Copy all the vertices and edges of graph g_in into graph g_out. 143 // The copy_vertex and copy_edge function objects control how vertex 144 // and edge properties are copied. 145 146 template <int Version> 147 struct copy_graph_impl { }; 148 149 template <> struct copy_graph_impl<0> 150 { 151 template <typename Graph, typename MutableGraph, 152 typename CopyVertex, typename CopyEdge, typename IndexMap, 153 typename Orig2CopyVertexIndexMap> applyboost::detail::copy_graph_impl154 static void apply(const Graph& g_in, MutableGraph& g_out, 155 CopyVertex copy_vertex, CopyEdge copy_edge, 156 Orig2CopyVertexIndexMap orig2copy, IndexMap) 157 { 158 typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt; 159 typename graph_traits<Graph>::vertex_iterator vi, vi_end; 160 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { 161 typename graph_traits<MutableGraph>::vertex_descriptor 162 new_v = add_vertex(g_out); 163 put(orig2copy, *vi, new_v); 164 copy_vertex(*vi, new_v); 165 } 166 typename graph_traits<Graph>::edge_iterator ei, ei_end; 167 for (boost::tie(ei, ei_end) = edges(g_in); ei != ei_end; ++ei) { 168 typename graph_traits<MutableGraph>::edge_descriptor new_e; 169 bool inserted; 170 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), 171 get(orig2copy, target(*ei, g_in)), 172 g_out); 173 copy_edge(cvt::convert(*ei, g_in), new_e); 174 } 175 } 176 }; 177 178 // for directed graphs 179 template <> struct copy_graph_impl<1> 180 { 181 template <typename Graph, typename MutableGraph, 182 typename CopyVertex, typename CopyEdge, typename IndexMap, 183 typename Orig2CopyVertexIndexMap> applyboost::detail::copy_graph_impl184 static void apply(const Graph& g_in, MutableGraph& g_out, 185 CopyVertex copy_vertex, CopyEdge copy_edge, 186 Orig2CopyVertexIndexMap orig2copy, IndexMap) 187 { 188 typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt; 189 typename graph_traits<Graph>::vertex_iterator vi, vi_end; 190 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { 191 typename graph_traits<MutableGraph>::vertex_descriptor 192 new_v = add_vertex(g_out); 193 put(orig2copy, *vi, new_v); 194 copy_vertex(*vi, new_v); 195 } 196 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { 197 typename graph_traits<Graph>::out_edge_iterator ei, ei_end; 198 for (boost::tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) { 199 typename graph_traits<MutableGraph>::edge_descriptor new_e; 200 bool inserted; 201 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)), 202 get(orig2copy, target(*ei, g_in)), 203 g_out); 204 copy_edge(cvt::convert(*ei, g_in), new_e); 205 } 206 } 207 } 208 }; 209 210 // for undirected graphs 211 template <> struct copy_graph_impl<2> 212 { 213 template <typename Graph, typename MutableGraph, 214 typename CopyVertex, typename CopyEdge, typename IndexMap, 215 typename Orig2CopyVertexIndexMap> applyboost::detail::copy_graph_impl216 static void apply(const Graph& g_in, MutableGraph& g_out, 217 CopyVertex copy_vertex, CopyEdge copy_edge, 218 Orig2CopyVertexIndexMap orig2copy, 219 IndexMap index_map) 220 { 221 typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt; 222 typedef color_traits<default_color_type> Color; 223 std::vector<default_color_type> 224 color(num_vertices(g_in), Color::white()); 225 typename graph_traits<Graph>::vertex_iterator vi, vi_end; 226 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { 227 typename graph_traits<MutableGraph>::vertex_descriptor 228 new_v = add_vertex(g_out); 229 put(orig2copy, *vi, new_v); 230 copy_vertex(*vi, new_v); 231 } 232 for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) { 233 typename graph_traits<Graph>::out_edge_iterator ei, ei_end; 234 for (boost::tie(ei, ei_end) = out_edges(*vi, g_in); ei != ei_end; ++ei) { 235 typename graph_traits<MutableGraph>::edge_descriptor new_e; 236 bool inserted; 237 if (color[get(index_map, target(*ei, g_in))] == Color::white()) { 238 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei,g_in)), 239 get(orig2copy, target(*ei,g_in)), 240 g_out); 241 copy_edge(cvt::convert(*ei, g_in), new_e); 242 } 243 } 244 color[get(index_map, *vi)] = Color::black(); 245 } 246 } 247 }; 248 249 template <class Graph> 250 struct choose_graph_copy { 251 typedef typename graph_traits<Graph>::traversal_category Trv; 252 typedef typename graph_traits<Graph>::directed_category Dr; 253 enum { algo = 254 (is_convertible<Trv, vertex_list_graph_tag>::value 255 && is_convertible<Trv, edge_list_graph_tag>::value) 256 ? 0 : is_convertible<Dr, directed_tag>::value ? 1 : 2 }; 257 typedef copy_graph_impl<algo> type; 258 }; 259 260 //------------------------------------------------------------------------- 261 struct choose_copier_parameter { 262 template <class P, class G1, class G2> 263 struct bind_ { 264 typedef const P& result_type; applyboost::detail::choose_copier_parameter::bind_265 static result_type apply(const P& p, const G1&, G2&) 266 { return p; } 267 }; 268 }; 269 struct choose_default_edge_copier { 270 template <class P, class G1, class G2> 271 struct bind_ { 272 typedef edge_copier<G1, G2> result_type; applyboost::detail::choose_default_edge_copier::bind_273 static result_type apply(const P&, const G1& g1, G2& g2) { 274 return result_type(g1, g2); 275 } 276 }; 277 }; 278 template <class Param> 279 struct choose_edge_copy { 280 typedef choose_copier_parameter type; 281 }; 282 template <> 283 struct choose_edge_copy<param_not_found> { 284 typedef choose_default_edge_copier type; 285 }; 286 template <class Param, class G1, class G2> 287 struct choose_edge_copier_helper { 288 typedef typename choose_edge_copy<Param>::type Selector; 289 typedef typename Selector:: template bind_<Param, G1, G2> Bind; 290 typedef Bind type; 291 typedef typename Bind::result_type result_type; 292 }; 293 template <typename Param, typename G1, typename G2> 294 typename detail::choose_edge_copier_helper<Param,G1,G2>::result_type choose_edge_copier(const Param & params,const G1 & g_in,G2 & g_out)295 choose_edge_copier(const Param& params, const G1& g_in, G2& g_out) 296 { 297 typedef typename 298 detail::choose_edge_copier_helper<Param,G1,G2>::type Choice; 299 return Choice::apply(params, g_in, g_out); 300 } 301 302 303 struct choose_default_vertex_copier { 304 template <class P, class G1, class G2> 305 struct bind_ { 306 typedef vertex_copier<G1, G2> result_type; applyboost::detail::choose_default_vertex_copier::bind_307 static result_type apply(const P&, const G1& g1, G2& g2) { 308 return result_type(g1, g2); 309 } 310 }; 311 }; 312 template <class Param> 313 struct choose_vertex_copy { 314 typedef choose_copier_parameter type; 315 }; 316 template <> 317 struct choose_vertex_copy<param_not_found> { 318 typedef choose_default_vertex_copier type; 319 }; 320 template <class Param, class G1, class G2> 321 struct choose_vertex_copier_helper { 322 typedef typename choose_vertex_copy<Param>::type Selector; 323 typedef typename Selector:: template bind_<Param, G1, G2> Bind; 324 typedef Bind type; 325 typedef typename Bind::result_type result_type; 326 }; 327 template <typename Param, typename G1, typename G2> 328 typename detail::choose_vertex_copier_helper<Param,G1,G2>::result_type choose_vertex_copier(const Param & params,const G1 & g_in,G2 & g_out)329 choose_vertex_copier(const Param& params, const G1& g_in, G2& g_out) 330 { 331 typedef typename 332 detail::choose_vertex_copier_helper<Param,G1,G2>::type Choice; 333 return Choice::apply(params, g_in, g_out); 334 } 335 336 } // namespace detail 337 338 339 template <typename VertexListGraph, typename MutableGraph> copy_graph(const VertexListGraph & g_in,MutableGraph & g_out)340 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out) 341 { 342 if (num_vertices(g_in) == 0) 343 return; 344 typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t; 345 std::vector<vertex_t> orig2copy(num_vertices(g_in)); 346 typedef typename detail::choose_graph_copy<VertexListGraph>::type 347 copy_impl; 348 copy_impl::apply 349 (g_in, g_out, 350 detail::make_vertex_copier(g_in, g_out), 351 detail::make_edge_copier(g_in, g_out), 352 make_iterator_property_map(orig2copy.begin(), 353 get(vertex_index, g_in), orig2copy[0]), 354 get(vertex_index, g_in) 355 ); 356 } 357 358 template <typename VertexListGraph, typename MutableGraph, 359 class P, class T, class R> copy_graph(const VertexListGraph & g_in,MutableGraph & g_out,const bgl_named_params<P,T,R> & params)360 void copy_graph(const VertexListGraph& g_in, MutableGraph& g_out, 361 const bgl_named_params<P, T, R>& params) 362 { 363 typename std::vector<T>::size_type n; 364 n = is_default_param(get_param(params, orig_to_copy_t())) 365 ? num_vertices(g_in) : 1; 366 if (n == 0) 367 return; 368 std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor> 369 orig2copy(n); 370 371 typedef typename detail::choose_graph_copy<VertexListGraph>::type 372 copy_impl; 373 copy_impl::apply 374 (g_in, g_out, 375 detail::choose_vertex_copier(get_param(params, vertex_copy_t()), 376 g_in, g_out), 377 detail::choose_edge_copier(get_param(params, edge_copy_t()), 378 g_in, g_out), 379 choose_param(get_param(params, orig_to_copy_t()), 380 make_iterator_property_map 381 (orig2copy.begin(), 382 choose_const_pmap(get_param(params, vertex_index), 383 g_in, vertex_index), orig2copy[0])), 384 choose_const_pmap(get_param(params, vertex_index), g_in, vertex_index) 385 ); 386 } 387 388 namespace detail { 389 390 template <class NewGraph, class Copy2OrigIndexMap, 391 class CopyVertex, class CopyEdge> 392 struct graph_copy_visitor : public bfs_visitor<> 393 { graph_copy_visitorboost::detail::graph_copy_visitor394 graph_copy_visitor(NewGraph& graph, Copy2OrigIndexMap c, 395 CopyVertex cv, CopyEdge ce) 396 : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce) { } 397 398 template <class Vertex> copy_one_vertexboost::detail::graph_copy_visitor399 typename graph_traits<NewGraph>::vertex_descriptor copy_one_vertex(Vertex u) const { 400 typename graph_traits<NewGraph>::vertex_descriptor 401 new_u = add_vertex(g_out); 402 put(orig2copy, u, new_u); 403 copy_vertex(u, new_u); 404 return new_u; 405 } 406 407 template <class Edge, class Graph> tree_edgeboost::detail::graph_copy_visitor408 void tree_edge(Edge e, const Graph& g_in) const { 409 // For a tree edge, the target vertex has not been copied yet. 410 typename graph_traits<NewGraph>::edge_descriptor new_e; 411 bool inserted; 412 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)), 413 this->copy_one_vertex(target(e, g_in)), 414 g_out); 415 copy_edge(e, new_e); 416 } 417 418 template <class Edge, class Graph> non_tree_edgeboost::detail::graph_copy_visitor419 void non_tree_edge(Edge e, const Graph& g_in) const { 420 // For a non-tree edge, the target vertex has already been copied. 421 typename graph_traits<NewGraph>::edge_descriptor new_e; 422 bool inserted; 423 boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(e, g_in)), 424 get(orig2copy, target(e, g_in)), 425 g_out); 426 copy_edge(e, new_e); 427 } 428 private: 429 NewGraph& g_out; 430 Copy2OrigIndexMap orig2copy; 431 CopyVertex copy_vertex; 432 CopyEdge copy_edge; 433 }; 434 435 template <typename Graph, typename MutableGraph, 436 typename CopyVertex, typename CopyEdge, 437 typename Orig2CopyVertexIndexMap, typename Params> 438 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)439 copy_component_impl 440 (const Graph& g_in, 441 typename graph_traits<Graph>::vertex_descriptor src, 442 MutableGraph& g_out, 443 CopyVertex copy_vertex, CopyEdge copy_edge, 444 Orig2CopyVertexIndexMap orig2copy, 445 const Params& params) 446 { 447 graph_copy_visitor<MutableGraph, Orig2CopyVertexIndexMap, 448 CopyVertex, CopyEdge> vis(g_out, orig2copy, copy_vertex, copy_edge); 449 typename graph_traits<MutableGraph>::vertex_descriptor src_copy 450 = vis.copy_one_vertex(src); 451 breadth_first_search(g_in, src, params.visitor(vis)); 452 return src_copy; 453 } 454 455 } // namespace detail 456 457 458 // Copy all the vertices and edges of graph g_in that are reachable 459 // from the source vertex into graph g_out. Return the vertex 460 // in g_out that matches the source vertex of g_in. 461 template <typename IncidenceGraph, typename MutableGraph, 462 typename P, typename T, typename R> 463 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)464 copy_component(IncidenceGraph& g_in, 465 typename graph_traits<IncidenceGraph>::vertex_descriptor src, 466 MutableGraph& g_out, 467 const bgl_named_params<P, T, R>& params) 468 { 469 typename std::vector<T>::size_type n; 470 n = is_default_param(get_param(params, orig_to_copy_t())) 471 ? num_vertices(g_in) : 1; 472 std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor> 473 orig2copy(n); 474 475 return detail::copy_component_impl 476 (g_in, src, g_out, 477 detail::choose_vertex_copier(get_param(params, vertex_copy_t()), 478 g_in, g_out), 479 detail::choose_edge_copier(get_param(params, edge_copy_t()), 480 g_in, g_out), 481 choose_param(get_param(params, orig_to_copy_t()), 482 make_iterator_property_map 483 (orig2copy.begin(), 484 choose_pmap(get_param(params, vertex_index), 485 g_in, vertex_index), orig2copy[0])), 486 params 487 ); 488 } 489 490 template <typename IncidenceGraph, typename MutableGraph> 491 typename graph_traits<MutableGraph>::vertex_descriptor copy_component(IncidenceGraph & g_in,typename graph_traits<IncidenceGraph>::vertex_descriptor src,MutableGraph & g_out)492 copy_component(IncidenceGraph& g_in, 493 typename graph_traits<IncidenceGraph>::vertex_descriptor src, 494 MutableGraph& g_out) 495 { 496 std::vector<typename graph_traits<IncidenceGraph>::vertex_descriptor> 497 orig2copy(num_vertices(g_in)); 498 499 return detail::copy_component_impl 500 (g_in, src, g_out, 501 make_vertex_copier(g_in, g_out), 502 make_edge_copier(g_in, g_out), 503 make_iterator_property_map(orig2copy.begin(), 504 get(vertex_index, g_in), orig2copy[0]), 505 bgl_named_params<char,char>('x') // dummy param object 506 ); 507 } 508 509 } // namespace boost 510 511 #endif // BOOST_GRAPH_COPY_HPP 512