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