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