1 //======================================================================= 2 // Copyright 2001 University of Notre Dame. 3 // Authors: Jeremy G. Siek and Lie-Quan Lee 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 //======================================================================= 9 10 #ifndef BOOST_SUBGRAPH_HPP 11 #define BOOST_SUBGRAPH_HPP 12 13 // UNDER CONSTRUCTION 14 15 #include <boost/config.hpp> 16 #include <list> 17 #include <vector> 18 #include <map> 19 #include <cassert> 20 #include <boost/graph/graph_traits.hpp> 21 #include <boost/graph/properties.hpp> 22 #include <boost/iterator/indirect_iterator.hpp> 23 24 #include <boost/static_assert.hpp> 25 #include <boost/type_traits/is_same.hpp> 26 27 namespace boost { 28 29 struct subgraph_tag { }; 30 31 // Invariants of an induced subgraph: 32 // - If vertex u is in subgraph g, then u must be in g.parent(). 33 // - If edge e is in subgraph g, then e must be in g.parent(). 34 // - If edge e=(u,v) is in the root graph, then edge e 35 // is also in any subgraph that contains both vertex u and v. 36 37 // The Graph template parameter must have a vertex_index 38 // and edge_index internal property. It is assumed that 39 // the vertex indices are assigned automatically by the 40 // graph during a call to add_vertex(). It is not 41 // assumed that the edge vertices are assigned automatically, 42 // they are explicitly assigned here. 43 44 template <typename Graph> 45 class subgraph { 46 typedef graph_traits<Graph> Traits; 47 typedef std::list<subgraph<Graph>*> ChildrenList; 48 public: 49 // Graph requirements 50 typedef typename Traits::vertex_descriptor vertex_descriptor; 51 typedef typename Traits::edge_descriptor edge_descriptor; 52 typedef typename Traits::directed_category directed_category; 53 typedef typename Traits::edge_parallel_category edge_parallel_category; 54 typedef typename Traits::traversal_category traversal_category; 55 null_vertex()56 static vertex_descriptor null_vertex() 57 { 58 return Traits::null_vertex(); 59 } 60 61 62 // IncidenceGraph requirements 63 typedef typename Traits::out_edge_iterator out_edge_iterator; 64 typedef typename Traits::degree_size_type degree_size_type; 65 66 // AdjacencyGraph requirements 67 typedef typename Traits::adjacency_iterator adjacency_iterator; 68 69 // VertexListGraph requirements 70 typedef typename Traits::vertex_iterator vertex_iterator; 71 typedef typename Traits::vertices_size_type vertices_size_type; 72 73 // EdgeListGraph requirements 74 typedef typename Traits::edge_iterator edge_iterator; 75 typedef typename Traits::edges_size_type edges_size_type; 76 77 typedef typename Traits::in_edge_iterator in_edge_iterator; 78 79 typedef typename Graph::edge_property_type edge_property_type; 80 typedef typename Graph::vertex_property_type vertex_property_type; 81 typedef subgraph_tag graph_tag; 82 typedef Graph graph_type; 83 typedef typename Graph::graph_property_type graph_property_type; 84 85 // Constructors 86 87 // Create the main graph, the root of the subgraph tree subgraph()88 subgraph() 89 : m_parent(0), m_edge_counter(0) 90 { } subgraph(const graph_property_type & p)91 subgraph(const graph_property_type& p) 92 : m_graph(p), m_parent(0), m_edge_counter(0) 93 { } subgraph(vertices_size_type n,const graph_property_type & p=graph_property_type ())94 subgraph(vertices_size_type n, 95 const graph_property_type& p = graph_property_type()) 96 : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n) 97 { 98 typename Graph::vertex_iterator v, v_end; 99 vertices_size_type i = 0; 100 for (tie(v, v_end) = vertices(m_graph); v != v_end; ++v) 101 m_global_vertex[i++] = *v; 102 } 103 104 // copy constructor subgraph(const subgraph & x)105 subgraph(const subgraph& x) 106 : m_graph(x.m_graph), m_parent(x.m_parent), 107 m_edge_counter(x.m_edge_counter), 108 m_global_vertex(x.m_global_vertex), 109 m_global_edge(x.m_global_edge) 110 { 111 // Do a deep copy 112 for (typename ChildrenList::const_iterator i = x.m_children.begin(); 113 i != x.m_children.end(); ++i) 114 m_children.push_back(new subgraph<Graph>( **i )); 115 } 116 117 ~subgraph()118 ~subgraph() { 119 for (typename ChildrenList::iterator i = m_children.begin(); 120 i != m_children.end(); ++i) 121 delete *i; 122 } 123 124 125 // Create a subgraph create_subgraph()126 subgraph<Graph>& create_subgraph() { 127 m_children.push_back(new subgraph<Graph>()); 128 m_children.back()->m_parent = this; 129 return *m_children.back(); 130 } 131 132 // Create a subgraph with the specified vertex set. 133 template <typename VertexIterator> create_subgraph(VertexIterator first,VertexIterator last)134 subgraph<Graph>& create_subgraph(VertexIterator first, 135 VertexIterator last) 136 { 137 m_children.push_back(new subgraph<Graph>()); 138 m_children.back()->m_parent = this; 139 for (; first != last; ++first) 140 add_vertex(*first, *m_children.back()); 141 return *m_children.back(); 142 } 143 144 // local <-> global descriptor conversion functions local_to_global(vertex_descriptor u_local) const145 vertex_descriptor local_to_global(vertex_descriptor u_local) const 146 { 147 return m_global_vertex[u_local]; 148 } global_to_local(vertex_descriptor u_global) const149 vertex_descriptor global_to_local(vertex_descriptor u_global) const 150 { 151 vertex_descriptor u_local; bool in_subgraph; 152 tie(u_local, in_subgraph) = this->find_vertex(u_global); 153 assert(in_subgraph == true); 154 return u_local; 155 } local_to_global(edge_descriptor e_local) const156 edge_descriptor local_to_global(edge_descriptor e_local) const 157 { 158 return m_global_edge[get(get(edge_index, m_graph), e_local)]; 159 } global_to_local(edge_descriptor e_global) const160 edge_descriptor global_to_local(edge_descriptor e_global) const 161 { 162 return 163 (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second; 164 } 165 166 // Is vertex u (of the root graph) contained in this subgraph? 167 // If so, return the matching local vertex. 168 std::pair<vertex_descriptor, bool> find_vertex(vertex_descriptor u_global) const169 find_vertex(vertex_descriptor u_global) const 170 { 171 typename std::map<vertex_descriptor, vertex_descriptor>::const_iterator 172 i = m_local_vertex.find(u_global); 173 bool valid = i != m_local_vertex.end(); 174 return std::make_pair((valid ? (*i).second : null_vertex()), valid); 175 } 176 177 // Return the parent graph. parent()178 subgraph& parent() { return *m_parent; } parent() const179 const subgraph& parent() const { return *m_parent; } 180 is_root() const181 bool is_root() const { return m_parent == 0; } 182 183 // Return the root graph of the subgraph tree. root()184 subgraph& root() { 185 if (this->is_root()) 186 return *this; 187 else 188 return m_parent->root(); 189 } root() const190 const subgraph& root() const { 191 if (this->is_root()) 192 return *this; 193 else 194 return m_parent->root(); 195 } 196 197 // Return the children subgraphs of this graph/subgraph. 198 // Use a list of pointers because the VC++ std::list doesn't like 199 // storing incomplete type. 200 typedef indirect_iterator< 201 typename ChildrenList::const_iterator 202 , subgraph<Graph> 203 , std::bidirectional_iterator_tag 204 > 205 children_iterator; 206 207 typedef indirect_iterator< 208 typename ChildrenList::const_iterator 209 , subgraph<Graph> const 210 , std::bidirectional_iterator_tag 211 > 212 const_children_iterator; 213 214 std::pair<const_children_iterator, const_children_iterator> children() const215 children() const 216 { 217 return std::make_pair(const_children_iterator(m_children.begin()), 218 const_children_iterator(m_children.end())); 219 } 220 221 std::pair<children_iterator, children_iterator> children()222 children() 223 { 224 return std::make_pair(children_iterator(m_children.begin()), 225 children_iterator(m_children.end())); 226 } 227 num_children() const228 std::size_t num_children() const { return m_children.size(); } 229 230 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES 231 // Bundled properties support 232 template<typename Descriptor> 233 typename graph::detail::bundled_result<Graph, Descriptor>::type& operator [](Descriptor x)234 operator[](Descriptor x) 235 { 236 if (m_parent == 0) return m_graph[x]; 237 else return root().m_graph[local_to_global(x)]; 238 } 239 240 template<typename Descriptor> 241 typename graph::detail::bundled_result<Graph, Descriptor>::type const& operator [](Descriptor x) const242 operator[](Descriptor x) const 243 { 244 if (m_parent == 0) return m_graph[x]; 245 else return root().m_graph[local_to_global(x)]; 246 } 247 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES 248 249 // private: 250 typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap; 251 typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type; 252 BOOST_STATIC_ASSERT((!is_same<edge_index_type, 253 boost::detail::error_property_not_found>::value)); 254 255 Graph m_graph; 256 subgraph<Graph>* m_parent; 257 edge_index_type m_edge_counter; // for generating unique edge indices 258 ChildrenList m_children; 259 std::vector<vertex_descriptor> m_global_vertex; // local -> global 260 std::map<vertex_descriptor, vertex_descriptor> m_local_vertex; // global -> local 261 std::vector<edge_descriptor> m_global_edge; // local -> global 262 std::map<edge_index_type, edge_descriptor> m_local_edge; // global -> local 263 264 edge_descriptor local_add_edge(vertex_descriptor u_local,vertex_descriptor v_local,edge_descriptor e_global)265 local_add_edge(vertex_descriptor u_local, vertex_descriptor v_local, 266 edge_descriptor e_global) 267 { 268 edge_descriptor e_local; 269 bool inserted; 270 tie(e_local, inserted) = add_edge(u_local, v_local, m_graph); 271 put(edge_index, m_graph, e_local, m_edge_counter++); 272 m_global_edge.push_back(e_global); 273 m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local; 274 return e_local; 275 } 276 277 }; 278 279 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES 280 template<typename Graph> 281 struct vertex_bundle_type<subgraph<Graph> > : vertex_bundle_type<Graph> { }; 282 283 template<typename Graph> 284 struct edge_bundle_type<subgraph<Graph> > : edge_bundle_type<Graph> { }; 285 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES 286 287 //=========================================================================== 288 // Functions special to the Subgraph Class 289 290 template <typename G> 291 typename subgraph<G>::vertex_descriptor add_vertex(typename subgraph<G>::vertex_descriptor u_global,subgraph<G> & g)292 add_vertex(typename subgraph<G>::vertex_descriptor u_global, 293 subgraph<G>& g) 294 { 295 assert(!g.is_root()); 296 typename subgraph<G>::vertex_descriptor u_local, v_global, uu_global; 297 typename subgraph<G>::edge_descriptor e_global; 298 299 u_local = add_vertex(g.m_graph); 300 g.m_global_vertex.push_back(u_global); 301 g.m_local_vertex[u_global] = u_local; 302 303 subgraph<G>& r = g.root(); 304 305 // remember edge global and local maps 306 { 307 typename subgraph<G>::out_edge_iterator ei, ei_end; 308 for (tie(ei, ei_end) = out_edges(u_global, r); 309 ei != ei_end; ++ei) { 310 e_global = *ei; 311 v_global = target(e_global, r); 312 if (g.find_vertex(v_global).second == true) 313 g.local_add_edge(u_local, g.global_to_local(v_global), e_global); 314 } 315 } 316 if (is_directed(g)) { // not necessary for undirected graph 317 typename subgraph<G>::vertex_iterator vi, vi_end; 318 typename subgraph<G>::out_edge_iterator ei, ei_end; 319 for (tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) { 320 v_global = *vi; 321 if (g.find_vertex(v_global).second) 322 for (tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) { 323 e_global = *ei; 324 uu_global = target(e_global, r); 325 if (uu_global == u_global && g.find_vertex(v_global).second) 326 g.local_add_edge(g.global_to_local(v_global), u_local, e_global); 327 } 328 } 329 } 330 331 return u_local; 332 } 333 334 //=========================================================================== 335 // Functions required by the IncidenceGraph concept 336 337 template <typename G> 338 std::pair<typename graph_traits<G>::out_edge_iterator, 339 typename graph_traits<G>::out_edge_iterator> out_edges(typename graph_traits<G>::vertex_descriptor u_local,const subgraph<G> & g)340 out_edges(typename graph_traits<G>::vertex_descriptor u_local, 341 const subgraph<G>& g) 342 { return out_edges(u_local, g.m_graph); } 343 344 template <typename G> 345 typename graph_traits<G>::degree_size_type out_degree(typename graph_traits<G>::vertex_descriptor u_local,const subgraph<G> & g)346 out_degree(typename graph_traits<G>::vertex_descriptor u_local, 347 const subgraph<G>& g) 348 { return out_degree(u_local, g.m_graph); } 349 350 template <typename G> 351 typename graph_traits<G>::vertex_descriptor source(typename graph_traits<G>::edge_descriptor e_local,const subgraph<G> & g)352 source(typename graph_traits<G>::edge_descriptor e_local, 353 const subgraph<G>& g) 354 { return source(e_local, g.m_graph); } 355 356 template <typename G> 357 typename graph_traits<G>::vertex_descriptor target(typename graph_traits<G>::edge_descriptor e_local,const subgraph<G> & g)358 target(typename graph_traits<G>::edge_descriptor e_local, 359 const subgraph<G>& g) 360 { return target(e_local, g.m_graph); } 361 362 //=========================================================================== 363 // Functions required by the BidirectionalGraph concept 364 365 template <typename G> 366 std::pair<typename graph_traits<G>::in_edge_iterator, 367 typename graph_traits<G>::in_edge_iterator> in_edges(typename graph_traits<G>::vertex_descriptor u_local,const subgraph<G> & g)368 in_edges(typename graph_traits<G>::vertex_descriptor u_local, 369 const subgraph<G>& g) 370 { return in_edges(u_local, g.m_graph); } 371 372 template <typename G> 373 typename graph_traits<G>::degree_size_type in_degree(typename graph_traits<G>::vertex_descriptor u_local,const subgraph<G> & g)374 in_degree(typename graph_traits<G>::vertex_descriptor u_local, 375 const subgraph<G>& g) 376 { return in_degree(u_local, g.m_graph); } 377 378 template <typename G> 379 typename graph_traits<G>::degree_size_type degree(typename graph_traits<G>::vertex_descriptor u_local,const subgraph<G> & g)380 degree(typename graph_traits<G>::vertex_descriptor u_local, 381 const subgraph<G>& g) 382 { return degree(u_local, g.m_graph); } 383 384 //=========================================================================== 385 // Functions required by the AdjacencyGraph concept 386 387 template <typename G> 388 std::pair<typename subgraph<G>::adjacency_iterator, 389 typename subgraph<G>::adjacency_iterator> adjacent_vertices(typename subgraph<G>::vertex_descriptor u_local,const subgraph<G> & g)390 adjacent_vertices(typename subgraph<G>::vertex_descriptor u_local, 391 const subgraph<G>& g) 392 { return adjacent_vertices(u_local, g.m_graph); } 393 394 //=========================================================================== 395 // Functions required by the VertexListGraph concept 396 397 template <typename G> 398 std::pair<typename subgraph<G>::vertex_iterator, 399 typename subgraph<G>::vertex_iterator> vertices(const subgraph<G> & g)400 vertices(const subgraph<G>& g) 401 { return vertices(g.m_graph); } 402 403 template <typename G> 404 typename subgraph<G>::vertices_size_type num_vertices(const subgraph<G> & g)405 num_vertices(const subgraph<G>& g) 406 { return num_vertices(g.m_graph); } 407 408 //=========================================================================== 409 // Functions required by the EdgeListGraph concept 410 411 template <typename G> 412 std::pair<typename subgraph<G>::edge_iterator, 413 typename subgraph<G>::edge_iterator> edges(const subgraph<G> & g)414 edges(const subgraph<G>& g) 415 { return edges(g.m_graph); } 416 417 template <typename G> 418 typename subgraph<G>::edges_size_type num_edges(const subgraph<G> & g)419 num_edges(const subgraph<G>& g) 420 { return num_edges(g.m_graph); } 421 422 //=========================================================================== 423 // Functions required by the AdjacencyMatrix concept 424 425 template <typename G> 426 std::pair<typename subgraph<G>::edge_descriptor, bool> edge(typename subgraph<G>::vertex_descriptor u_local,typename subgraph<G>::vertex_descriptor v_local,const subgraph<G> & g)427 edge(typename subgraph<G>::vertex_descriptor u_local, 428 typename subgraph<G>::vertex_descriptor v_local, 429 const subgraph<G>& g) 430 { 431 return edge(u_local, v_local, g.m_graph); 432 } 433 434 //=========================================================================== 435 // Functions required by the MutableGraph concept 436 437 namespace detail { 438 439 template <typename Vertex, typename Edge, typename Graph> 440 void add_edge_recur_down 441 (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g); 442 443 template <typename Vertex, typename Edge, typename Children, typename G> children_add_edge(Vertex u_global,Vertex v_global,Edge e_global,Children & c,subgraph<G> * orig)444 void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global, 445 Children& c, subgraph<G>* orig) 446 { 447 for (typename Children::iterator i = c.begin(); i != c.end(); ++i) 448 if ((*i)->find_vertex(u_global).second 449 && (*i)->find_vertex(v_global).second) 450 add_edge_recur_down(u_global, v_global, e_global, **i, orig); 451 } 452 453 template <typename Vertex, typename Edge, typename Graph> add_edge_recur_down(Vertex u_global,Vertex v_global,Edge e_global,subgraph<Graph> & g,subgraph<Graph> * orig)454 void add_edge_recur_down 455 (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g, 456 subgraph<Graph>* orig) 457 { 458 if (&g != orig ) { 459 // add local edge only if u_global and v_global are in subgraph g 460 Vertex u_local, v_local; 461 bool u_in_subgraph, v_in_subgraph; 462 tie(u_local, u_in_subgraph) = g.find_vertex(u_global); 463 tie(v_local, v_in_subgraph) = g.find_vertex(v_global); 464 if (u_in_subgraph && v_in_subgraph) 465 g.local_add_edge(u_local, v_local, e_global); 466 } 467 children_add_edge(u_global, v_global, e_global, g.m_children, orig); 468 } 469 470 template <typename Vertex, typename Graph> 471 std::pair<typename subgraph<Graph>::edge_descriptor, bool> add_edge_recur_up(Vertex u_global,Vertex v_global,const typename Graph::edge_property_type & ep,subgraph<Graph> & g,subgraph<Graph> * orig)472 add_edge_recur_up(Vertex u_global, Vertex v_global, 473 const typename Graph::edge_property_type& ep, 474 subgraph<Graph>& g, subgraph<Graph>* orig) 475 { 476 if (g.is_root()) { 477 typename subgraph<Graph>::edge_descriptor e_global; 478 bool inserted; 479 tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph); 480 put(edge_index, g.m_graph, e_global, g.m_edge_counter++); 481 g.m_global_edge.push_back(e_global); 482 children_add_edge(u_global, v_global, e_global, g.m_children, orig); 483 return std::make_pair(e_global, inserted); 484 } else 485 return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig); 486 } 487 488 } // namespace detail 489 490 // Add an edge to the subgraph g, specified by the local vertex 491 // descriptors u and v. In addition, the edge will be added to any 492 // other subgraphs which contain vertex descriptors u and v. 493 494 template <typename G> 495 std::pair<typename subgraph<G>::edge_descriptor, bool> add_edge(typename subgraph<G>::vertex_descriptor u_local,typename subgraph<G>::vertex_descriptor v_local,const typename G::edge_property_type & ep,subgraph<G> & g)496 add_edge(typename subgraph<G>::vertex_descriptor u_local, 497 typename subgraph<G>::vertex_descriptor v_local, 498 const typename G::edge_property_type& ep, 499 subgraph<G>& g) 500 { 501 if (g.is_root()) // u_local and v_local are really global 502 return detail::add_edge_recur_up(u_local, v_local, ep, g, &g); 503 else { 504 typename subgraph<G>::edge_descriptor e_local, e_global; 505 bool inserted; 506 tie(e_global, inserted) = detail::add_edge_recur_up 507 (g.local_to_global(u_local), g.local_to_global(v_local), ep, g, &g); 508 e_local = g.local_add_edge(u_local, v_local, e_global); 509 return std::make_pair(e_local, inserted); 510 } 511 } 512 513 template <typename G> 514 std::pair<typename subgraph<G>::edge_descriptor, bool> add_edge(typename subgraph<G>::vertex_descriptor u,typename subgraph<G>::vertex_descriptor v,subgraph<G> & g)515 add_edge(typename subgraph<G>::vertex_descriptor u, 516 typename subgraph<G>::vertex_descriptor v, 517 subgraph<G>& g) 518 { 519 typename G::edge_property_type ep; 520 return add_edge(u, v, ep, g); 521 } 522 523 namespace detail { 524 525 //------------------------------------------------------------------------- 526 // implementation of remove_edge(u,v,g) 527 528 template <typename Vertex, typename Graph> 529 void remove_edge_recur_down(Vertex u_global, Vertex v_global, 530 subgraph<Graph>& g); 531 532 template <typename Vertex, typename Children> children_remove_edge(Vertex u_global,Vertex v_global,Children & c)533 void children_remove_edge(Vertex u_global, Vertex v_global, 534 Children& c) 535 { 536 for (typename Children::iterator i = c.begin(); i != c.end(); ++i) 537 if ((*i)->find_vertex(u_global).second 538 && (*i)->find_vertex(v_global).second) 539 remove_edge_recur_down(u_global, v_global, **i); 540 } 541 542 template <typename Vertex, typename Graph> remove_edge_recur_down(Vertex u_global,Vertex v_global,subgraph<Graph> & g)543 void remove_edge_recur_down(Vertex u_global, Vertex v_global, 544 subgraph<Graph>& g) 545 { 546 Vertex u_local, v_local; 547 u_local = g.m_local_vertex[u_global]; 548 v_local = g.m_local_vertex[v_global]; 549 remove_edge(u_local, v_local, g.m_graph); 550 children_remove_edge(u_global, v_global, g.m_children); 551 } 552 553 template <typename Vertex, typename Graph> remove_edge_recur_up(Vertex u_global,Vertex v_global,subgraph<Graph> & g)554 void remove_edge_recur_up(Vertex u_global, Vertex v_global, 555 subgraph<Graph>& g) 556 { 557 if (g.is_root()) { 558 remove_edge(u_global, v_global, g.m_graph); 559 children_remove_edge(u_global, v_global, g.m_children); 560 } else 561 remove_edge_recur_up(u_global, v_global, *g.m_parent); 562 } 563 564 //------------------------------------------------------------------------- 565 // implementation of remove_edge(e,g) 566 567 template <typename Edge, typename Graph> 568 void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g); 569 570 template <typename Edge, typename Children> children_remove_edge(Edge e_global,Children & c)571 void children_remove_edge(Edge e_global, Children& c) 572 { 573 for (typename Children::iterator i = c.begin(); i != c.end(); ++i) 574 if ((*i)->find_vertex(source(e_global, **i)).second 575 && (*i)->find_vertex(target(e_global, **i)).second) 576 remove_edge_recur_down(source(e_global, **i), 577 target(e_global, **i), **i); 578 } 579 580 template <typename Edge, typename Graph> remove_edge_recur_down(Edge e_global,subgraph<Graph> & g)581 void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g) 582 { 583 remove_edge(g.global_to_local(e_global), g.m_graph); 584 children_remove_edge(e_global, g.m_children); 585 } 586 587 template <typename Edge, typename Graph> remove_edge_recur_up(Edge e_global,subgraph<Graph> & g)588 void remove_edge_recur_up(Edge e_global, subgraph<Graph>& g) 589 { 590 if (g.is_root()) { 591 remove_edge(e_global, g.m_graph); 592 children_remove_edge(e_global, g.m_children); 593 } else 594 remove_edge_recur_up(e_global, *g.m_parent); 595 } 596 597 } // namespace detail 598 599 template <typename G> 600 void remove_edge(typename subgraph<G>::vertex_descriptor u_local,typename subgraph<G>::vertex_descriptor v_local,subgraph<G> & g)601 remove_edge(typename subgraph<G>::vertex_descriptor u_local, 602 typename subgraph<G>::vertex_descriptor v_local, 603 subgraph<G>& g) 604 { 605 if (g.is_root()) 606 detail::remove_edge_recur_up(u_local, v_local, g); 607 else 608 detail::remove_edge_recur_up(g.local_to_global(u_local), 609 g.local_to_global(v_local), g); 610 } 611 612 template <typename G> 613 void remove_edge(typename subgraph<G>::edge_descriptor e_local,subgraph<G> & g)614 remove_edge(typename subgraph<G>::edge_descriptor e_local, 615 subgraph<G>& g) 616 { 617 if (g.is_root()) 618 detail::remove_edge_recur_up(e_local, g); 619 else 620 detail::remove_edge_recur_up(g.local_to_global(e_local), g); 621 } 622 623 template <typename Predicate, typename G> 624 void remove_edge_if(Predicate p,subgraph<G> & g)625 remove_edge_if(Predicate p, subgraph<G>& g) 626 { 627 // This is wrong... 628 remove_edge_if(p, g.m_graph); 629 } 630 631 template <typename G> 632 void clear_vertex(typename subgraph<G>::vertex_descriptor v_local,subgraph<G> & g)633 clear_vertex(typename subgraph<G>::vertex_descriptor v_local, 634 subgraph<G>& g) 635 { 636 // this is wrong... 637 clear_vertex(v_local, g.m_graph); 638 } 639 640 namespace detail { 641 642 template <typename G> 643 typename subgraph<G>::vertex_descriptor add_vertex_recur_up(subgraph<G> & g)644 add_vertex_recur_up(subgraph<G>& g) 645 { 646 typename subgraph<G>::vertex_descriptor u_local, u_global; 647 if (g.is_root()) { 648 u_global = add_vertex(g.m_graph); 649 g.m_global_vertex.push_back(u_global); 650 } else { 651 u_global = add_vertex_recur_up(*g.m_parent); 652 u_local = add_vertex(g.m_graph); 653 g.m_global_vertex.push_back(u_global); 654 g.m_local_vertex[u_global] = u_local; 655 } 656 return u_global; 657 } 658 659 } // namespace detail 660 661 template <typename G> 662 typename subgraph<G>::vertex_descriptor add_vertex(subgraph<G> & g)663 add_vertex(subgraph<G>& g) 664 { 665 typename subgraph<G>::vertex_descriptor u_local, u_global; 666 if (g.is_root()) { 667 u_global = add_vertex(g.m_graph); 668 g.m_global_vertex.push_back(u_global); 669 u_local = u_global; 670 } else { 671 u_global = detail::add_vertex_recur_up(g.parent()); 672 u_local = add_vertex(g.m_graph); 673 g.m_global_vertex.push_back(u_global); 674 g.m_local_vertex[u_global] = u_local; 675 } 676 return u_local; 677 } 678 679 template <typename G> remove_vertex(typename subgraph<G>::vertex_descriptor u,subgraph<G> & g)680 void remove_vertex(typename subgraph<G>::vertex_descriptor u, 681 subgraph<G>& g) 682 { 683 // UNDER CONSTRUCTION 684 assert(false); 685 } 686 687 688 //=========================================================================== 689 // Functions required by the PropertyGraph concept 690 691 template <typename GraphPtr, typename PropertyMap, typename Tag> 692 class subgraph_global_property_map 693 : public put_get_helper< 694 typename property_traits<PropertyMap>::reference, 695 subgraph_global_property_map<GraphPtr, PropertyMap, Tag> > 696 { 697 typedef property_traits<PropertyMap> Traits; 698 public: 699 typedef typename Traits::category category; 700 typedef typename Traits::value_type value_type; 701 typedef typename Traits::key_type key_type; 702 typedef typename Traits::reference reference; 703 subgraph_global_property_map()704 subgraph_global_property_map() { } 705 subgraph_global_property_map(GraphPtr g)706 subgraph_global_property_map(GraphPtr g) 707 : m_g(g) { } 708 operator [](key_type e_local) const709 inline reference operator[](key_type e_local) const { 710 PropertyMap pmap = get(Tag(), m_g->root().m_graph); 711 if (m_g->m_parent == 0) 712 return pmap[e_local]; 713 else 714 return pmap[m_g->local_to_global(e_local)]; 715 } 716 GraphPtr m_g; 717 }; 718 719 template <typename GraphPtr, typename PropertyMap, typename Tag> 720 class subgraph_local_property_map 721 : public put_get_helper< 722 typename property_traits<PropertyMap>::reference, 723 subgraph_local_property_map<GraphPtr, PropertyMap, Tag> > 724 { 725 typedef property_traits<PropertyMap> Traits; 726 public: 727 typedef typename Traits::category category; 728 typedef typename Traits::value_type value_type; 729 typedef typename Traits::key_type key_type; 730 typedef typename Traits::reference reference; 731 subgraph_local_property_map()732 subgraph_local_property_map() { } 733 subgraph_local_property_map(GraphPtr g)734 subgraph_local_property_map(GraphPtr g) 735 : m_g(g) { } 736 operator [](key_type e_local) const737 inline reference operator[](key_type e_local) const { 738 PropertyMap pmap = get(Tag(), *m_g); 739 return pmap[e_local]; 740 } 741 GraphPtr m_g; 742 }; 743 744 namespace detail { 745 746 struct subgraph_any_pmap { 747 template <class Tag, class SubGraph, class Property> 748 class bind_ { 749 typedef typename SubGraph::graph_type Graph; 750 typedef SubGraph* SubGraphPtr; 751 typedef const SubGraph* const_SubGraphPtr; 752 typedef typename property_map<Graph, Tag>::type PMap; 753 typedef typename property_map<Graph, Tag>::const_type const_PMap; 754 public: 755 typedef subgraph_global_property_map<SubGraphPtr, PMap, Tag> type; 756 typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, Tag> 757 const_type; 758 }; 759 }; 760 struct subgraph_id_pmap { 761 template <class Tag, class SubGraph, class Property> 762 struct bind_ { 763 typedef typename SubGraph::graph_type Graph; 764 typedef SubGraph* SubGraphPtr; 765 typedef const SubGraph* const_SubGraphPtr; 766 typedef typename property_map<Graph, Tag>::type PMap; 767 typedef typename property_map<Graph, Tag>::const_type const_PMap; 768 public: 769 typedef subgraph_local_property_map<SubGraphPtr, PMap, Tag> type; 770 typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, Tag> 771 const_type; 772 }; 773 }; 774 template <class Tag> 775 struct subgraph_choose_pmap_helper { 776 typedef subgraph_any_pmap type; 777 }; 778 template <> 779 struct subgraph_choose_pmap_helper<vertex_index_t> { 780 typedef subgraph_id_pmap type; 781 }; 782 template <class Tag, class Graph, class Property> 783 struct subgraph_choose_pmap { 784 typedef typename subgraph_choose_pmap_helper<Tag>::type Helper; 785 typedef typename Helper::template bind_<Tag, Graph, Property> Bind; 786 typedef typename Bind::type type; 787 typedef typename Bind::const_type const_type; 788 }; 789 struct subgraph_property_generator { 790 template <class SubGraph, class Property, class Tag> 791 struct bind_ { 792 typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice; 793 typedef typename Choice::type type; 794 typedef typename Choice::const_type const_type; 795 }; 796 }; 797 798 } // namespace detail 799 800 template <> 801 struct vertex_property_selector<subgraph_tag> { 802 typedef detail::subgraph_property_generator type; 803 }; 804 805 template <> 806 struct edge_property_selector<subgraph_tag> { 807 typedef detail::subgraph_property_generator type; 808 }; 809 810 template <typename G, typename Property> 811 typename property_map< subgraph<G>, Property>::type get(Property,subgraph<G> & g)812 get(Property, subgraph<G>& g) 813 { 814 typedef typename property_map< subgraph<G>, Property>::type PMap; 815 return PMap(&g); 816 } 817 818 template <typename G, typename Property> 819 typename property_map< subgraph<G>, Property>::const_type get(Property,const subgraph<G> & g)820 get(Property, const subgraph<G>& g) 821 { 822 typedef typename property_map< subgraph<G>, Property>::const_type PMap; 823 return PMap(&g); 824 } 825 826 template <typename G, typename Property, typename Key> 827 typename property_traits< 828 typename property_map< subgraph<G>, Property>::const_type 829 >::value_type get(Property,const subgraph<G> & g,const Key & k)830 get(Property, const subgraph<G>& g, const Key& k) 831 { 832 typedef typename property_map< subgraph<G>, Property>::const_type PMap; 833 PMap pmap(&g); 834 return pmap[k]; 835 } 836 837 template <typename G, typename Property, typename Key, typename Value> 838 void put(Property,subgraph<G> & g,const Key & k,const Value & val)839 put(Property, subgraph<G>& g, const Key& k, const Value& val) 840 { 841 typedef typename property_map< subgraph<G>, Property>::type PMap; 842 PMap pmap(&g); 843 pmap[k] = val; 844 } 845 846 template <typename G, typename Tag> 847 inline 848 typename graph_property<G, Tag>::type& get_property(subgraph<G> & g,Tag tag)849 get_property(subgraph<G>& g, Tag tag) { 850 return get_property(g.m_graph, tag); 851 } 852 853 template <typename G, typename Tag> 854 inline 855 const typename graph_property<G, Tag>::type& get_property(const subgraph<G> & g,Tag tag)856 get_property(const subgraph<G>& g, Tag tag) { 857 return get_property(g.m_graph, tag); 858 } 859 860 //=========================================================================== 861 // Miscellaneous Functions 862 863 template <typename G> 864 typename subgraph<G>::vertex_descriptor vertex(typename subgraph<G>::vertices_size_type n,const subgraph<G> & g)865 vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g) 866 { 867 return vertex(n, g.m_graph); 868 } 869 870 } // namespace boost 871 872 #endif // BOOST_SUBGRAPH_HPP 873