ceph/src/boost/boost/graph/subgraph.hpp

   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 <boost/assert.hpp>
  20 #include <boost/graph/graph_traits.hpp>
  21 #include <boost/graph/graph_mutability_traits.hpp>
  22 #include <boost/graph/properties.hpp>
  23 #include <boost/iterator/indirect_iterator.hpp>
  24
  25 #include <boost/static_assert.hpp>
  26 #include <boost/assert.hpp>
  27 #include <boost/type_traits.hpp>
  28 #include <boost/mpl/if.hpp>
  29 #include <boost/mpl/or.hpp>
  30
  31 namespace boost
  32 {
  33
  34 struct subgraph_tag
  35 {
  36 };
  37
  38 /** @name Property Lookup
  39  * The local_property and global_property functions are used to create
  40  * structures that determine the lookup strategy for properties in subgraphs.
  41  * Note that the nested kind member is used to help interoperate with actual
  42  * Property types.
  43  */
  44 //@{
  45 template < typename T > struct local_property
  46 {
  47     typedef T kind;
  48     local_property(T x) : value(x) {}
  49     T value;
  50 };
  51
  52 template < typename T > inline local_property< T > local(T x)
  53 {
  54     return local_property< T >(x);
  55 }
  56
  57 template < typename T > struct global_property
  58 {
  59     typedef T kind;
  60     global_property(T x) : value(x) {}
  61     T value;
  62 };
  63
  64 template < typename T > inline global_property< T > global(T x)
  65 {
  66     return global_property< T >(x);
  67 }
  68 //@}
  69
  70 // Invariants of an induced subgraph:
  71 //   - If vertex u is in subgraph g, then u must be in g.parent().
  72 //   - If edge e is in subgraph g, then e must be in g.parent().
  73 //   - If edge e=(u,v) is in the root graph, then edge e
  74 //     is also in any subgraph that contains both vertex u and v.
  75
  76 // The Graph template parameter must have a vertex_index and edge_index
  77 // internal property. It is assumed that the vertex indices are assigned
  78 // automatically by the graph during a call to add_vertex(). It is not
  79 // assumed that the edge vertices are assigned automatically, they are
  80 // explicitly assigned here.
  81
  82 template < typename Graph > class subgraph
  83 {
  84     typedef graph_traits< Graph > Traits;
  85     typedef std::list< subgraph< Graph >* > ChildrenList;
  86
  87 public:
  88     // Graph requirements
  89     typedef typename Traits::vertex_descriptor vertex_descriptor;
  90     typedef typename Traits::edge_descriptor edge_descriptor;
  91     typedef typename Traits::directed_category directed_category;
  92     typedef typename Traits::edge_parallel_category edge_parallel_category;
  93     typedef typename Traits::traversal_category traversal_category;
  94
  95     // IncidenceGraph requirements
  96     typedef typename Traits::out_edge_iterator out_edge_iterator;
  97     typedef typename Traits::degree_size_type degree_size_type;
  98
  99     // AdjacencyGraph requirements
 100     typedef typename Traits::adjacency_iterator adjacency_iterator;
 101
 102     // VertexListGraph requirements
 103     typedef typename Traits::vertex_iterator vertex_iterator;
 104     typedef typename Traits::vertices_size_type vertices_size_type;
 105
 106     // EdgeListGraph requirements
 107     typedef typename Traits::edge_iterator edge_iterator;
 108     typedef typename Traits::edges_size_type edges_size_type;
 109
 110     typedef typename Traits::in_edge_iterator in_edge_iterator;
 111
 112     typedef typename edge_property_type< Graph >::type edge_property_type;
 113     typedef typename vertex_property_type< Graph >::type vertex_property_type;
 114     typedef subgraph_tag graph_tag;
 115     typedef Graph graph_type;
 116     typedef typename graph_property_type< Graph >::type graph_property_type;
 117
 118     // Create the main graph, the root of the subgraph tree
 119     subgraph() : m_parent(0), m_edge_counter(0) {}
 120
 121     subgraph(const graph_property_type& p)
 122     : m_graph(p), m_parent(0), m_edge_counter(0)
 123     {
 124     }
 125
 126     subgraph(vertices_size_type n,
 127         const graph_property_type& p = graph_property_type())
 128     : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
 129     {
 130         typename Graph::vertex_iterator v, v_end;
 131         vertices_size_type i = 0;
 132         for (boost::tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
 133             m_global_vertex[i++] = *v;
 134     }
 135
 136     // copy constructor
 137     subgraph(const subgraph& x) : m_parent(x.m_parent), m_edge_counter(0)
 138     {
 139         if (x.is_root())
 140         {
 141             m_graph = x.m_graph;
 142             m_edge_counter = x.m_edge_counter;
 143             m_global_vertex = x.m_global_vertex;
 144             m_global_edge = x.m_global_edge;
 145         }
 146         else
 147         {
 148             get_property(*this) = get_property(x);
 149             typename subgraph< Graph >::vertex_iterator vi, vi_end;
 150             boost::tie(vi, vi_end) = vertices(x);
 151             for (; vi != vi_end; ++vi)
 152             {
 153                 add_vertex(x.local_to_global(*vi), *this);
 154             }
 155         }
 156         // Do a deep copy (recursive).
 157         // Only the root graph is copied, the subgraphs contain
 158         // only references to the global vertices they own.
 159         typename subgraph< Graph >::children_iterator i, i_end;
 160         boost::tie(i, i_end) = x.children();
 161         for (; i != i_end; ++i)
 162         {
 163             m_children.push_back(new subgraph< Graph >(*i));
 164             m_children.back()->m_parent = this;
 165         }
 166     }
 167
 168     ~subgraph()
 169     {
 170         for (typename ChildrenList::iterator i = m_children.begin();
 171              i != m_children.end(); ++i)
 172         {
 173             delete *i;
 174         }
 175     }
 176
 177     // Return a null vertex descriptor for the graph.
 178     static vertex_descriptor null_vertex() { return Traits::null_vertex(); }
 179
 180     // Create a subgraph
 181     subgraph< Graph >& create_subgraph()
 182     {
 183         m_children.push_back(new subgraph< Graph >());
 184         m_children.back()->m_parent = this;
 185         return *m_children.back();
 186     }
 187
 188     // Create a subgraph with the specified vertex set.
 189     template < typename VertexIterator >
 190     subgraph< Graph >& create_subgraph(
 191         VertexIterator first, VertexIterator last)
 192     {
 193         m_children.push_back(new subgraph< Graph >());
 194         m_children.back()->m_parent = this;
 195         for (; first != last; ++first)
 196         {
 197             add_vertex(*first, *m_children.back());
 198         }
 199         return *m_children.back();
 200     }
 201
 202     // local <-> global descriptor conversion functions
 203     vertex_descriptor local_to_global(vertex_descriptor u_local) const
 204     {
 205         return is_root() ? u_local : m_global_vertex[u_local];
 206     }
 207
 208     vertex_descriptor global_to_local(vertex_descriptor u_global) const
 209     {
 210         vertex_descriptor u_local;
 211         bool in_subgraph;
 212         if (is_root())
 213             return u_global;
 214         boost::tie(u_local, in_subgraph) = this->find_vertex(u_global);
 215         BOOST_ASSERT(in_subgraph == true);
 216         return u_local;
 217     }
 218
 219     edge_descriptor local_to_global(edge_descriptor e_local) const
 220     {
 221         return is_root()
 222             ? e_local
 223             : m_global_edge[get(get(edge_index, m_graph), e_local)];
 224     }
 225
 226     edge_descriptor global_to_local(edge_descriptor e_global) const
 227     {
 228         return is_root() ? e_global
 229                          : (*m_local_edge.find(
 230                                 get(get(edge_index, root().m_graph), e_global)))
 231                                .second;
 232     }
 233
 234     // Is vertex u (of the root graph) contained in this subgraph?
 235     // If so, return the matching local vertex.
 236     std::pair< vertex_descriptor, bool > find_vertex(
 237         vertex_descriptor u_global) const
 238     {
 239         if (is_root())
 240             return std::make_pair(u_global, true);
 241         typename LocalVertexMap::const_iterator i
 242             = m_local_vertex.find(u_global);
 243         bool valid = i != m_local_vertex.end();
 244         return std::make_pair((valid ? (*i).second : null_vertex()), valid);
 245     }
 246
 247     // Is edge e (of the root graph) contained in this subgraph?
 248     // If so, return the matching local edge.
 249     std::pair< edge_descriptor, bool > find_edge(edge_descriptor e_global) const
 250     {
 251         if (is_root())
 252             return std::make_pair(e_global, true);
 253         typename LocalEdgeMap::const_iterator i
 254             = m_local_edge.find(get(get(edge_index, root().m_graph), e_global));
 255         bool valid = i != m_local_edge.end();
 256         return std::make_pair((valid ? (*i).second : edge_descriptor()), valid);
 257     }
 258
 259     // Return the parent graph.
 260     subgraph& parent() { return *m_parent; }
 261     const subgraph& parent() const { return *m_parent; }
 262
 263     // Return true if this is the root subgraph
 264     bool is_root() const { return m_parent == 0; }
 265
 266     // Return the root graph of the subgraph tree.
 267     subgraph& root() { return is_root() ? *this : m_parent->root(); }
 268
 269     const subgraph& root() const
 270     {
 271         return is_root() ? *this : m_parent->root();
 272     }
 273
 274     // Return the children subgraphs of this graph/subgraph.
 275     // Use a list of pointers because the VC++ std::list doesn't like
 276     // storing incomplete type.
 277     typedef indirect_iterator< typename ChildrenList::const_iterator,
 278         subgraph< Graph >, std::bidirectional_iterator_tag >
 279         children_iterator;
 280
 281     typedef indirect_iterator< typename ChildrenList::const_iterator,
 282         subgraph< Graph > const, std::bidirectional_iterator_tag >
 283         const_children_iterator;
 284
 285     std::pair< const_children_iterator, const_children_iterator >
 286     children() const
 287     {
 288         return std::make_pair(const_children_iterator(m_children.begin()),
 289             const_children_iterator(m_children.end()));
 290     }
 291
 292     std::pair< children_iterator, children_iterator > children()
 293     {
 294         return std::make_pair(children_iterator(m_children.begin()),
 295             children_iterator(m_children.end()));
 296     }
 297
 298     std::size_t num_children() const { return m_children.size(); }
 299
 300 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 301     // Defualt property access delegates the lookup to global properties.
 302     template < typename Descriptor >
 303     typename graph::detail::bundled_result< Graph, Descriptor >::type&
 304     operator[](Descriptor x)
 305     {
 306         return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)];
 307     }
 308
 309     template < typename Descriptor >
 310     typename graph::detail::bundled_result< Graph, Descriptor >::type const&
 311     operator[](Descriptor x) const
 312     {
 313         return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)];
 314     }
 315
 316     // Local property access returns the local property of the given descripor.
 317     template < typename Descriptor >
 318     typename graph::detail::bundled_result< Graph, Descriptor >::type&
 319     operator[](local_property< Descriptor > x)
 320     {
 321         return m_graph[x.value];
 322     }
 323
 324     template < typename Descriptor >
 325     typename graph::detail::bundled_result< Graph, Descriptor >::type const&
 326     operator[](local_property< Descriptor > x) const
 327     {
 328         return m_graph[x.value];
 329     }
 330
 331     // Global property access returns the global property associated with the
 332     // given descriptor. This is an alias for the default bundled property
 333     // access operations.
 334     template < typename Descriptor >
 335     typename graph::detail::bundled_result< Graph, Descriptor >::type&
 336     operator[](global_property< Descriptor > x)
 337     {
 338         return (*this)[x.value];
 339     }
 340
 341     template < typename Descriptor >
 342     typename graph::detail::bundled_result< Graph, Descriptor >::type const&
 343     operator[](global_property< Descriptor > x) const
 344     {
 345         return (*this)[x.value];
 346     }
 347
 348 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 349
 350     //  private:
 351     typedef typename property_map< Graph, edge_index_t >::type EdgeIndexMap;
 352     typedef
 353         typename property_traits< EdgeIndexMap >::value_type edge_index_type;
 354     BOOST_STATIC_ASSERT((!is_same< edge_index_type,
 355                          boost::detail::error_property_not_found >::value));
 356
 357 private:
 358     typedef std::vector< vertex_descriptor > GlobalVertexList;
 359     typedef std::vector< edge_descriptor > GlobalEdgeList;
 360     typedef std::map< vertex_descriptor, vertex_descriptor > LocalVertexMap;
 361     typedef std::map< edge_index_type, edge_descriptor > LocalEdgeMap;
 362     // TODO: Should the LocalVertexMap be: map<index_type, descriptor>?
 363     // TODO: Can we relax the indexing requirement if both descriptors are
 364     // LessThanComparable?
 365     // TODO: Should we really be using unorderd_map for improved lookup times?
 366
 367 public: // Probably shouldn't be public....
 368     Graph m_graph;
 369     subgraph< Graph >* m_parent;
 370     edge_index_type m_edge_counter; // for generating unique edge indices
 371     ChildrenList m_children;
 372     GlobalVertexList m_global_vertex; // local -> global
 373     LocalVertexMap m_local_vertex; // global -> local
 374     GlobalEdgeList m_global_edge; // local -> global
 375     LocalEdgeMap m_local_edge; // global -> local
 376
 377     edge_descriptor local_add_edge(vertex_descriptor u_local,
 378         vertex_descriptor v_local, edge_descriptor e_global)
 379     {
 380         edge_descriptor e_local;
 381         bool inserted;
 382         boost::tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
 383         put(edge_index, m_graph, e_local, m_edge_counter++);
 384         m_global_edge.push_back(e_global);
 385         m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
 386         return e_local;
 387     }
 388 };
 389
 390 template < typename Graph >
 391 struct vertex_bundle_type< subgraph< Graph > > : vertex_bundle_type< Graph >
 392 {
 393 };
 394
 395 template < typename Graph >
 396 struct edge_bundle_type< subgraph< Graph > > : edge_bundle_type< Graph >
 397 {
 398 };
 399
 400 template < typename Graph >
 401 struct graph_bundle_type< subgraph< Graph > > : graph_bundle_type< Graph >
 402 {
 403 };
 404
 405 //===========================================================================
 406 // Functions special to the Subgraph Class
 407
 408 template < typename G >
 409 typename subgraph< G >::vertex_descriptor add_vertex(
 410     typename subgraph< G >::vertex_descriptor u_global, subgraph< G >& g)
 411 {
 412     BOOST_ASSERT(!g.is_root());
 413     typename subgraph< G >::vertex_descriptor u_local;
 414     bool exists_local;
 415     boost::tie(u_local, exists_local) = g.find_vertex(u_global);
 416
 417     if (!exists_local)
 418     {
 419         typename subgraph< G >::vertex_descriptor v_global;
 420         typename subgraph< G >::edge_descriptor e_global;
 421         // call recursion for parent subgraph
 422         if (!g.parent().is_root())
 423             add_vertex(u_global, g.parent());
 424
 425         u_local = add_vertex(g.m_graph);
 426         g.m_global_vertex.push_back(u_global);
 427         g.m_local_vertex[u_global] = u_local;
 428
 429         subgraph< G >& r = g.root();
 430
 431         // remember edge global and local maps
 432         {
 433             typename subgraph< G >::out_edge_iterator ei, ei_end;
 434             for (boost::tie(ei, ei_end) = out_edges(u_global, r); ei != ei_end;
 435                  ++ei)
 436             {
 437                 e_global = *ei;
 438                 v_global = target(e_global, r);
 439                 if (g.find_vertex(v_global).second == true)
 440                     g.local_add_edge(
 441                         u_local, g.global_to_local(v_global), e_global);
 442             }
 443         }
 444         if (is_directed(g))
 445         { // not necessary for undirected graph
 446             typename subgraph< G >::vertex_iterator vi, vi_end;
 447             typename subgraph< G >::out_edge_iterator ei, ei_end;
 448             for (boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi)
 449             {
 450                 v_global = *vi;
 451                 if (v_global == u_global)
 452                     continue; // don't insert self loops twice!
 453                 if (!g.find_vertex(v_global).second)
 454                     continue; // not a subgraph vertex => try next one
 455                 for (boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end;
 456                      ++ei)
 457                 {
 458                     e_global = *ei;
 459                     if (target(e_global, r) == u_global)
 460                     {
 461                         g.local_add_edge(
 462                             g.global_to_local(v_global), u_local, e_global);
 463                     }
 464                 }
 465             }
 466         }
 467     }
 468     return u_local;
 469 }
 470
 471 // NOTE: Descriptors are local unless otherwise noted.
 472
 473 //===========================================================================
 474 // Functions required by the IncidenceGraph concept
 475
 476 template < typename G >
 477 std::pair< typename graph_traits< G >::out_edge_iterator,
 478     typename graph_traits< G >::out_edge_iterator >
 479 out_edges(
 480     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
 481 {
 482     return out_edges(v, g.m_graph);
 483 }
 484
 485 template < typename G >
 486 typename graph_traits< G >::degree_size_type out_degree(
 487     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
 488 {
 489     return out_degree(v, g.m_graph);
 490 }
 491
 492 template < typename G >
 493 typename graph_traits< G >::vertex_descriptor source(
 494     typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g)
 495 {
 496     return source(e, g.m_graph);
 497 }
 498
 499 template < typename G >
 500 typename graph_traits< G >::vertex_descriptor target(
 501     typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g)
 502 {
 503     return target(e, g.m_graph);
 504 }
 505
 506 //===========================================================================
 507 // Functions required by the BidirectionalGraph concept
 508
 509 template < typename G >
 510 std::pair< typename graph_traits< G >::in_edge_iterator,
 511     typename graph_traits< G >::in_edge_iterator >
 512 in_edges(
 513     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
 514 {
 515     return in_edges(v, g.m_graph);
 516 }
 517
 518 template < typename G >
 519 typename graph_traits< G >::degree_size_type in_degree(
 520     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
 521 {
 522     return in_degree(v, g.m_graph);
 523 }
 524
 525 template < typename G >
 526 typename graph_traits< G >::degree_size_type degree(
 527     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
 528 {
 529     return degree(v, g.m_graph);
 530 }
 531
 532 //===========================================================================
 533 // Functions required by the AdjacencyGraph concept
 534
 535 template < typename G >
 536 std::pair< typename subgraph< G >::adjacency_iterator,
 537     typename subgraph< G >::adjacency_iterator >
 538 adjacent_vertices(
 539     typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g)
 540 {
 541     return adjacent_vertices(v, g.m_graph);
 542 }
 543
 544 //===========================================================================
 545 // Functions required by the VertexListGraph concept
 546
 547 template < typename G >
 548 std::pair< typename subgraph< G >::vertex_iterator,
 549     typename subgraph< G >::vertex_iterator >
 550 vertices(const subgraph< G >& g)
 551 {
 552     return vertices(g.m_graph);
 553 }
 554
 555 template < typename G >
 556 typename subgraph< G >::vertices_size_type num_vertices(const subgraph< G >& g)
 557 {
 558     return num_vertices(g.m_graph);
 559 }
 560
 561 //===========================================================================
 562 // Functions required by the EdgeListGraph concept
 563
 564 template < typename G >
 565 std::pair< typename subgraph< G >::edge_iterator,
 566     typename subgraph< G >::edge_iterator >
 567 edges(const subgraph< G >& g)
 568 {
 569     return edges(g.m_graph);
 570 }
 571
 572 template < typename G >
 573 typename subgraph< G >::edges_size_type num_edges(const subgraph< G >& g)
 574 {
 575     return num_edges(g.m_graph);
 576 }
 577
 578 //===========================================================================
 579 // Functions required by the AdjacencyMatrix concept
 580
 581 template < typename G >
 582 std::pair< typename subgraph< G >::edge_descriptor, bool > edge(
 583     typename subgraph< G >::vertex_descriptor u,
 584     typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g)
 585 {
 586     return edge(u, v, g.m_graph);
 587 }
 588
 589 //===========================================================================
 590 // Functions required by the MutableGraph concept
 591
 592 namespace detail
 593 {
 594
 595     template < typename Vertex, typename Edge, typename Graph >
 596     void add_edge_recur_down(
 597         Vertex u_global, Vertex v_global, Edge e_global, subgraph< Graph >& g);
 598
 599     template < typename Vertex, typename Edge, typename Children, typename G >
 600     void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
 601         Children& c, subgraph< G >* orig)
 602     {
 603         for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
 604         {
 605             if ((*i)->find_vertex(u_global).second
 606                 && (*i)->find_vertex(v_global).second)
 607             {
 608                 add_edge_recur_down(u_global, v_global, e_global, **i, orig);
 609             }
 610         }
 611     }
 612
 613     template < typename Vertex, typename Edge, typename Graph >
 614     void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
 615         subgraph< Graph >& g, subgraph< Graph >* orig)
 616     {
 617         if (&g != orig)
 618         {
 619             // add local edge only if u_global and v_global are in subgraph g
 620             Vertex u_local, v_local;
 621             bool u_in_subgraph, v_in_subgraph;
 622             boost::tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
 623             boost::tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
 624             if (u_in_subgraph && v_in_subgraph)
 625             {
 626                 g.local_add_edge(u_local, v_local, e_global);
 627             }
 628         }
 629         children_add_edge(u_global, v_global, e_global, g.m_children, orig);
 630     }
 631
 632     template < typename Vertex, typename Graph >
 633     std::pair< typename subgraph< Graph >::edge_descriptor, bool >
 634     add_edge_recur_up(Vertex u_global, Vertex v_global,
 635         const typename Graph::edge_property_type& ep, subgraph< Graph >& g,
 636         subgraph< Graph >* orig)
 637     {
 638         if (g.is_root())
 639         {
 640             typename subgraph< Graph >::edge_descriptor e_global;
 641             bool inserted;
 642             boost::tie(e_global, inserted)
 643                 = add_edge(u_global, v_global, ep, g.m_graph);
 644             put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
 645             g.m_global_edge.push_back(e_global);
 646             children_add_edge(u_global, v_global, e_global, g.m_children, orig);
 647             return std::make_pair(e_global, inserted);
 648         }
 649         else
 650         {
 651             return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
 652         }
 653     }
 654
 655 } // namespace detail
 656
 657 // Add an edge to the subgraph g, specified by the local vertex descriptors u
 658 // and v. In addition, the edge will be added to any (all) other subgraphs that
 659 // contain vertex descriptors u and v.
 660
 661 template < typename G >
 662 std::pair< typename subgraph< G >::edge_descriptor, bool > add_edge(
 663     typename subgraph< G >::vertex_descriptor u,
 664     typename subgraph< G >::vertex_descriptor v,
 665     const typename G::edge_property_type& ep, subgraph< G >& g)
 666 {
 667     if (g.is_root())
 668     {
 669         // u and v are really global
 670         return detail::add_edge_recur_up(u, v, ep, g, &g);
 671     }
 672     else
 673     {
 674         typename subgraph< G >::edge_descriptor e_local, e_global;
 675         bool inserted;
 676         boost::tie(e_global, inserted) = detail::add_edge_recur_up(
 677             g.local_to_global(u), g.local_to_global(v), ep, g, &g);
 678         e_local = g.local_add_edge(u, v, e_global);
 679         return std::make_pair(e_local, inserted);
 680     }
 681 }
 682
 683 template < typename G >
 684 std::pair< typename subgraph< G >::edge_descriptor, bool > add_edge(
 685     typename subgraph< G >::vertex_descriptor u,
 686     typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
 687 {
 688     return add_edge(u, v, typename G::edge_property_type(), g);
 689 }
 690
 691 namespace detail
 692 {
 693     //-------------------------------------------------------------------------
 694     // implementation of remove_edge(u,v,g)
 695     template < typename Vertex, typename Graph >
 696     void remove_edge_recur_down(
 697         Vertex u_global, Vertex v_global, subgraph< Graph >& g);
 698
 699     template < typename Vertex, typename Children >
 700     void children_remove_edge(Vertex u_global, Vertex v_global, Children& c)
 701     {
 702         for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
 703         {
 704             if ((*i)->find_vertex(u_global).second
 705                 && (*i)->find_vertex(v_global).second)
 706             {
 707                 remove_edge_recur_down(u_global, v_global, **i);
 708             }
 709         }
 710     }
 711
 712     template < typename Vertex, typename Graph >
 713     void remove_edge_recur_down(
 714         Vertex u_global, Vertex v_global, subgraph< Graph >& g)
 715     {
 716         Vertex u_local, v_local;
 717         u_local = g.m_local_vertex[u_global];
 718         v_local = g.m_local_vertex[v_global];
 719         remove_edge(u_local, v_local, g.m_graph);
 720         children_remove_edge(u_global, v_global, g.m_children);
 721     }
 722
 723     template < typename Vertex, typename Graph >
 724     void remove_edge_recur_up(
 725         Vertex u_global, Vertex v_global, subgraph< Graph >& g)
 726     {
 727         if (g.is_root())
 728         {
 729             remove_edge(u_global, v_global, g.m_graph);
 730             children_remove_edge(u_global, v_global, g.m_children);
 731         }
 732         else
 733         {
 734             remove_edge_recur_up(u_global, v_global, *g.m_parent);
 735         }
 736     }
 737
 738     //-------------------------------------------------------------------------
 739     // implementation of remove_edge(e,g)
 740
 741     template < typename G, typename Edge, typename Children >
 742     void children_remove_edge(Edge e_global, Children& c)
 743     {
 744         for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
 745         {
 746             std::pair< typename subgraph< G >::edge_descriptor, bool > found
 747                 = (*i)->find_edge(e_global);
 748             if (!found.second)
 749             {
 750                 continue;
 751             }
 752             children_remove_edge< G >(e_global, (*i)->m_children);
 753             remove_edge(found.first, (*i)->m_graph);
 754         }
 755     }
 756
 757 } // namespace detail
 758
 759 template < typename G >
 760 void remove_edge(typename subgraph< G >::vertex_descriptor u,
 761     typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
 762 {
 763     if (g.is_root())
 764     {
 765         detail::remove_edge_recur_up(u, v, g);
 766     }
 767     else
 768     {
 769         detail::remove_edge_recur_up(
 770             g.local_to_global(u), g.local_to_global(v), g);
 771     }
 772 }
 773
 774 template < typename G >
 775 void remove_edge(typename subgraph< G >::edge_descriptor e, subgraph< G >& g)
 776 {
 777     typename subgraph< G >::edge_descriptor e_global = g.local_to_global(e);
 778 #ifndef NDEBUG
 779     std::pair< typename subgraph< G >::edge_descriptor, bool > fe
 780         = g.find_edge(e_global);
 781     BOOST_ASSERT(fe.second && fe.first == e);
 782 #endif // NDEBUG
 783     subgraph< G >& root = g.root(); // chase to root
 784     detail::children_remove_edge< G >(e_global, root.m_children);
 785     remove_edge(e_global, root.m_graph); // kick edge from root
 786 }
 787
 788 // This is slow, but there may not be a good way to do it safely otherwise
 789 template < typename Predicate, typename G >
 790 void remove_edge_if(Predicate p, subgraph< G >& g)
 791 {
 792     while (true)
 793     {
 794         bool any_removed = false;
 795         typedef typename subgraph< G >::edge_iterator ei_type;
 796         for (std::pair< ei_type, ei_type > ep = edges(g); ep.first != ep.second;
 797              ++ep.first)
 798         {
 799             if (p(*ep.first))
 800             {
 801                 any_removed = true;
 802                 remove_edge(*ep.first, g);
 803                 break; /* Since iterators may be invalidated */
 804             }
 805         }
 806         if (!any_removed)
 807             break;
 808     }
 809 }
 810
 811 template < typename G >
 812 void clear_vertex(typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
 813 {
 814     while (true)
 815     {
 816         typedef typename subgraph< G >::out_edge_iterator oei_type;
 817         std::pair< oei_type, oei_type > p = out_edges(v, g);
 818         if (p.first == p.second)
 819             break;
 820         remove_edge(*p.first, g);
 821     }
 822 }
 823
 824 namespace detail
 825 {
 826     template < typename G >
 827     typename subgraph< G >::vertex_descriptor add_vertex_recur_up(
 828         subgraph< G >& g)
 829     {
 830         typename subgraph< G >::vertex_descriptor u_local, u_global;
 831         if (g.is_root())
 832         {
 833             u_global = add_vertex(g.m_graph);
 834             g.m_global_vertex.push_back(u_global);
 835         }
 836         else
 837         {
 838             u_global = add_vertex_recur_up(*g.m_parent);
 839             u_local = add_vertex(g.m_graph);
 840             g.m_global_vertex.push_back(u_global);
 841             g.m_local_vertex[u_global] = u_local;
 842         }
 843         return u_global;
 844     }
 845 } // namespace detail
 846
 847 template < typename G >
 848 typename subgraph< G >::vertex_descriptor add_vertex(subgraph< G >& g)
 849 {
 850     typename subgraph< G >::vertex_descriptor u_local, u_global;
 851     if (g.is_root())
 852     {
 853         u_global = add_vertex(g.m_graph);
 854         g.m_global_vertex.push_back(u_global);
 855         u_local = u_global;
 856     }
 857     else
 858     {
 859         u_global = detail::add_vertex_recur_up(g.parent());
 860         u_local = add_vertex(g.m_graph);
 861         g.m_global_vertex.push_back(u_global);
 862         g.m_local_vertex[u_global] = u_local;
 863     }
 864     return u_local;
 865 }
 866
 867 #if 0
 868 // TODO: Under Construction
 869 template <typename G>
 870 void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
 871 { BOOST_ASSERT(false); }
 872 #endif
 873
 874 //===========================================================================
 875 // Functions required by the PropertyGraph concept
 876
 877 /**
 878  * The global property map returns the global properties associated with local
 879  * descriptors.
 880  */
 881 template < typename GraphPtr, typename PropertyMap, typename Tag >
 882 class subgraph_global_property_map
 883 : public put_get_helper< typename property_traits< PropertyMap >::reference,
 884       subgraph_global_property_map< GraphPtr, PropertyMap, Tag > >
 885 {
 886     typedef property_traits< PropertyMap > Traits;
 887
 888 public:
 889     typedef typename mpl::if_<
 890         is_const< typename remove_pointer< GraphPtr >::type >,
 891         readable_property_map_tag, typename Traits::category >::type category;
 892     typedef typename Traits::value_type value_type;
 893     typedef typename Traits::key_type key_type;
 894     typedef typename Traits::reference reference;
 895
 896     subgraph_global_property_map() {}
 897
 898     subgraph_global_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {}
 899
 900     reference operator[](key_type e) const
 901     {
 902         PropertyMap pmap = get(m_tag, m_g->root().m_graph);
 903         return m_g->is_root() ? pmap[e] : pmap[m_g->local_to_global(e)];
 904     }
 905
 906     GraphPtr m_g;
 907     Tag m_tag;
 908 };
 909
 910 /**
 911  * The local property map returns the local property associated with the local
 912  * descriptors.
 913  */
 914 template < typename GraphPtr, typename PropertyMap, typename Tag >
 915 class subgraph_local_property_map
 916 : public put_get_helper< typename property_traits< PropertyMap >::reference,
 917       subgraph_local_property_map< GraphPtr, PropertyMap, Tag > >
 918 {
 919     typedef property_traits< PropertyMap > Traits;
 920
 921 public:
 922     typedef typename mpl::if_<
 923         is_const< typename remove_pointer< GraphPtr >::type >,
 924         readable_property_map_tag, typename Traits::category >::type category;
 925     typedef typename Traits::value_type value_type;
 926     typedef typename Traits::key_type key_type;
 927     typedef typename Traits::reference reference;
 928
 929     typedef Tag tag;
 930     typedef PropertyMap pmap;
 931
 932     subgraph_local_property_map() {}
 933
 934     subgraph_local_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {}
 935
 936     reference operator[](key_type e) const
 937     {
 938         // Get property map on the underlying graph.
 939         PropertyMap pmap = get(m_tag, m_g->m_graph);
 940         return pmap[e];
 941     }
 942
 943     GraphPtr m_g;
 944     Tag m_tag;
 945 };
 946
 947 namespace detail
 948 {
 949     // Extract the actual tags from local or global property maps so we don't
 950     // try to find non-properties.
 951     template < typename P > struct extract_lg_tag
 952     {
 953         typedef P type;
 954     };
 955     template < typename P > struct extract_lg_tag< local_property< P > >
 956     {
 957         typedef P type;
 958     };
 959     template < typename P > struct extract_lg_tag< global_property< P > >
 960     {
 961         typedef P type;
 962     };
 963
 964     // NOTE: Mysterious Property template parameter unused in both metafunction
 965     // classes.
 966     struct subgraph_global_pmap
 967     {
 968         template < class Tag, class SubGraph, class Property > struct bind_
 969         {
 970             typedef typename SubGraph::graph_type Graph;
 971             typedef SubGraph* SubGraphPtr;
 972             typedef const SubGraph* const_SubGraphPtr;
 973             typedef typename extract_lg_tag< Tag >::type TagType;
 974             typedef typename property_map< Graph, TagType >::type PMap;
 975             typedef
 976                 typename property_map< Graph, TagType >::const_type const_PMap;
 977
 978         public:
 979             typedef subgraph_global_property_map< SubGraphPtr, PMap, TagType >
 980                 type;
 981             typedef subgraph_global_property_map< const_SubGraphPtr, const_PMap,
 982                 TagType >
 983                 const_type;
 984         };
 985     };
 986
 987     struct subgraph_local_pmap
 988     {
 989         template < class Tag, class SubGraph, class Property > struct bind_
 990         {
 991             typedef typename SubGraph::graph_type Graph;
 992             typedef SubGraph* SubGraphPtr;
 993             typedef const SubGraph* const_SubGraphPtr;
 994             typedef typename extract_lg_tag< Tag >::type TagType;
 995             typedef typename property_map< Graph, TagType >::type PMap;
 996             typedef
 997                 typename property_map< Graph, TagType >::const_type const_PMap;
 998
 999         public:
1000             typedef subgraph_local_property_map< SubGraphPtr, PMap, TagType >
1001                 type;
1002             typedef subgraph_local_property_map< const_SubGraphPtr, const_PMap,
1003                 TagType >
1004                 const_type;
1005         };
1006     };
1007
1008     // These metafunctions select the corresponding metafunctions above, and
1009     // are used by the choose_pmap metafunction below to specialize the choice
1010     // of local/global property map. By default, we defer to the global
1011     // property.
1012     template < class Tag > struct subgraph_choose_pmap_helper
1013     {
1014         typedef subgraph_global_pmap type;
1015     };
1016     template < class Tag >
1017     struct subgraph_choose_pmap_helper< local_property< Tag > >
1018     {
1019         typedef subgraph_local_pmap type;
1020     };
1021     template < class Tag >
1022     struct subgraph_choose_pmap_helper< global_property< Tag > >
1023     {
1024         typedef subgraph_global_pmap type;
1025     };
1026
1027     // As above, unless we're requesting vertex_index_t. Then it's always a
1028     // local property map. This enables the correct translation of descriptors
1029     // between local and global layers.
1030     template <> struct subgraph_choose_pmap_helper< vertex_index_t >
1031     {
1032         typedef subgraph_local_pmap type;
1033     };
1034     template <>
1035     struct subgraph_choose_pmap_helper< local_property< vertex_index_t > >
1036     {
1037         typedef subgraph_local_pmap type;
1038     };
1039     template <>
1040     struct subgraph_choose_pmap_helper< global_property< vertex_index_t > >
1041     {
1042         typedef subgraph_local_pmap type;
1043     };
1044
1045     // Determine the kind of property. If SameType<Tag, vertex_index_t>, then
1046     // the property lookup is always local. Otherwise, the lookup is global.
1047     // NOTE: Property parameter is basically unused.
1048     template < class Tag, class Graph, class Property >
1049     struct subgraph_choose_pmap
1050     {
1051         typedef typename subgraph_choose_pmap_helper< Tag >::type Helper;
1052         typedef typename Helper::template bind_< Tag, Graph, Property > Bind;
1053         typedef typename Bind::type type;
1054         typedef typename Bind::const_type const_type;
1055     };
1056
1057     // Used by the vertex/edge property selectors to determine the kind(s) of
1058     // property maps used by the property_map type generator.
1059     struct subgraph_property_generator
1060     {
1061         template < class SubGraph, class Property, class Tag > struct bind_
1062         {
1063             typedef subgraph_choose_pmap< Tag, SubGraph, Property > Choice;
1064             typedef typename Choice::type type;
1065             typedef typename Choice::const_type const_type;
1066         };
1067     };
1068
1069 } // namespace detail
1070
1071 template <> struct vertex_property_selector< subgraph_tag >
1072 {
1073     typedef detail::subgraph_property_generator type;
1074 };
1075
1076 template <> struct edge_property_selector< subgraph_tag >
1077 {
1078     typedef detail::subgraph_property_generator type;
1079 };
1080
1081 // ==================================================
1082 // get(p, g), get(p, g, k), and put(p, g, k, v)
1083 // ==================================================
1084 template < typename G, typename Property >
1085 typename property_map< subgraph< G >, Property >::type get(
1086     Property p, subgraph< G >& g)
1087 {
1088     typedef typename property_map< subgraph< G >, Property >::type PMap;
1089     return PMap(&g, p);
1090 }
1091
1092 template < typename G, typename Property >
1093 typename property_map< subgraph< G >, Property >::const_type get(
1094     Property p, const subgraph< G >& g)
1095 {
1096     typedef typename property_map< subgraph< G >, Property >::const_type PMap;
1097     return PMap(&g, p);
1098 }
1099
1100 template < typename G, typename Property, typename Key >
1101 typename property_traits<
1102     typename property_map< subgraph< G >, Property >::const_type >::value_type
1103 get(Property p, const subgraph< G >& g, const Key& k)
1104 {
1105     typedef typename property_map< subgraph< G >, Property >::const_type PMap;
1106     PMap pmap(&g, p);
1107     return pmap[k];
1108 }
1109
1110 template < typename G, typename Property, typename Key, typename Value >
1111 void put(Property p, subgraph< G >& g, const Key& k, const Value& val)
1112 {
1113     typedef typename property_map< subgraph< G >, Property >::type PMap;
1114     PMap pmap(&g, p);
1115     pmap[k] = val;
1116 }
1117
1118 // ==================================================
1119 // get(global(p), g)
1120 // NOTE: get(global(p), g, k) and put(global(p), g, k, v) not supported
1121 // ==================================================
1122 template < typename G, typename Property >
1123 typename property_map< subgraph< G >, global_property< Property > >::type get(
1124     global_property< Property > p, subgraph< G >& g)
1125 {
1126     typedef typename property_map< subgraph< G >,
1127         global_property< Property > >::type Map;
1128     return Map(&g, p.value);
1129 }
1130
1131 template < typename G, typename Property >
1132 typename property_map< subgraph< G >, global_property< Property > >::const_type
1133 get(global_property< Property > p, const subgraph< G >& g)
1134 {
1135     typedef typename property_map< subgraph< G >,
1136         global_property< Property > >::const_type Map;
1137     return Map(&g, p.value);
1138 }
1139
1140 // ==================================================
1141 // get(local(p), g)
1142 // NOTE: get(local(p), g, k) and put(local(p), g, k, v) not supported
1143 // ==================================================
1144 template < typename G, typename Property >
1145 typename property_map< subgraph< G >, local_property< Property > >::type get(
1146     local_property< Property > p, subgraph< G >& g)
1147 {
1148     typedef
1149         typename property_map< subgraph< G >, local_property< Property > >::type
1150             Map;
1151     return Map(&g, p.value);
1152 }
1153
1154 template < typename G, typename Property >
1155 typename property_map< subgraph< G >, local_property< Property > >::const_type
1156 get(local_property< Property > p, const subgraph< G >& g)
1157 {
1158     typedef typename property_map< subgraph< G >,
1159         local_property< Property > >::const_type Map;
1160     return Map(&g, p.value);
1161 }
1162
1163 template < typename G, typename Tag >
1164 inline typename graph_property< G, Tag >::type& get_property(
1165     subgraph< G >& g, Tag tag)
1166 {
1167     return get_property(g.m_graph, tag);
1168 }
1169
1170 template < typename G, typename Tag >
1171 inline const typename graph_property< G, Tag >::type& get_property(
1172     const subgraph< G >& g, Tag tag)
1173 {
1174     return get_property(g.m_graph, tag);
1175 }
1176
1177 //===========================================================================
1178 // Miscellaneous Functions
1179
1180 template < typename G >
1181 typename subgraph< G >::vertex_descriptor vertex(
1182     typename subgraph< G >::vertices_size_type n, const subgraph< G >& g)
1183 {
1184     return vertex(n, g.m_graph);
1185 }
1186
1187 //===========================================================================
1188 // Mutability Traits
1189 // Just pull the mutability traits form the underlying graph. Note that this
1190 // will probably fail (badly) for labeled graphs.
1191 template < typename G > struct graph_mutability_traits< subgraph< G > >
1192 {
1193     typedef typename graph_mutability_traits< G >::category category;
1194 };
1195
1196 } // namespace boost
1197
1198 #endif // BOOST_SUBGRAPH_HPP