epoc32/include/stdapis/boost/graph/subgraph.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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 
    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
    88     subgraph()
    89       : m_parent(0), m_edge_counter(0)
    90     { }
    91     subgraph(const graph_property_type& p)
    92       : m_graph(p), m_parent(0), m_edge_counter(0)
    93     { }
    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
   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 
   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
   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>
   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
   145     vertex_descriptor local_to_global(vertex_descriptor u_local) const
   146     {
   147       return m_global_vertex[u_local];
   148     }
   149     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     }
   156     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     }
   160     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>
   169     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.
   178     subgraph& parent() { return *m_parent; }
   179     const subgraph& parent() const { return *m_parent; }
   180 
   181     bool is_root() const { return m_parent == 0; }
   182 
   183     // Return the root graph of the subgraph tree.
   184     subgraph& root() {
   185       if (this->is_root())
   186         return *this;
   187       else
   188         return m_parent->root();
   189     }
   190     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>
   215     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>
   222     children()
   223     {
   224       return std::make_pair(children_iterator(m_children.begin()),
   225                             children_iterator(m_children.end()));
   226     }
   227 
   228     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&
   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&
   242     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
   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
   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>
   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
   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
   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
   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>
   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
   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
   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>
   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>
   400   vertices(const subgraph<G>& g)
   401     { return vertices(g.m_graph); }
   402 
   403   template <typename G>
   404   typename subgraph<G>::vertices_size_type
   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>
   414   edges(const subgraph<G>& g)
   415     { return edges(g.m_graph); }
   416 
   417   template <typename G>
   418   typename subgraph<G>::edges_size_type
   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>
   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>
   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>
   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>
   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>
   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>
   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>
   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>
   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>
   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>
   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>
   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>
   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
   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
   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
   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
   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
   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
   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>
   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 
   704     subgraph_global_property_map() { }
   705 
   706     subgraph_global_property_map(GraphPtr g)
   707       : m_g(g) { }
   708 
   709     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 
   732     subgraph_local_property_map() { }
   733 
   734     subgraph_local_property_map(GraphPtr g)
   735       : m_g(g) { }
   736 
   737     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
   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
   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
   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
   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&
   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&
   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
   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