Chris@16: //=======================================================================
Chris@16: // Copyright 2001 University of Notre Dame.
Chris@16: // Authors: Jeremy G. Siek and Lie-Quan Lee
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: #ifndef BOOST_SUBGRAPH_HPP
Chris@16: #define BOOST_SUBGRAPH_HPP
Chris@16: 
Chris@16: // UNDER CONSTRUCTION
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <list>
Chris@16: #include <vector>
Chris@16: #include <map>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/graph_mutability_traits.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/iterator/indirect_iterator.hpp>
Chris@16: 
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/type_traits.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/mpl/or.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: struct subgraph_tag { };
Chris@16: 
Chris@16: /** @name Property Lookup
Chris@16:  * The local_property and global_property functions are used to create
Chris@16:  * structures that determine the lookup strategy for properties in subgraphs.
Chris@16:  * Note that the nested kind member is used to help interoperate with actual
Chris@16:  * Property types.
Chris@16:  */
Chris@16: //@{
Chris@16: template <typename T>
Chris@16: struct local_property
Chris@16: {
Chris@16:     typedef T kind;
Chris@16:     local_property(T x) : value(x) { }
Chris@16:     T value;
Chris@16: };
Chris@16: 
Chris@16: template <typename T>
Chris@16: inline local_property<T> local(T x)
Chris@16: { return local_property<T>(x); }
Chris@16: 
Chris@16: template <typename T>
Chris@16: struct global_property
Chris@16: {
Chris@16:     typedef T kind;
Chris@16:     global_property(T x) : value(x) { }
Chris@16:     T value;
Chris@16: };
Chris@16: 
Chris@16: template <typename T>
Chris@16: inline global_property<T> global(T x)
Chris@16: { return global_property<T>(x); }
Chris@16: //@}
Chris@16: 
Chris@16: // Invariants of an induced subgraph:
Chris@16: //   - If vertex u is in subgraph g, then u must be in g.parent().
Chris@16: //   - If edge e is in subgraph g, then e must be in g.parent().
Chris@16: //   - If edge e=(u,v) is in the root graph, then edge e
Chris@16: //     is also in any subgraph that contains both vertex u and v.
Chris@16: 
Chris@16: // The Graph template parameter must have a vertex_index and edge_index
Chris@16: // internal property. It is assumed that the vertex indices are assigned
Chris@16: // automatically by the graph during a call to add_vertex(). It is not
Chris@16: // assumed that the edge vertices are assigned automatically, they are
Chris@16: // explicitly assigned here.
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: class subgraph {
Chris@16:     typedef graph_traits<Graph> Traits;
Chris@16:     typedef std::list<subgraph<Graph>*> ChildrenList;
Chris@16: public:
Chris@16:     // Graph requirements
Chris@16:     typedef typename Traits::vertex_descriptor         vertex_descriptor;
Chris@16:     typedef typename Traits::edge_descriptor           edge_descriptor;
Chris@16:     typedef typename Traits::directed_category         directed_category;
Chris@16:     typedef typename Traits::edge_parallel_category    edge_parallel_category;
Chris@16:     typedef typename Traits::traversal_category        traversal_category;
Chris@16: 
Chris@16:     // IncidenceGraph requirements
Chris@16:     typedef typename Traits::out_edge_iterator         out_edge_iterator;
Chris@16:     typedef typename Traits::degree_size_type          degree_size_type;
Chris@16: 
Chris@16:     // AdjacencyGraph requirements
Chris@16:     typedef typename Traits::adjacency_iterator        adjacency_iterator;
Chris@16: 
Chris@16:     // VertexListGraph requirements
Chris@16:     typedef typename Traits::vertex_iterator           vertex_iterator;
Chris@16:     typedef typename Traits::vertices_size_type        vertices_size_type;
Chris@16: 
Chris@16:     // EdgeListGraph requirements
Chris@16:     typedef typename Traits::edge_iterator             edge_iterator;
Chris@16:     typedef typename Traits::edges_size_type           edges_size_type;
Chris@16: 
Chris@16:     typedef typename Traits::in_edge_iterator          in_edge_iterator;
Chris@16: 
Chris@16:     typedef typename edge_property_type<Graph>::type   edge_property_type;
Chris@16:     typedef typename vertex_property_type<Graph>::type vertex_property_type;
Chris@16:     typedef subgraph_tag                               graph_tag;
Chris@16:     typedef Graph                                      graph_type;
Chris@16:     typedef typename graph_property_type<Graph>::type  graph_property_type;
Chris@16: 
Chris@16:     // Create the main graph, the root of the subgraph tree
Chris@16:     subgraph()
Chris@16:         : m_parent(0), m_edge_counter(0)
Chris@16:     { }
Chris@16: 
Chris@16:     subgraph(const graph_property_type& p)
Chris@16:         : m_graph(p), m_parent(0), m_edge_counter(0)
Chris@16:     { }
Chris@16: 
Chris@16:     subgraph(vertices_size_type n, const graph_property_type& p = graph_property_type())
Chris@16:         : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
Chris@16:     {
Chris@16:         typename Graph::vertex_iterator v, v_end;
Chris@16:         vertices_size_type i = 0;
Chris@16:         for(boost::tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
Chris@16:             m_global_vertex[i++] = *v;
Chris@16:     }
Chris@16: 
Chris@16:     // copy constructor
Chris@16:     subgraph(const subgraph& x)
Chris@16:         : m_parent(x.m_parent), m_edge_counter(x.m_edge_counter)
Chris@16:         , m_global_vertex(x.m_global_vertex), m_global_edge(x.m_global_edge)
Chris@16:     {
Chris@16:         if(x.is_root())
Chris@16:         {
Chris@16:          m_graph = x.m_graph;
Chris@16:         }
Chris@16:         // Do a deep copy (recursive).
Chris@16:         // Only the root graph is copied, the subgraphs contain
Chris@16:         // only references to the global vertices they own.
Chris@16:         typename subgraph<Graph>::children_iterator i,i_end;
Chris@16:         boost::tie(i,i_end) = x.children();
Chris@16:         for(; i != i_end; ++i)
Chris@16:         {         
Chris@16:          subgraph<Graph> child = this->create_subgraph();
Chris@16:          child = *i;
Chris@16:          vertex_iterator vi,vi_end;   
Chris@16:          boost::tie(vi,vi_end) = vertices(*i);
Chris@16:          for (;vi!=vi_end;++vi)  
Chris@16:          {
Chris@16:           add_vertex(*vi,child);
Chris@16:          }
Chris@16:        }
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     ~subgraph() {
Chris@16:       for(typename ChildrenList::iterator i = m_children.begin();
Chris@16:           i != m_children.end(); ++i)
Chris@16:         {
Chris@16:             delete *i;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     // Return a null vertex descriptor for the graph.
Chris@16:     static vertex_descriptor null_vertex()
Chris@16:     { return Traits::null_vertex(); }
Chris@16: 
Chris@16: 
Chris@16:     // Create a subgraph
Chris@16:     subgraph<Graph>& create_subgraph() {
Chris@16:         m_children.push_back(new subgraph<Graph>());
Chris@16:         m_children.back()->m_parent = this;
Chris@16:         return *m_children.back();
Chris@16:     }
Chris@16: 
Chris@16:     // Create a subgraph with the specified vertex set.
Chris@16:     template <typename VertexIterator>
Chris@16:     subgraph<Graph>& create_subgraph(VertexIterator first, VertexIterator last) {
Chris@16:         m_children.push_back(new subgraph<Graph>());
Chris@16:         m_children.back()->m_parent = this;
Chris@16:         for(; first != last; ++first) {
Chris@16:             add_vertex(*first, *m_children.back());
Chris@16:         }
Chris@16:         return *m_children.back();
Chris@16:     }
Chris@16: 
Chris@16:     // local <-> global descriptor conversion functions
Chris@16:     vertex_descriptor local_to_global(vertex_descriptor u_local) const
Chris@16:     { return is_root() ? u_local : m_global_vertex[u_local]; }
Chris@16: 
Chris@16:     vertex_descriptor global_to_local(vertex_descriptor u_global) const {
Chris@16:         vertex_descriptor u_local; bool in_subgraph;
Chris@16:         if (is_root()) return u_global;
Chris@16:         boost::tie(u_local, in_subgraph) = this->find_vertex(u_global);
Chris@16:         BOOST_ASSERT(in_subgraph == true);
Chris@16:         return u_local;
Chris@16:     }
Chris@16: 
Chris@16:     edge_descriptor local_to_global(edge_descriptor e_local) const
Chris@16:     { return is_root() ? e_local : m_global_edge[get(get(edge_index, m_graph), e_local)]; }
Chris@16: 
Chris@16:     edge_descriptor global_to_local(edge_descriptor e_global) const
Chris@16:     { return is_root() ? e_global : (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second; }
Chris@16: 
Chris@16:     // Is vertex u (of the root graph) contained in this subgraph?
Chris@16:     // If so, return the matching local vertex.
Chris@16:     std::pair<vertex_descriptor, bool>
Chris@16:     find_vertex(vertex_descriptor u_global) const {
Chris@16:         if (is_root()) return std::make_pair(u_global, true);
Chris@16:         typename LocalVertexMap::const_iterator i = m_local_vertex.find(u_global);
Chris@16:         bool valid = i != m_local_vertex.end();
Chris@16:         return std::make_pair((valid ? (*i).second : null_vertex()), valid);
Chris@16:     }
Chris@16: 
Chris@16:     // Is edge e (of the root graph) contained in this subgraph?
Chris@16:     // If so, return the matching local edge.
Chris@16:     std::pair<edge_descriptor, bool>
Chris@16:     find_edge(edge_descriptor e_global) const {
Chris@16:         if (is_root()) return std::make_pair(e_global, true);
Chris@16:         typename LocalEdgeMap::const_iterator i =
Chris@16:           m_local_edge.find(get(get(edge_index, root().m_graph), e_global));
Chris@16:         bool valid = i != m_local_edge.end();
Chris@16:         return std::make_pair((valid ? (*i).second : edge_descriptor()), valid);
Chris@16:     }
Chris@16: 
Chris@16:     // Return the parent graph.
Chris@16:     subgraph& parent() { return *m_parent; }
Chris@16:     const subgraph& parent() const { return *m_parent; }
Chris@16: 
Chris@16:     // Return true if this is the root subgraph
Chris@16:     bool is_root() const { return m_parent == 0; }
Chris@16: 
Chris@16:     // Return the root graph of the subgraph tree.
Chris@16:     subgraph& root()
Chris@16:     { return is_root() ? *this : m_parent->root(); }
Chris@16: 
Chris@16:     const subgraph& root() const
Chris@16:     { return is_root() ? *this : m_parent->root(); }
Chris@16: 
Chris@16:     // Return the children subgraphs of this graph/subgraph.
Chris@16:     // Use a list of pointers because the VC++ std::list doesn't like
Chris@16:     // storing incomplete type.
Chris@16:     typedef indirect_iterator<
Chris@16:         typename ChildrenList::const_iterator
Chris@16:       , subgraph<Graph>
Chris@16:       , std::bidirectional_iterator_tag
Chris@16:     >
Chris@16:     children_iterator;
Chris@16: 
Chris@16:     typedef indirect_iterator<
Chris@16:         typename ChildrenList::const_iterator
Chris@16:       , subgraph<Graph> const
Chris@16:       , std::bidirectional_iterator_tag
Chris@16:     >
Chris@16:     const_children_iterator;
Chris@16: 
Chris@16:     std::pair<const_children_iterator, const_children_iterator> children() const {
Chris@16:       return std::make_pair(const_children_iterator(m_children.begin()),
Chris@16:                             const_children_iterator(m_children.end()));
Chris@16:     }
Chris@16: 
Chris@16:     std::pair<children_iterator, children_iterator> children() {
Chris@16:       return std::make_pair(children_iterator(m_children.begin()),
Chris@16:                             children_iterator(m_children.end()));
Chris@16:     }
Chris@16: 
Chris@16:     std::size_t num_children() const { return m_children.size(); }
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16:     // Defualt property access delegates the lookup to global properties.
Chris@16:     template <typename Descriptor>
Chris@16:     typename graph::detail::bundled_result<Graph, Descriptor>::type&
Chris@16:     operator[](Descriptor x)
Chris@16:     { return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)]; }
Chris@16: 
Chris@16:     template <typename Descriptor>
Chris@16:     typename graph::detail::bundled_result<Graph, Descriptor>::type const&
Chris@16:     operator[](Descriptor x) const
Chris@16:     { return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)]; }
Chris@16: 
Chris@16:     // Local property access returns the local property of the given descripor.
Chris@16:     template <typename Descriptor>
Chris@16:     typename graph::detail::bundled_result<Graph, Descriptor>::type&
Chris@16:     operator[](local_property<Descriptor> x)
Chris@16:     { return m_graph[x.value]; }
Chris@16: 
Chris@16:     template <typename Descriptor>
Chris@16:     typename graph::detail::bundled_result<Graph, Descriptor>::type const&
Chris@16:     operator[](local_property<Descriptor> x) const
Chris@16:     { return m_graph[x.value]; }
Chris@16: 
Chris@16:     // Global property access returns the global property associated with the
Chris@16:     // given descriptor. This is an alias for the default bundled property
Chris@16:     // access operations.
Chris@16:     template <typename Descriptor>
Chris@16:     typename graph::detail::bundled_result<Graph, Descriptor>::type&
Chris@16:     operator[](global_property<Descriptor> x)
Chris@16:     { return (*this)[x.value]; }
Chris@16: 
Chris@16:     template <typename Descriptor>
Chris@16:     typename graph::detail::bundled_result<Graph, Descriptor>::type const&
Chris@16:     operator[](global_property<Descriptor> x) const
Chris@16:     { return (*this)[x.value]; }
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16: 
Chris@16:     //  private:
Chris@16:     typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap;
Chris@16:     typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type;
Chris@16:     BOOST_STATIC_ASSERT((!is_same<edge_index_type,
Chris@16:                         boost::detail::error_property_not_found>::value));
Chris@16: 
Chris@16: private:
Chris@16:     typedef std::vector<vertex_descriptor> GlobalVertexList;
Chris@16:     typedef std::vector<edge_descriptor> GlobalEdgeList;
Chris@16:     typedef std::map<vertex_descriptor, vertex_descriptor> LocalVertexMap;
Chris@16:     typedef std::map<edge_index_type, edge_descriptor> LocalEdgeMap;
Chris@16:     // TODO: Should the LocalVertexMap be: map<index_type, descriptor>?
Chris@16:     // TODO: Can we relax the indexing requirement if both descriptors are
Chris@16:     // LessThanComparable?
Chris@16:     // TODO: Should we really be using unorderd_map for improved lookup times?
Chris@16: 
Chris@16: public: // Probably shouldn't be public....
Chris@16:     Graph m_graph;
Chris@16:     subgraph<Graph>* m_parent;
Chris@16:     edge_index_type m_edge_counter; // for generating unique edge indices
Chris@16:     ChildrenList m_children;
Chris@16:     GlobalVertexList m_global_vertex; // local -> global
Chris@16:     LocalVertexMap m_local_vertex;  // global -> local
Chris@16:     GlobalEdgeList m_global_edge;              // local -> global
Chris@16:     LocalEdgeMap m_local_edge; // global -> local
Chris@16: 
Chris@16:     edge_descriptor local_add_edge(vertex_descriptor u_local,
Chris@16:                                    vertex_descriptor v_local,
Chris@16:                                    edge_descriptor e_global)
Chris@16:     {
Chris@16:         edge_descriptor e_local;
Chris@16:         bool inserted;
Chris@16:         boost::tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
Chris@16:         put(edge_index, m_graph, e_local, m_edge_counter++);
Chris@16:         m_global_edge.push_back(e_global);
Chris@16:         m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
Chris@16:         return e_local;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: struct vertex_bundle_type<subgraph<Graph> >
Chris@16:     : vertex_bundle_type<Graph>
Chris@16: { };
Chris@16: 
Chris@16: template<typename Graph>
Chris@16: struct edge_bundle_type<subgraph<Graph> >
Chris@16:     : edge_bundle_type<Graph>
Chris@16: { };
Chris@16: 
Chris@16: template<typename Graph>
Chris@16: struct graph_bundle_type<subgraph<Graph> >
Chris@16:     : graph_bundle_type<Graph>
Chris@16: { };
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions special to the Subgraph Class
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename subgraph<G>::vertex_descriptor
Chris@16: add_vertex(typename subgraph<G>::vertex_descriptor u_global,
Chris@16:            subgraph<G>& g)
Chris@16: {
Chris@16:     BOOST_ASSERT(!g.is_root());
Chris@16:     typename subgraph<G>::vertex_descriptor u_local, v_global;
Chris@16:     typename subgraph<G>::edge_descriptor e_global;
Chris@16: 
Chris@16:     u_local = add_vertex(g.m_graph);
Chris@16:     g.m_global_vertex.push_back(u_global);
Chris@16:     g.m_local_vertex[u_global] = u_local;
Chris@16: 
Chris@16:     subgraph<G>& r = g.root();
Chris@16: 
Chris@16:     // remember edge global and local maps
Chris@16:     {
Chris@16:         typename subgraph<G>::out_edge_iterator ei, ei_end;
Chris@16:         for (boost::tie(ei, ei_end) = out_edges(u_global, r);
Chris@16:             ei != ei_end; ++ei) {
Chris@16:             e_global = *ei;
Chris@16:             v_global = target(e_global, r);
Chris@16:             if (g.find_vertex(v_global).second == true)
Chris@16:             g.local_add_edge(u_local, g.global_to_local(v_global), e_global);
Chris@16:         }
Chris@16:     }
Chris@16:     if (is_directed(g)) { // not necessary for undirected graph
Chris@16:         typename subgraph<G>::vertex_iterator vi, vi_end;
Chris@16:         typename subgraph<G>::out_edge_iterator ei, ei_end;
Chris@16:         for(boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
Chris@16:             v_global = *vi;
Chris@16:             if (v_global == u_global)
Chris@16:                 continue; // don't insert self loops twice!
Chris@16:             if (!g.find_vertex(v_global).second)
Chris@16:                 continue; // not a subgraph vertex => try next one
Chris@16:             for(boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
Chris@16:                 e_global = *ei;
Chris@16:                 if(target(e_global, r) == u_global) {
Chris@16:                     g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     return u_local;
Chris@16: }
Chris@16: 
Chris@16: // NOTE: Descriptors are local unless otherwise noted.
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the IncidenceGraph concept
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename graph_traits<G>::out_edge_iterator,
Chris@16:           typename graph_traits<G>::out_edge_iterator>
Chris@16: out_edges(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
Chris@16: { return out_edges(v, g.m_graph); }
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename graph_traits<G>::degree_size_type
Chris@16: out_degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
Chris@16: { return out_degree(v, g.m_graph); }
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename graph_traits<G>::vertex_descriptor
Chris@16: source(typename graph_traits<G>::edge_descriptor e, const subgraph<G>& g)
Chris@16: { return source(e, g.m_graph); }
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename graph_traits<G>::vertex_descriptor
Chris@16: target(typename graph_traits<G>::edge_descriptor e, const subgraph<G>& g)
Chris@16: { return target(e, g.m_graph); }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the BidirectionalGraph concept
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename graph_traits<G>::in_edge_iterator,
Chris@16:           typename graph_traits<G>::in_edge_iterator>
Chris@16: in_edges(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
Chris@16: { return in_edges(v, g.m_graph); }
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename graph_traits<G>::degree_size_type
Chris@16: in_degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
Chris@16: { return in_degree(v, g.m_graph); }
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename graph_traits<G>::degree_size_type
Chris@16: degree(typename graph_traits<G>::vertex_descriptor v, const subgraph<G>& g)
Chris@16: { return degree(v, g.m_graph); }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the AdjacencyGraph concept
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename subgraph<G>::adjacency_iterator,
Chris@16:           typename subgraph<G>::adjacency_iterator>
Chris@16: adjacent_vertices(typename subgraph<G>::vertex_descriptor v, const subgraph<G>& g)
Chris@16: { return adjacent_vertices(v, g.m_graph); }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the VertexListGraph concept
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename subgraph<G>::vertex_iterator,
Chris@16:           typename subgraph<G>::vertex_iterator>
Chris@16: vertices(const subgraph<G>& g)
Chris@16: { return vertices(g.m_graph); }
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename subgraph<G>::vertices_size_type
Chris@16: num_vertices(const subgraph<G>& g)
Chris@16: { return num_vertices(g.m_graph); }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the EdgeListGraph concept
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename subgraph<G>::edge_iterator,
Chris@16:           typename subgraph<G>::edge_iterator>
Chris@16: edges(const subgraph<G>& g)
Chris@16: { return edges(g.m_graph); }
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename subgraph<G>::edges_size_type
Chris@16: num_edges(const subgraph<G>& g)
Chris@16: { return num_edges(g.m_graph); }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the AdjacencyMatrix concept
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename subgraph<G>::edge_descriptor, bool>
Chris@16: edge(typename subgraph<G>::vertex_descriptor u,
Chris@16:      typename subgraph<G>::vertex_descriptor v,
Chris@16:      const subgraph<G>& g)
Chris@16: { return edge(u, v, g.m_graph); }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the MutableGraph concept
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16:     template <typename Vertex, typename Edge, typename Graph>
Chris@16:     void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
Chris@16:                              subgraph<Graph>& g);
Chris@16: 
Chris@16:     template <typename Vertex, typename Edge, typename Children, typename G>
Chris@16:     void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
Chris@16:                            Children& c, subgraph<G>* orig)
Chris@16:     {
Chris@16:         for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
Chris@16:             if ((*i)->find_vertex(u_global).second &&
Chris@16:                 (*i)->find_vertex(v_global).second)
Chris@16:             {
Chris@16:                 add_edge_recur_down(u_global, v_global, e_global, **i, orig);
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Vertex, typename Edge, typename Graph>
Chris@16:     void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
Chris@16:                              subgraph<Graph>& g, subgraph<Graph>* orig)
Chris@16:     {
Chris@16:         if(&g != orig ) {
Chris@16:             // add local edge only if u_global and v_global are in subgraph g
Chris@16:             Vertex u_local, v_local;
Chris@16:             bool u_in_subgraph, v_in_subgraph;
Chris@16:             boost::tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
Chris@16:             boost::tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
Chris@16:             if(u_in_subgraph && v_in_subgraph) {
Chris@16:                 g.local_add_edge(u_local, v_local, e_global);
Chris@16:             }
Chris@16:         }
Chris@16:         children_add_edge(u_global, v_global, e_global, g.m_children, orig);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Vertex, typename Graph>
Chris@16:     std::pair<typename subgraph<Graph>::edge_descriptor, bool>
Chris@16:     add_edge_recur_up(Vertex u_global, Vertex v_global,
Chris@16:                       const typename Graph::edge_property_type& ep,
Chris@16:                       subgraph<Graph>& g, subgraph<Graph>* orig)
Chris@16:     {
Chris@16:         if(g.is_root()) {
Chris@16:             typename subgraph<Graph>::edge_descriptor e_global;
Chris@16:             bool inserted;
Chris@16:             boost::tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);
Chris@16:             put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
Chris@16:             g.m_global_edge.push_back(e_global);
Chris@16:             children_add_edge(u_global, v_global, e_global, g.m_children, orig);
Chris@16:             return std::make_pair(e_global, inserted);
Chris@16:         } else {
Chris@16:             return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: // Add an edge to the subgraph g, specified by the local vertex descriptors u
Chris@16: // and v. In addition, the edge will be added to any (all) other subgraphs that
Chris@16: // contain vertex descriptors u and v.
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename subgraph<G>::edge_descriptor, bool>
Chris@16: add_edge(typename subgraph<G>::vertex_descriptor u,
Chris@16:          typename subgraph<G>::vertex_descriptor v,
Chris@16:          const typename G::edge_property_type& ep,
Chris@16:          subgraph<G>& g)
Chris@16: {
Chris@16:     if (g.is_root()) {
Chris@16:         // u and v are really global
Chris@16:         return detail::add_edge_recur_up(u, v, ep, g, &g);
Chris@16:     } else {
Chris@16:         typename subgraph<G>::edge_descriptor e_local, e_global;
Chris@16:         bool inserted;
Chris@16:         boost::tie(e_global, inserted) =
Chris@16:             detail::add_edge_recur_up(g.local_to_global(u),
Chris@16:                                       g.local_to_global(v),
Chris@16:                                       ep, g, &g);
Chris@16:         e_local = g.local_add_edge(u, v, e_global);
Chris@16:         return std::make_pair(e_local, inserted);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <typename G>
Chris@16: std::pair<typename subgraph<G>::edge_descriptor, bool>
Chris@16: add_edge(typename subgraph<G>::vertex_descriptor u,
Chris@16:          typename subgraph<G>::vertex_descriptor v,
Chris@16:          subgraph<G>& g)
Chris@16: { return add_edge(u, v, typename G::edge_property_type(), g); }
Chris@16: 
Chris@16: namespace detail {
Chris@16:     //-------------------------------------------------------------------------
Chris@16:     // implementation of remove_edge(u,v,g)
Chris@16:     template <typename Vertex, typename Graph>
Chris@16:     void remove_edge_recur_down(Vertex u_global, Vertex v_global,
Chris@16:                                 subgraph<Graph>& g);
Chris@16: 
Chris@16:     template <typename Vertex, typename Children>
Chris@16:     void children_remove_edge(Vertex u_global, Vertex v_global,
Chris@16:                               Children& c)
Chris@16:     {
Chris@16:         for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
Chris@16:             if((*i)->find_vertex(u_global).second &&
Chris@16:                (*i)->find_vertex(v_global).second)
Chris@16:             {
Chris@16:                 remove_edge_recur_down(u_global, v_global, **i);
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Vertex, typename Graph>
Chris@16:     void remove_edge_recur_down(Vertex u_global, Vertex v_global,
Chris@16:                                 subgraph<Graph>& g)
Chris@16:     {
Chris@16:         Vertex u_local, v_local;
Chris@16:         u_local = g.m_local_vertex[u_global];
Chris@16:         v_local = g.m_local_vertex[v_global];
Chris@16:         remove_edge(u_local, v_local, g.m_graph);
Chris@16:         children_remove_edge(u_global, v_global, g.m_children);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Vertex, typename Graph>
Chris@16:     void remove_edge_recur_up(Vertex u_global, Vertex v_global,
Chris@16:                               subgraph<Graph>& g)
Chris@16:     {
Chris@16:         if(g.is_root()) {
Chris@16:             remove_edge(u_global, v_global, g.m_graph);
Chris@16:             children_remove_edge(u_global, v_global, g.m_children);
Chris@16:         } else {
Chris@16:             remove_edge_recur_up(u_global, v_global, *g.m_parent);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     //-------------------------------------------------------------------------
Chris@16:     // implementation of remove_edge(e,g)
Chris@16: 
Chris@16:     template <typename G, typename Edge, typename Children>
Chris@16:     void children_remove_edge(Edge e_global, Children& c)
Chris@16:     {
Chris@16:         for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
Chris@16:             std::pair<typename subgraph<G>::edge_descriptor, bool> found =
Chris@16:               (*i)->find_edge(e_global);
Chris@16:             if (!found.second) {
Chris@16:               continue;
Chris@16:             }
Chris@16:             children_remove_edge<G>(e_global, (*i)->m_children);
Chris@16:             remove_edge(found.first, (*i)->m_graph);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: template <typename G>
Chris@16: void
Chris@16: remove_edge(typename subgraph<G>::vertex_descriptor u,
Chris@16:             typename subgraph<G>::vertex_descriptor v,
Chris@16:             subgraph<G>& g)
Chris@16: {
Chris@16:     if(g.is_root()) {
Chris@16:         detail::remove_edge_recur_up(u, v, g);
Chris@16:     } else {
Chris@16:         detail::remove_edge_recur_up(g.local_to_global(u),
Chris@16:                                      g.local_to_global(v), g);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <typename G>
Chris@16: void
Chris@16: remove_edge(typename subgraph<G>::edge_descriptor e, subgraph<G>& g)
Chris@16: {
Chris@16:     typename subgraph<G>::edge_descriptor e_global = g.local_to_global(e);
Chris@16: #ifndef NDEBUG
Chris@16:     std::pair<typename subgraph<G>::edge_descriptor, bool> fe = g.find_edge(e_global);
Chris@16:     BOOST_ASSERT(fe.second && fe.first == e);
Chris@16: #endif //NDEBUG
Chris@16:     subgraph<G> &root = g.root(); // chase to root
Chris@16:     detail::children_remove_edge<G>(e_global, root.m_children);
Chris@16:     remove_edge(e_global, root.m_graph); // kick edge from root
Chris@16: }
Chris@16: 
Chris@16: // This is slow, but there may not be a good way to do it safely otherwise
Chris@16: template <typename Predicate, typename G>
Chris@16: void
Chris@16: remove_edge_if(Predicate p, subgraph<G>& g) {
Chris@16:   while (true) {
Chris@16:     bool any_removed = false;
Chris@16:     typedef typename subgraph<G>::edge_iterator ei_type;
Chris@16:     for (std::pair<ei_type, ei_type> ep = edges(g);
Chris@16:          ep.first != ep.second; ++ep.first) {
Chris@16:       if (p(*ep.first)) {
Chris@16:         any_removed = true;
Chris@16:         remove_edge(*ep.first, g);
Chris@16:         break; /* Since iterators may be invalidated */
Chris@16:       }
Chris@16:     }
Chris@16:     if (!any_removed) break;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <typename G>
Chris@16: void
Chris@16: clear_vertex(typename subgraph<G>::vertex_descriptor v, subgraph<G>& g) {
Chris@16:   while (true) {
Chris@16:     typedef typename subgraph<G>::out_edge_iterator oei_type;
Chris@16:     std::pair<oei_type, oei_type> p = out_edges(v, g);
Chris@16:     if (p.first == p.second) break;
Chris@16:     remove_edge(*p.first, g);
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: namespace detail {
Chris@16:     template <typename G>
Chris@16:     typename subgraph<G>::vertex_descriptor
Chris@16:     add_vertex_recur_up(subgraph<G>& g)
Chris@16:     {
Chris@16:         typename subgraph<G>::vertex_descriptor u_local, u_global;
Chris@16:         if (g.is_root()) {
Chris@16:             u_global = add_vertex(g.m_graph);
Chris@16:             g.m_global_vertex.push_back(u_global);
Chris@16:         } else {
Chris@16:             u_global = add_vertex_recur_up(*g.m_parent);
Chris@16:             u_local = add_vertex(g.m_graph);
Chris@16:             g.m_global_vertex.push_back(u_global);
Chris@16:             g.m_local_vertex[u_global] = u_local;
Chris@16:         }
Chris@16:         return u_global;
Chris@16:     }
Chris@16: } // namespace detail
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename subgraph<G>::vertex_descriptor
Chris@16: add_vertex(subgraph<G>& g)
Chris@16: {
Chris@16:     typename subgraph<G>::vertex_descriptor  u_local, u_global;
Chris@16:     if(g.is_root()) {
Chris@16:         u_global = add_vertex(g.m_graph);
Chris@16:         g.m_global_vertex.push_back(u_global);
Chris@16:         u_local = u_global;
Chris@16:     } else {
Chris@16:         u_global = detail::add_vertex_recur_up(g.parent());
Chris@16:         u_local = add_vertex(g.m_graph);
Chris@16:         g.m_global_vertex.push_back(u_global);
Chris@16:         g.m_local_vertex[u_global] = u_local;
Chris@16:     }
Chris@16:     return u_local;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: #if 0
Chris@16: // TODO: Under Construction
Chris@16: template <typename G>
Chris@16: void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
Chris@16: { BOOST_ASSERT(false); }
Chris@16: #endif
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Functions required by the PropertyGraph concept
Chris@16: 
Chris@16: /**
Chris@16:  * The global property map returns the global properties associated with local
Chris@16:  * descriptors.
Chris@16:  */
Chris@16: template <typename GraphPtr, typename PropertyMap, typename Tag>
Chris@16: class subgraph_global_property_map
Chris@16:     : public put_get_helper<
Chris@16:         typename property_traits<PropertyMap>::reference,
Chris@16:         subgraph_global_property_map<GraphPtr, PropertyMap, Tag>
Chris@16:     >
Chris@16: {
Chris@16:     typedef property_traits<PropertyMap> Traits;
Chris@16: public:
Chris@16:     typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
Chris@16:                               readable_property_map_tag,
Chris@16:                               typename Traits::category>::type
Chris@16:       category;
Chris@16:     typedef typename Traits::value_type value_type;
Chris@16:     typedef typename Traits::key_type key_type;
Chris@16:     typedef typename Traits::reference reference;
Chris@16: 
Chris@16:     subgraph_global_property_map()
Chris@16:     { }
Chris@16: 
Chris@16:     subgraph_global_property_map(GraphPtr g, Tag tag)
Chris@16:         : m_g(g), m_tag(tag)
Chris@16:     { }
Chris@16: 
Chris@16:     reference operator[](key_type e) const {
Chris@16:         PropertyMap pmap = get(m_tag, m_g->root().m_graph);
Chris@16:         return m_g->is_root()
Chris@16:             ? pmap[e]
Chris@16:             : pmap[m_g->local_to_global(e)];
Chris@16:     }
Chris@16: 
Chris@16:     GraphPtr m_g;
Chris@16:     Tag m_tag;
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * The local property map returns the local property associated with the local
Chris@16:  * descriptors.
Chris@16:  */
Chris@16: template <typename GraphPtr, typename PropertyMap, typename Tag>
Chris@16: class subgraph_local_property_map
Chris@16:     : public put_get_helper<
Chris@16:         typename property_traits<PropertyMap>::reference,
Chris@16:         subgraph_local_property_map<GraphPtr, PropertyMap, Tag>
Chris@16:     >
Chris@16: {
Chris@16:     typedef property_traits<PropertyMap> Traits;
Chris@16: public:
Chris@16:     typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
Chris@16:                               readable_property_map_tag,
Chris@16:                               typename Traits::category>::type
Chris@16:       category;
Chris@16:     typedef typename Traits::value_type value_type;
Chris@16:     typedef typename Traits::key_type key_type;
Chris@16:     typedef typename Traits::reference reference;
Chris@16: 
Chris@16:     typedef Tag tag;
Chris@16:     typedef PropertyMap pmap;
Chris@16: 
Chris@16:     subgraph_local_property_map()
Chris@16:     { }
Chris@16: 
Chris@16:     subgraph_local_property_map(GraphPtr g, Tag tag)
Chris@16:         : m_g(g), m_tag(tag)
Chris@16:     { }
Chris@16: 
Chris@16:     reference operator[](key_type e) const {
Chris@16:         // Get property map on the underlying graph.
Chris@16:         PropertyMap pmap = get(m_tag, m_g->m_graph);
Chris@16:         return pmap[e];
Chris@16:     }
Chris@16: 
Chris@16:     GraphPtr m_g;
Chris@16:     Tag m_tag;
Chris@16: };
Chris@16: 
Chris@16: namespace detail {
Chris@16:     // Extract the actual tags from local or global property maps so we don't
Chris@16:     // try to find non-properties.
Chris@16:     template <typename P> struct extract_lg_tag { typedef P type; };
Chris@16:     template <typename P> struct extract_lg_tag< local_property<P> > {
Chris@16:         typedef P type;
Chris@16:     };
Chris@16:     template <typename P> struct extract_lg_tag< global_property<P> > {
Chris@16:         typedef P type;
Chris@16:     };
Chris@16: 
Chris@16:     // NOTE: Mysterious Property template parameter unused in both metafunction
Chris@16:     // classes.
Chris@16:     struct subgraph_global_pmap {
Chris@16:         template <class Tag, class SubGraph, class Property>
Chris@16:         struct bind_ {
Chris@16:             typedef typename SubGraph::graph_type Graph;
Chris@16:             typedef SubGraph* SubGraphPtr;
Chris@16:             typedef const SubGraph* const_SubGraphPtr;
Chris@16:             typedef typename extract_lg_tag<Tag>::type TagType;
Chris@16:             typedef typename property_map<Graph, TagType>::type PMap;
Chris@16:             typedef typename property_map<Graph, TagType>::const_type const_PMap;
Chris@16:         public:
Chris@16:             typedef subgraph_global_property_map<SubGraphPtr, PMap, TagType> type;
Chris@16:             typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, TagType>
Chris@16:             const_type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     struct subgraph_local_pmap {
Chris@16:         template <class Tag, class SubGraph, class Property>
Chris@16:         struct bind_ {
Chris@16:             typedef typename SubGraph::graph_type Graph;
Chris@16:             typedef SubGraph* SubGraphPtr;
Chris@16:             typedef const SubGraph* const_SubGraphPtr;
Chris@16:             typedef typename extract_lg_tag<Tag>::type TagType;
Chris@16:             typedef typename property_map<Graph, TagType>::type PMap;
Chris@16:             typedef typename property_map<Graph, TagType>::const_type const_PMap;
Chris@16:         public:
Chris@16:             typedef subgraph_local_property_map<SubGraphPtr, PMap, TagType> type;
Chris@16:             typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, TagType>
Chris@16:             const_type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     // These metafunctions select the corresponding metafunctions above, and
Chris@16:     // are used by the choose_pmap metafunction below to specialize the choice
Chris@16:     // of local/global property map. By default, we defer to the global
Chris@16:     // property.
Chris@16:     template <class Tag>
Chris@16:     struct subgraph_choose_pmap_helper {
Chris@16:         typedef subgraph_global_pmap type;
Chris@16:     };
Chris@16:     template <class Tag>
Chris@16:     struct subgraph_choose_pmap_helper< local_property<Tag> > {
Chris@16:         typedef subgraph_local_pmap type;
Chris@16:     };
Chris@16:     template <class Tag>
Chris@16:     struct subgraph_choose_pmap_helper< global_property<Tag> > {
Chris@16:         typedef subgraph_global_pmap type;
Chris@16:     };
Chris@16: 
Chris@16:     // As above, unless we're requesting vertex_index_t. Then it's always a
Chris@16:     // local property map. This enables the correct translation of descriptors
Chris@16:     // between local and global layers.
Chris@16:     template <>
Chris@16:     struct subgraph_choose_pmap_helper<vertex_index_t> {
Chris@16:         typedef subgraph_local_pmap type;
Chris@16:     };
Chris@16:     template <>
Chris@16:     struct subgraph_choose_pmap_helper< local_property<vertex_index_t> > {
Chris@16:         typedef subgraph_local_pmap type;
Chris@16:     };
Chris@16:     template <>
Chris@16:     struct subgraph_choose_pmap_helper< global_property<vertex_index_t> > {
Chris@16:         typedef subgraph_local_pmap type;
Chris@16:     };
Chris@16: 
Chris@16:     // Determine the kind of property. If SameType<Tag, vertex_index_t>, then
Chris@16:     // the property lookup is always local. Otherwise, the lookup is global.
Chris@16:     // NOTE: Property parameter is basically unused.
Chris@16:     template <class Tag, class Graph, class Property>
Chris@16:     struct subgraph_choose_pmap {
Chris@16:         typedef typename subgraph_choose_pmap_helper<Tag>::type Helper;
Chris@16:         typedef typename Helper::template bind_<Tag, Graph, Property> Bind;
Chris@16:         typedef typename Bind::type type;
Chris@16:         typedef typename Bind::const_type const_type;
Chris@16:     };
Chris@16: 
Chris@16:     // Used by the vertex/edge property selectors to determine the kind(s) of
Chris@16:     // property maps used by the property_map type generator.
Chris@16:     struct subgraph_property_generator {
Chris@16:         template <class SubGraph, class Property, class Tag>
Chris@16:         struct bind_ {
Chris@16:             typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice;
Chris@16:             typedef typename Choice::type type;
Chris@16:             typedef typename Choice::const_type const_type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16: template <>
Chris@16: struct vertex_property_selector<subgraph_tag> {
Chris@16:     typedef detail::subgraph_property_generator type;
Chris@16: };
Chris@16: 
Chris@16: template <>
Chris@16: struct edge_property_selector<subgraph_tag> {
Chris@16:     typedef detail::subgraph_property_generator type;
Chris@16: };
Chris@16: 
Chris@16: // ==================================================
Chris@16: // get(p, g), get(p, g, k), and put(p, g, k, v)
Chris@16: // ==================================================
Chris@16: template <typename G, typename Property>
Chris@16: typename property_map<subgraph<G>, Property>::type
Chris@16: get(Property p, subgraph<G>& g) {
Chris@16:     typedef typename property_map< subgraph<G>, Property>::type PMap;
Chris@16:     return PMap(&g, p);
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Property>
Chris@16: typename property_map<subgraph<G>, Property>::const_type
Chris@16: get(Property p, const subgraph<G>& g) {
Chris@16:     typedef typename property_map< subgraph<G>, Property>::const_type PMap;
Chris@16:     return PMap(&g, p);
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Property, typename Key>
Chris@16: typename property_traits<
Chris@16:     typename property_map<subgraph<G>, Property>::const_type
Chris@16: >::value_type
Chris@16: get(Property p, const subgraph<G>& g, const Key& k) {
Chris@16:     typedef typename property_map< subgraph<G>, Property>::const_type PMap;
Chris@16:     PMap pmap(&g, p);
Chris@16:     return pmap[k];
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Property, typename Key, typename Value>
Chris@16: void put(Property p, subgraph<G>& g, const Key& k, const Value& val) {
Chris@16:     typedef typename property_map< subgraph<G>, Property>::type PMap;
Chris@16:     PMap pmap(&g, p);
Chris@16:     pmap[k] = val;
Chris@16: }
Chris@16: 
Chris@16: // ==================================================
Chris@16: // get(global(p), g)
Chris@16: // NOTE: get(global(p), g, k) and put(global(p), g, k, v) not supported
Chris@16: // ==================================================
Chris@16: template <typename G, typename Property>
Chris@16: typename property_map<subgraph<G>, global_property<Property> >::type
Chris@16: get(global_property<Property> p, subgraph<G>& g) {
Chris@16:     typedef typename property_map<
Chris@16:         subgraph<G>, global_property<Property>
Chris@16:     >::type Map;
Chris@16:     return Map(&g, p.value);
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Property>
Chris@16: typename property_map<subgraph<G>, global_property<Property> >::const_type
Chris@16: get(global_property<Property> p, const subgraph<G>& g) {
Chris@16:     typedef typename property_map<
Chris@16:         subgraph<G>, global_property<Property>
Chris@16:     >::const_type Map;
Chris@16:     return Map(&g, p.value);
Chris@16: }
Chris@16: 
Chris@16: // ==================================================
Chris@16: // get(local(p), g)
Chris@16: // NOTE: get(local(p), g, k) and put(local(p), g, k, v) not supported
Chris@16: // ==================================================
Chris@16: template <typename G, typename Property>
Chris@16: typename property_map<subgraph<G>, local_property<Property> >::type
Chris@16: get(local_property<Property> p, subgraph<G>& g) {
Chris@16:     typedef typename property_map<
Chris@16:         subgraph<G>, local_property<Property>
Chris@16:     >::type Map;
Chris@16:     return Map(&g, p.value);
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Property>
Chris@16: typename property_map<subgraph<G>, local_property<Property> >::const_type
Chris@16: get(local_property<Property> p, const subgraph<G>& g) {
Chris@16:     typedef typename property_map<
Chris@16:         subgraph<G>, local_property<Property>
Chris@16:     >::const_type Map;
Chris@16:     return Map(&g, p.value);
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Tag>
Chris@16: inline typename graph_property<G, Tag>::type&
Chris@16: get_property(subgraph<G>& g, Tag tag) {
Chris@16:     return get_property(g.m_graph, tag);
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Tag>
Chris@16: inline const typename graph_property<G, Tag>::type&
Chris@16: get_property(const subgraph<G>& g, Tag tag) {
Chris@16:     return get_property(g.m_graph, tag);
Chris@16: }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Miscellaneous Functions
Chris@16: 
Chris@16: template <typename G>
Chris@16: typename subgraph<G>::vertex_descriptor
Chris@16: vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g)
Chris@16: { return vertex(n, g.m_graph); }
Chris@16: 
Chris@16: //===========================================================================
Chris@16: // Mutability Traits
Chris@16: // Just pull the mutability traits form the underlying graph. Note that this
Chris@16: // will probably fail (badly) for labeled graphs.
Chris@16: template <typename G>
Chris@16: struct graph_mutability_traits< subgraph<G> > {
Chris@16:     typedef typename graph_mutability_traits<G>::category category;
Chris@16: };
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_SUBGRAPH_HPP