Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:37 

0001 //=======================================================================
0002 // Copyright 2001 University of Notre Dame.
0003 // Authors: Jeremy G. Siek and Lie-Quan Lee
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 
0010 #ifndef BOOST_SUBGRAPH_HPP
0011 #define BOOST_SUBGRAPH_HPP
0012 
0013 // UNDER CONSTRUCTION
0014 
0015 #include <boost/config.hpp>
0016 #include <list>
0017 #include <vector>
0018 #include <map>
0019 #include <boost/assert.hpp>
0020 #include <boost/graph/graph_traits.hpp>
0021 #include <boost/graph/graph_mutability_traits.hpp>
0022 #include <boost/graph/properties.hpp>
0023 #include <boost/iterator/indirect_iterator.hpp>
0024 
0025 #include <boost/static_assert.hpp>
0026 #include <boost/assert.hpp>
0027 #include <boost/type_traits.hpp>
0028 #include <boost/mpl/if.hpp>
0029 #include <boost/mpl/or.hpp>
0030 
0031 namespace boost
0032 {
0033 
0034 struct subgraph_tag
0035 {
0036 };
0037 
0038 /** @name Property Lookup
0039  * The local_property and global_property functions are used to create
0040  * structures that determine the lookup strategy for properties in subgraphs.
0041  * Note that the nested kind member is used to help interoperate with actual
0042  * Property types.
0043  */
0044 //@{
0045 template < typename T > struct local_property
0046 {
0047     typedef T kind;
0048     local_property(T x) : value(x) {}
0049     T value;
0050 };
0051 
0052 template < typename T > inline local_property< T > local(T x)
0053 {
0054     return local_property< T >(x);
0055 }
0056 
0057 template < typename T > struct global_property
0058 {
0059     typedef T kind;
0060     global_property(T x) : value(x) {}
0061     T value;
0062 };
0063 
0064 template < typename T > inline global_property< T > global(T x)
0065 {
0066     return global_property< T >(x);
0067 }
0068 //@}
0069 
0070 // Invariants of an induced subgraph:
0071 //   - If vertex u is in subgraph g, then u must be in g.parent().
0072 //   - If edge e is in subgraph g, then e must be in g.parent().
0073 //   - If edge e=(u,v) is in the root graph, then edge e
0074 //     is also in any subgraph that contains both vertex u and v.
0075 
0076 // The Graph template parameter must have a vertex_index and edge_index
0077 // internal property. It is assumed that the vertex indices are assigned
0078 // automatically by the graph during a call to add_vertex(). It is not
0079 // assumed that the edge vertices are assigned automatically, they are
0080 // explicitly assigned here.
0081 
0082 template < typename Graph > class subgraph
0083 {
0084     typedef graph_traits< Graph > Traits;
0085     typedef std::list< subgraph< Graph >* > ChildrenList;
0086 
0087 public:
0088     // Graph requirements
0089     typedef typename Traits::vertex_descriptor vertex_descriptor;
0090     typedef typename Traits::edge_descriptor edge_descriptor;
0091     typedef typename Traits::directed_category directed_category;
0092     typedef typename Traits::edge_parallel_category edge_parallel_category;
0093     typedef typename Traits::traversal_category traversal_category;
0094 
0095     // IncidenceGraph requirements
0096     typedef typename Traits::out_edge_iterator out_edge_iterator;
0097     typedef typename Traits::degree_size_type degree_size_type;
0098 
0099     // AdjacencyGraph requirements
0100     typedef typename Traits::adjacency_iterator adjacency_iterator;
0101 
0102     // VertexListGraph requirements
0103     typedef typename Traits::vertex_iterator vertex_iterator;
0104     typedef typename Traits::vertices_size_type vertices_size_type;
0105 
0106     // EdgeListGraph requirements
0107     typedef typename Traits::edge_iterator edge_iterator;
0108     typedef typename Traits::edges_size_type edges_size_type;
0109 
0110     typedef typename Traits::in_edge_iterator in_edge_iterator;
0111 
0112     typedef typename edge_property_type< Graph >::type edge_property_type;
0113     typedef typename vertex_property_type< Graph >::type vertex_property_type;
0114     typedef subgraph_tag graph_tag;
0115     typedef Graph graph_type;
0116     typedef typename graph_property_type< Graph >::type graph_property_type;
0117 
0118     // Create the main graph, the root of the subgraph tree
0119     subgraph() : m_parent(0), m_edge_counter(0) {}
0120 
0121     subgraph(const graph_property_type& p)
0122     : m_graph(p), m_parent(0), m_edge_counter(0)
0123     {
0124     }
0125 
0126     subgraph(vertices_size_type n,
0127         const graph_property_type& p = graph_property_type())
0128     : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
0129     {
0130         typename Graph::vertex_iterator v, v_end;
0131         vertices_size_type i = 0;
0132         for (boost::tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
0133             m_global_vertex[i++] = *v;
0134     }
0135 
0136     // copy constructor
0137     subgraph(const subgraph& x) : m_parent(x.m_parent), m_edge_counter(0)
0138     {
0139         if (x.is_root())
0140         {
0141             m_graph = x.m_graph;
0142             m_edge_counter = x.m_edge_counter;
0143             m_global_vertex = x.m_global_vertex;
0144             m_global_edge = x.m_global_edge;
0145         }
0146         else
0147         {
0148             get_property(*this) = get_property(x);
0149             typename subgraph< Graph >::vertex_iterator vi, vi_end;
0150             boost::tie(vi, vi_end) = vertices(x);
0151             for (; vi != vi_end; ++vi)
0152             {
0153                 add_vertex(x.local_to_global(*vi), *this);
0154             }
0155         }
0156         // Do a deep copy (recursive).
0157         // Only the root graph is copied, the subgraphs contain
0158         // only references to the global vertices they own.
0159         typename subgraph< Graph >::children_iterator i, i_end;
0160         boost::tie(i, i_end) = x.children();
0161         for (; i != i_end; ++i)
0162         {
0163             m_children.push_back(new subgraph< Graph >(*i));
0164             m_children.back()->m_parent = this;
0165         }
0166     }
0167 
0168     ~subgraph()
0169     {
0170         for (typename ChildrenList::iterator i = m_children.begin();
0171              i != m_children.end(); ++i)
0172         {
0173             delete *i;
0174         }
0175     }
0176 
0177     // Return a null vertex descriptor for the graph.
0178     static vertex_descriptor null_vertex() { return Traits::null_vertex(); }
0179 
0180     // Create a subgraph
0181     subgraph< Graph >& create_subgraph()
0182     {
0183         m_children.push_back(new subgraph< Graph >());
0184         m_children.back()->m_parent = this;
0185         return *m_children.back();
0186     }
0187 
0188     // Create a subgraph with the specified vertex set.
0189     template < typename VertexIterator >
0190     subgraph< Graph >& create_subgraph(
0191         VertexIterator first, VertexIterator last)
0192     {
0193         m_children.push_back(new subgraph< Graph >());
0194         m_children.back()->m_parent = this;
0195         for (; first != last; ++first)
0196         {
0197             add_vertex(*first, *m_children.back());
0198         }
0199         return *m_children.back();
0200     }
0201 
0202     // local <-> global descriptor conversion functions
0203     vertex_descriptor local_to_global(vertex_descriptor u_local) const
0204     {
0205         return is_root() ? u_local : m_global_vertex[u_local];
0206     }
0207 
0208     vertex_descriptor global_to_local(vertex_descriptor u_global) const
0209     {
0210         vertex_descriptor u_local;
0211         bool in_subgraph;
0212         if (is_root())
0213             return u_global;
0214         boost::tie(u_local, in_subgraph) = this->find_vertex(u_global);
0215         BOOST_ASSERT(in_subgraph == true);
0216         return u_local;
0217     }
0218 
0219     edge_descriptor local_to_global(edge_descriptor e_local) const
0220     {
0221         return is_root()
0222             ? e_local
0223             : m_global_edge[get(get(edge_index, m_graph), e_local)];
0224     }
0225 
0226     edge_descriptor global_to_local(edge_descriptor e_global) const
0227     {
0228         return is_root() ? e_global
0229                          : (*m_local_edge.find(
0230                                 get(get(edge_index, root().m_graph), e_global)))
0231                                .second;
0232     }
0233 
0234     // Is vertex u (of the root graph) contained in this subgraph?
0235     // If so, return the matching local vertex.
0236     std::pair< vertex_descriptor, bool > find_vertex(
0237         vertex_descriptor u_global) const
0238     {
0239         if (is_root())
0240             return std::make_pair(u_global, true);
0241         typename LocalVertexMap::const_iterator i
0242             = m_local_vertex.find(u_global);
0243         bool valid = i != m_local_vertex.end();
0244         return std::make_pair((valid ? (*i).second : null_vertex()), valid);
0245     }
0246 
0247     // Is edge e (of the root graph) contained in this subgraph?
0248     // If so, return the matching local edge.
0249     std::pair< edge_descriptor, bool > find_edge(edge_descriptor e_global) const
0250     {
0251         if (is_root())
0252             return std::make_pair(e_global, true);
0253         typename LocalEdgeMap::const_iterator i
0254             = m_local_edge.find(get(get(edge_index, root().m_graph), e_global));
0255         bool valid = i != m_local_edge.end();
0256         return std::make_pair((valid ? (*i).second : edge_descriptor()), valid);
0257     }
0258 
0259     // Return the parent graph.
0260     subgraph& parent() { return *m_parent; }
0261     const subgraph& parent() const { return *m_parent; }
0262 
0263     // Return true if this is the root subgraph
0264     bool is_root() const { return m_parent == 0; }
0265 
0266     // Return the root graph of the subgraph tree.
0267     subgraph& root() { return is_root() ? *this : m_parent->root(); }
0268 
0269     const subgraph& root() const
0270     {
0271         return is_root() ? *this : m_parent->root();
0272     }
0273 
0274     // Return the children subgraphs of this graph/subgraph.
0275     // Use a list of pointers because the VC++ std::list doesn't like
0276     // storing incomplete type.
0277     typedef indirect_iterator< typename ChildrenList::const_iterator,
0278         subgraph< Graph >, std::bidirectional_iterator_tag >
0279         children_iterator;
0280 
0281     typedef indirect_iterator< typename ChildrenList::const_iterator,
0282         subgraph< Graph > const, std::bidirectional_iterator_tag >
0283         const_children_iterator;
0284 
0285     std::pair< const_children_iterator, const_children_iterator >
0286     children() const
0287     {
0288         return std::make_pair(const_children_iterator(m_children.begin()),
0289             const_children_iterator(m_children.end()));
0290     }
0291 
0292     std::pair< children_iterator, children_iterator > children()
0293     {
0294         return std::make_pair(children_iterator(m_children.begin()),
0295             children_iterator(m_children.end()));
0296     }
0297 
0298     std::size_t num_children() const { return m_children.size(); }
0299 
0300 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0301     // Defualt property access delegates the lookup to global properties.
0302     template < typename Descriptor >
0303     typename graph::detail::bundled_result< Graph, Descriptor >::type&
0304     operator[](Descriptor x)
0305     {
0306         return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)];
0307     }
0308 
0309     template < typename Descriptor >
0310     typename graph::detail::bundled_result< Graph, Descriptor >::type const&
0311     operator[](Descriptor x) const
0312     {
0313         return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)];
0314     }
0315 
0316     // Local property access returns the local property of the given descripor.
0317     template < typename Descriptor >
0318     typename graph::detail::bundled_result< Graph, Descriptor >::type&
0319     operator[](local_property< Descriptor > x)
0320     {
0321         return m_graph[x.value];
0322     }
0323 
0324     template < typename Descriptor >
0325     typename graph::detail::bundled_result< Graph, Descriptor >::type const&
0326     operator[](local_property< Descriptor > x) const
0327     {
0328         return m_graph[x.value];
0329     }
0330 
0331     // Global property access returns the global property associated with the
0332     // given descriptor. This is an alias for the default bundled property
0333     // access operations.
0334     template < typename Descriptor >
0335     typename graph::detail::bundled_result< Graph, Descriptor >::type&
0336     operator[](global_property< Descriptor > x)
0337     {
0338         return (*this)[x.value];
0339     }
0340 
0341     template < typename Descriptor >
0342     typename graph::detail::bundled_result< Graph, Descriptor >::type const&
0343     operator[](global_property< Descriptor > x) const
0344     {
0345         return (*this)[x.value];
0346     }
0347 
0348 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0349 
0350     //  private:
0351     typedef typename property_map< Graph, edge_index_t >::type EdgeIndexMap;
0352     typedef
0353         typename property_traits< EdgeIndexMap >::value_type edge_index_type;
0354     BOOST_STATIC_ASSERT((!is_same< edge_index_type,
0355                          boost::detail::error_property_not_found >::value));
0356 
0357 private:
0358     typedef std::vector< vertex_descriptor > GlobalVertexList;
0359     typedef std::vector< edge_descriptor > GlobalEdgeList;
0360     typedef std::map< vertex_descriptor, vertex_descriptor > LocalVertexMap;
0361     typedef std::map< edge_index_type, edge_descriptor > LocalEdgeMap;
0362     // TODO: Should the LocalVertexMap be: map<index_type, descriptor>?
0363     // TODO: Can we relax the indexing requirement if both descriptors are
0364     // LessThanComparable?
0365     // TODO: Should we really be using unorderd_map for improved lookup times?
0366 
0367 public: // Probably shouldn't be public....
0368     Graph m_graph;
0369     subgraph< Graph >* m_parent;
0370     edge_index_type m_edge_counter; // for generating unique edge indices
0371     ChildrenList m_children;
0372     GlobalVertexList m_global_vertex; // local -> global
0373     LocalVertexMap m_local_vertex; // global -> local
0374     GlobalEdgeList m_global_edge; // local -> global
0375     LocalEdgeMap m_local_edge; // global -> local
0376 
0377     edge_descriptor local_add_edge(vertex_descriptor u_local,
0378         vertex_descriptor v_local, edge_descriptor e_global)
0379     {
0380         edge_descriptor e_local;
0381         bool inserted;
0382         boost::tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
0383         put(edge_index, m_graph, e_local, m_edge_counter++);
0384         m_global_edge.push_back(e_global);
0385         m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
0386         return e_local;
0387     }
0388 };
0389 
0390 template < typename Graph >
0391 struct vertex_bundle_type< subgraph< Graph > > : vertex_bundle_type< Graph >
0392 {
0393 };
0394 
0395 template < typename Graph >
0396 struct edge_bundle_type< subgraph< Graph > > : edge_bundle_type< Graph >
0397 {
0398 };
0399 
0400 template < typename Graph >
0401 struct graph_bundle_type< subgraph< Graph > > : graph_bundle_type< Graph >
0402 {
0403 };
0404 
0405 //===========================================================================
0406 // Functions special to the Subgraph Class
0407 
0408 template < typename G >
0409 typename subgraph< G >::vertex_descriptor add_vertex(
0410     typename subgraph< G >::vertex_descriptor u_global, subgraph< G >& g)
0411 {
0412     BOOST_ASSERT(!g.is_root());
0413     typename subgraph< G >::vertex_descriptor u_local;
0414     bool exists_local;
0415     boost::tie(u_local, exists_local) = g.find_vertex(u_global);
0416 
0417     if (!exists_local)
0418     {
0419         typename subgraph< G >::vertex_descriptor v_global;
0420         typename subgraph< G >::edge_descriptor e_global;
0421         // call recursion for parent subgraph
0422         if (!g.parent().is_root())
0423             add_vertex(u_global, g.parent());
0424 
0425         u_local = add_vertex(g.m_graph);
0426         g.m_global_vertex.push_back(u_global);
0427         g.m_local_vertex[u_global] = u_local;
0428 
0429         subgraph< G >& r = g.root();
0430 
0431         // remember edge global and local maps
0432         {
0433             typename subgraph< G >::out_edge_iterator ei, ei_end;
0434             for (boost::tie(ei, ei_end) = out_edges(u_global, r); ei != ei_end;
0435                  ++ei)
0436             {
0437                 e_global = *ei;
0438                 v_global = target(e_global, r);
0439                 if (g.find_vertex(v_global).second == true)
0440                     g.local_add_edge(
0441                         u_local, g.global_to_local(v_global), e_global);
0442             }
0443         }
0444         if (is_directed(g))
0445         { // not necessary for undirected graph
0446             typename subgraph< G >::vertex_iterator vi, vi_end;
0447             typename subgraph< G >::out_edge_iterator ei, ei_end;
0448             for (boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi)
0449             {
0450                 v_global = *vi;
0451                 if (v_global == u_global)
0452                     continue; // don't insert self loops twice!
0453                 if (!g.find_vertex(v_global).second)
0454                     continue; // not a subgraph vertex => try next one
0455                 for (boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end;
0456                      ++ei)
0457                 {
0458                     e_global = *ei;
0459                     if (target(e_global, r) == u_global)
0460                     {
0461                         g.local_add_edge(
0462                             g.global_to_local(v_global), u_local, e_global);
0463                     }
0464                 }
0465             }
0466         }
0467     }
0468     return u_local;
0469 }
0470 
0471 // NOTE: Descriptors are local unless otherwise noted.
0472 
0473 //===========================================================================
0474 // Functions required by the IncidenceGraph concept
0475 
0476 template < typename G >
0477 std::pair< typename graph_traits< G >::out_edge_iterator,
0478     typename graph_traits< G >::out_edge_iterator >
0479 out_edges(
0480     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
0481 {
0482     return out_edges(v, g.m_graph);
0483 }
0484 
0485 template < typename G >
0486 typename graph_traits< G >::degree_size_type out_degree(
0487     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
0488 {
0489     return out_degree(v, g.m_graph);
0490 }
0491 
0492 template < typename G >
0493 typename graph_traits< G >::vertex_descriptor source(
0494     typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g)
0495 {
0496     return source(e, g.m_graph);
0497 }
0498 
0499 template < typename G >
0500 typename graph_traits< G >::vertex_descriptor target(
0501     typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g)
0502 {
0503     return target(e, g.m_graph);
0504 }
0505 
0506 //===========================================================================
0507 // Functions required by the BidirectionalGraph concept
0508 
0509 template < typename G >
0510 std::pair< typename graph_traits< G >::in_edge_iterator,
0511     typename graph_traits< G >::in_edge_iterator >
0512 in_edges(
0513     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
0514 {
0515     return in_edges(v, g.m_graph);
0516 }
0517 
0518 template < typename G >
0519 typename graph_traits< G >::degree_size_type in_degree(
0520     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
0521 {
0522     return in_degree(v, g.m_graph);
0523 }
0524 
0525 template < typename G >
0526 typename graph_traits< G >::degree_size_type degree(
0527     typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
0528 {
0529     return degree(v, g.m_graph);
0530 }
0531 
0532 //===========================================================================
0533 // Functions required by the AdjacencyGraph concept
0534 
0535 template < typename G >
0536 std::pair< typename subgraph< G >::adjacency_iterator,
0537     typename subgraph< G >::adjacency_iterator >
0538 adjacent_vertices(
0539     typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g)
0540 {
0541     return adjacent_vertices(v, g.m_graph);
0542 }
0543 
0544 //===========================================================================
0545 // Functions required by the VertexListGraph concept
0546 
0547 template < typename G >
0548 std::pair< typename subgraph< G >::vertex_iterator,
0549     typename subgraph< G >::vertex_iterator >
0550 vertices(const subgraph< G >& g)
0551 {
0552     return vertices(g.m_graph);
0553 }
0554 
0555 template < typename G >
0556 typename subgraph< G >::vertices_size_type num_vertices(const subgraph< G >& g)
0557 {
0558     return num_vertices(g.m_graph);
0559 }
0560 
0561 //===========================================================================
0562 // Functions required by the EdgeListGraph concept
0563 
0564 template < typename G >
0565 std::pair< typename subgraph< G >::edge_iterator,
0566     typename subgraph< G >::edge_iterator >
0567 edges(const subgraph< G >& g)
0568 {
0569     return edges(g.m_graph);
0570 }
0571 
0572 template < typename G >
0573 typename subgraph< G >::edges_size_type num_edges(const subgraph< G >& g)
0574 {
0575     return num_edges(g.m_graph);
0576 }
0577 
0578 //===========================================================================
0579 // Functions required by the AdjacencyMatrix concept
0580 
0581 template < typename G >
0582 std::pair< typename subgraph< G >::edge_descriptor, bool > edge(
0583     typename subgraph< G >::vertex_descriptor u,
0584     typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g)
0585 {
0586     return edge(u, v, g.m_graph);
0587 }
0588 
0589 //===========================================================================
0590 // Functions required by the MutableGraph concept
0591 
0592 namespace detail
0593 {
0594 
0595     template < typename Vertex, typename Edge, typename Graph >
0596     void add_edge_recur_down(
0597         Vertex u_global, Vertex v_global, Edge e_global, subgraph< Graph >& g);
0598 
0599     template < typename Vertex, typename Edge, typename Children, typename G >
0600     void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
0601         Children& c, subgraph< G >* orig)
0602     {
0603         for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
0604         {
0605             if ((*i)->find_vertex(u_global).second
0606                 && (*i)->find_vertex(v_global).second)
0607             {
0608                 add_edge_recur_down(u_global, v_global, e_global, **i, orig);
0609             }
0610         }
0611     }
0612 
0613     template < typename Vertex, typename Edge, typename Graph >
0614     void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
0615         subgraph< Graph >& g, subgraph< Graph >* orig)
0616     {
0617         if (&g != orig)
0618         {
0619             // add local edge only if u_global and v_global are in subgraph g
0620             Vertex u_local, v_local;
0621             bool u_in_subgraph, v_in_subgraph;
0622             boost::tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
0623             boost::tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
0624             if (u_in_subgraph && v_in_subgraph)
0625             {
0626                 g.local_add_edge(u_local, v_local, e_global);
0627             }
0628         }
0629         children_add_edge(u_global, v_global, e_global, g.m_children, orig);
0630     }
0631 
0632     template < typename Vertex, typename Graph >
0633     std::pair< typename subgraph< Graph >::edge_descriptor, bool >
0634     add_edge_recur_up(Vertex u_global, Vertex v_global,
0635         const typename Graph::edge_property_type& ep, subgraph< Graph >& g,
0636         subgraph< Graph >* orig)
0637     {
0638         if (g.is_root())
0639         {
0640             typename subgraph< Graph >::edge_descriptor e_global;
0641             bool inserted;
0642             boost::tie(e_global, inserted)
0643                 = add_edge(u_global, v_global, ep, g.m_graph);
0644             put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
0645             g.m_global_edge.push_back(e_global);
0646             children_add_edge(u_global, v_global, e_global, g.m_children, orig);
0647             return std::make_pair(e_global, inserted);
0648         }
0649         else
0650         {
0651             return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
0652         }
0653     }
0654 
0655 } // namespace detail
0656 
0657 // Add an edge to the subgraph g, specified by the local vertex descriptors u
0658 // and v. In addition, the edge will be added to any (all) other subgraphs that
0659 // contain vertex descriptors u and v.
0660 
0661 template < typename G >
0662 std::pair< typename subgraph< G >::edge_descriptor, bool > add_edge(
0663     typename subgraph< G >::vertex_descriptor u,
0664     typename subgraph< G >::vertex_descriptor v,
0665     const typename G::edge_property_type& ep, subgraph< G >& g)
0666 {
0667     if (g.is_root())
0668     {
0669         // u and v are really global
0670         return detail::add_edge_recur_up(u, v, ep, g, &g);
0671     }
0672     else
0673     {
0674         typename subgraph< G >::edge_descriptor e_local, e_global;
0675         bool inserted;
0676         boost::tie(e_global, inserted) = detail::add_edge_recur_up(
0677             g.local_to_global(u), g.local_to_global(v), ep, g, &g);
0678         e_local = g.local_add_edge(u, v, e_global);
0679         return std::make_pair(e_local, inserted);
0680     }
0681 }
0682 
0683 template < typename G >
0684 std::pair< typename subgraph< G >::edge_descriptor, bool > add_edge(
0685     typename subgraph< G >::vertex_descriptor u,
0686     typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
0687 {
0688     return add_edge(u, v, typename G::edge_property_type(), g);
0689 }
0690 
0691 namespace detail
0692 {
0693     //-------------------------------------------------------------------------
0694     // implementation of remove_edge(u,v,g)
0695     template < typename Vertex, typename Graph >
0696     void remove_edge_recur_down(
0697         Vertex u_global, Vertex v_global, subgraph< Graph >& g);
0698 
0699     template < typename Vertex, typename Children >
0700     void children_remove_edge(Vertex u_global, Vertex v_global, Children& c)
0701     {
0702         for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
0703         {
0704             if ((*i)->find_vertex(u_global).second
0705                 && (*i)->find_vertex(v_global).second)
0706             {
0707                 remove_edge_recur_down(u_global, v_global, **i);
0708             }
0709         }
0710     }
0711 
0712     template < typename Vertex, typename Graph >
0713     void remove_edge_recur_down(
0714         Vertex u_global, Vertex v_global, subgraph< Graph >& g)
0715     {
0716         Vertex u_local, v_local;
0717         u_local = g.m_local_vertex[u_global];
0718         v_local = g.m_local_vertex[v_global];
0719         remove_edge(u_local, v_local, g.m_graph);
0720         children_remove_edge(u_global, v_global, g.m_children);
0721     }
0722 
0723     template < typename Vertex, typename Graph >
0724     void remove_edge_recur_up(
0725         Vertex u_global, Vertex v_global, subgraph< Graph >& g)
0726     {
0727         if (g.is_root())
0728         {
0729             remove_edge(u_global, v_global, g.m_graph);
0730             children_remove_edge(u_global, v_global, g.m_children);
0731         }
0732         else
0733         {
0734             remove_edge_recur_up(u_global, v_global, *g.m_parent);
0735         }
0736     }
0737 
0738     //-------------------------------------------------------------------------
0739     // implementation of remove_edge(e,g)
0740 
0741     template < typename G, typename Edge, typename Children >
0742     void children_remove_edge(Edge e_global, Children& c)
0743     {
0744         for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
0745         {
0746             std::pair< typename subgraph< G >::edge_descriptor, bool > found
0747                 = (*i)->find_edge(e_global);
0748             if (!found.second)
0749             {
0750                 continue;
0751             }
0752             children_remove_edge< G >(e_global, (*i)->m_children);
0753             remove_edge(found.first, (*i)->m_graph);
0754         }
0755     }
0756 
0757 } // namespace detail
0758 
0759 template < typename G >
0760 void remove_edge(typename subgraph< G >::vertex_descriptor u,
0761     typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
0762 {
0763     if (g.is_root())
0764     {
0765         detail::remove_edge_recur_up(u, v, g);
0766     }
0767     else
0768     {
0769         detail::remove_edge_recur_up(
0770             g.local_to_global(u), g.local_to_global(v), g);
0771     }
0772 }
0773 
0774 template < typename G >
0775 void remove_edge(typename subgraph< G >::edge_descriptor e, subgraph< G >& g)
0776 {
0777     typename subgraph< G >::edge_descriptor e_global = g.local_to_global(e);
0778 #ifndef NDEBUG
0779     std::pair< typename subgraph< G >::edge_descriptor, bool > fe
0780         = g.find_edge(e_global);
0781     BOOST_ASSERT(fe.second && fe.first == e);
0782 #endif // NDEBUG
0783     subgraph< G >& root = g.root(); // chase to root
0784     detail::children_remove_edge< G >(e_global, root.m_children);
0785     remove_edge(e_global, root.m_graph); // kick edge from root
0786 }
0787 
0788 // This is slow, but there may not be a good way to do it safely otherwise
0789 template < typename Predicate, typename G >
0790 void remove_edge_if(Predicate p, subgraph< G >& g)
0791 {
0792     while (true)
0793     {
0794         bool any_removed = false;
0795         typedef typename subgraph< G >::edge_iterator ei_type;
0796         for (std::pair< ei_type, ei_type > ep = edges(g); ep.first != ep.second;
0797              ++ep.first)
0798         {
0799             if (p(*ep.first))
0800             {
0801                 any_removed = true;
0802                 remove_edge(*ep.first, g);
0803                 break; /* Since iterators may be invalidated */
0804             }
0805         }
0806         if (!any_removed)
0807             break;
0808     }
0809 }
0810 
0811 template < typename G >
0812 void clear_vertex(typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
0813 {
0814     while (true)
0815     {
0816         typedef typename subgraph< G >::out_edge_iterator oei_type;
0817         std::pair< oei_type, oei_type > p = out_edges(v, g);
0818         if (p.first == p.second)
0819             break;
0820         remove_edge(*p.first, g);
0821     }
0822 }
0823 
0824 namespace detail
0825 {
0826     template < typename G >
0827     typename subgraph< G >::vertex_descriptor add_vertex_recur_up(
0828         subgraph< G >& g)
0829     {
0830         typename subgraph< G >::vertex_descriptor u_local, u_global;
0831         if (g.is_root())
0832         {
0833             u_global = add_vertex(g.m_graph);
0834             g.m_global_vertex.push_back(u_global);
0835         }
0836         else
0837         {
0838             u_global = add_vertex_recur_up(*g.m_parent);
0839             u_local = add_vertex(g.m_graph);
0840             g.m_global_vertex.push_back(u_global);
0841             g.m_local_vertex[u_global] = u_local;
0842         }
0843         return u_global;
0844     }
0845 } // namespace detail
0846 
0847 template < typename G >
0848 typename subgraph< G >::vertex_descriptor add_vertex(subgraph< G >& g)
0849 {
0850     typename subgraph< G >::vertex_descriptor u_local, u_global;
0851     if (g.is_root())
0852     {
0853         u_global = add_vertex(g.m_graph);
0854         g.m_global_vertex.push_back(u_global);
0855         u_local = u_global;
0856     }
0857     else
0858     {
0859         u_global = detail::add_vertex_recur_up(g.parent());
0860         u_local = add_vertex(g.m_graph);
0861         g.m_global_vertex.push_back(u_global);
0862         g.m_local_vertex[u_global] = u_local;
0863     }
0864     return u_local;
0865 }
0866 
0867 #if 0
0868 // TODO: Under Construction
0869 template <typename G>
0870 void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
0871 { BOOST_ASSERT(false); }
0872 #endif
0873 
0874 //===========================================================================
0875 // Functions required by the PropertyGraph concept
0876 
0877 /**
0878  * The global property map returns the global properties associated with local
0879  * descriptors.
0880  */
0881 template < typename GraphPtr, typename PropertyMap, typename Tag >
0882 class subgraph_global_property_map
0883 : public put_get_helper< typename property_traits< PropertyMap >::reference,
0884       subgraph_global_property_map< GraphPtr, PropertyMap, Tag > >
0885 {
0886     typedef property_traits< PropertyMap > Traits;
0887 
0888 public:
0889     typedef typename mpl::if_<
0890         is_const< typename remove_pointer< GraphPtr >::type >,
0891         readable_property_map_tag, typename Traits::category >::type category;
0892     typedef typename Traits::value_type value_type;
0893     typedef typename Traits::key_type key_type;
0894     typedef typename Traits::reference reference;
0895 
0896     subgraph_global_property_map() {}
0897 
0898     subgraph_global_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {}
0899 
0900     reference operator[](key_type e) const
0901     {
0902         PropertyMap pmap = get(m_tag, m_g->root().m_graph);
0903         return m_g->is_root() ? pmap[e] : pmap[m_g->local_to_global(e)];
0904     }
0905 
0906     GraphPtr m_g;
0907     Tag m_tag;
0908 };
0909 
0910 /**
0911  * The local property map returns the local property associated with the local
0912  * descriptors.
0913  */
0914 template < typename GraphPtr, typename PropertyMap, typename Tag >
0915 class subgraph_local_property_map
0916 : public put_get_helper< typename property_traits< PropertyMap >::reference,
0917       subgraph_local_property_map< GraphPtr, PropertyMap, Tag > >
0918 {
0919     typedef property_traits< PropertyMap > Traits;
0920 
0921 public:
0922     typedef typename mpl::if_<
0923         is_const< typename remove_pointer< GraphPtr >::type >,
0924         readable_property_map_tag, typename Traits::category >::type category;
0925     typedef typename Traits::value_type value_type;
0926     typedef typename Traits::key_type key_type;
0927     typedef typename Traits::reference reference;
0928 
0929     typedef Tag tag;
0930     typedef PropertyMap pmap;
0931 
0932     subgraph_local_property_map() {}
0933 
0934     subgraph_local_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {}
0935 
0936     reference operator[](key_type e) const
0937     {
0938         // Get property map on the underlying graph.
0939         PropertyMap pmap = get(m_tag, m_g->m_graph);
0940         return pmap[e];
0941     }
0942 
0943     GraphPtr m_g;
0944     Tag m_tag;
0945 };
0946 
0947 namespace detail
0948 {
0949     // Extract the actual tags from local or global property maps so we don't
0950     // try to find non-properties.
0951     template < typename P > struct extract_lg_tag
0952     {
0953         typedef P type;
0954     };
0955     template < typename P > struct extract_lg_tag< local_property< P > >
0956     {
0957         typedef P type;
0958     };
0959     template < typename P > struct extract_lg_tag< global_property< P > >
0960     {
0961         typedef P type;
0962     };
0963 
0964     // NOTE: Mysterious Property template parameter unused in both metafunction
0965     // classes.
0966     struct subgraph_global_pmap
0967     {
0968         template < class Tag, class SubGraph, class Property > struct bind_
0969         {
0970             typedef typename SubGraph::graph_type Graph;
0971             typedef SubGraph* SubGraphPtr;
0972             typedef const SubGraph* const_SubGraphPtr;
0973             typedef typename extract_lg_tag< Tag >::type TagType;
0974             typedef typename property_map< Graph, TagType >::type PMap;
0975             typedef
0976                 typename property_map< Graph, TagType >::const_type const_PMap;
0977 
0978         public:
0979             typedef subgraph_global_property_map< SubGraphPtr, PMap, TagType >
0980                 type;
0981             typedef subgraph_global_property_map< const_SubGraphPtr, const_PMap,
0982                 TagType >
0983                 const_type;
0984         };
0985     };
0986 
0987     struct subgraph_local_pmap
0988     {
0989         template < class Tag, class SubGraph, class Property > struct bind_
0990         {
0991             typedef typename SubGraph::graph_type Graph;
0992             typedef SubGraph* SubGraphPtr;
0993             typedef const SubGraph* const_SubGraphPtr;
0994             typedef typename extract_lg_tag< Tag >::type TagType;
0995             typedef typename property_map< Graph, TagType >::type PMap;
0996             typedef
0997                 typename property_map< Graph, TagType >::const_type const_PMap;
0998 
0999         public:
1000             typedef subgraph_local_property_map< SubGraphPtr, PMap, TagType >
1001                 type;
1002             typedef subgraph_local_property_map< const_SubGraphPtr, const_PMap,
1003                 TagType >
1004                 const_type;
1005         };
1006     };
1007 
1008     // These metafunctions select the corresponding metafunctions above, and
1009     // are used by the choose_pmap metafunction below to specialize the choice
1010     // of local/global property map. By default, we defer to the global
1011     // property.
1012     template < class Tag > struct subgraph_choose_pmap_helper
1013     {
1014         typedef subgraph_global_pmap type;
1015     };
1016     template < class Tag >
1017     struct subgraph_choose_pmap_helper< local_property< Tag > >
1018     {
1019         typedef subgraph_local_pmap type;
1020     };
1021     template < class Tag >
1022     struct subgraph_choose_pmap_helper< global_property< Tag > >
1023     {
1024         typedef subgraph_global_pmap type;
1025     };
1026 
1027     // As above, unless we're requesting vertex_index_t. Then it's always a
1028     // local property map. This enables the correct translation of descriptors
1029     // between local and global layers.
1030     template <> struct subgraph_choose_pmap_helper< vertex_index_t >
1031     {
1032         typedef subgraph_local_pmap type;
1033     };
1034     template <>
1035     struct subgraph_choose_pmap_helper< local_property< vertex_index_t > >
1036     {
1037         typedef subgraph_local_pmap type;
1038     };
1039     template <>
1040     struct subgraph_choose_pmap_helper< global_property< vertex_index_t > >
1041     {
1042         typedef subgraph_local_pmap type;
1043     };
1044 
1045     // Determine the kind of property. If SameType<Tag, vertex_index_t>, then
1046     // the property lookup is always local. Otherwise, the lookup is global.
1047     // NOTE: Property parameter is basically unused.
1048     template < class Tag, class Graph, class Property >
1049     struct subgraph_choose_pmap
1050     {
1051         typedef typename subgraph_choose_pmap_helper< Tag >::type Helper;
1052         typedef typename Helper::template bind_< Tag, Graph, Property > Bind;
1053         typedef typename Bind::type type;
1054         typedef typename Bind::const_type const_type;
1055     };
1056 
1057     // Used by the vertex/edge property selectors to determine the kind(s) of
1058     // property maps used by the property_map type generator.
1059     struct subgraph_property_generator
1060     {
1061         template < class SubGraph, class Property, class Tag > struct bind_
1062         {
1063             typedef subgraph_choose_pmap< Tag, SubGraph, Property > Choice;
1064             typedef typename Choice::type type;
1065             typedef typename Choice::const_type const_type;
1066         };
1067     };
1068 
1069 } // namespace detail
1070 
1071 template <> struct vertex_property_selector< subgraph_tag >
1072 {
1073     typedef detail::subgraph_property_generator type;
1074 };
1075 
1076 template <> struct edge_property_selector< subgraph_tag >
1077 {
1078     typedef detail::subgraph_property_generator type;
1079 };
1080 
1081 // ==================================================
1082 // get(p, g), get(p, g, k), and put(p, g, k, v)
1083 // ==================================================
1084 template < typename G, typename Property >
1085 typename property_map< subgraph< G >, Property >::type get(
1086     Property p, subgraph< G >& g)
1087 {
1088     typedef typename property_map< subgraph< G >, Property >::type PMap;
1089     return PMap(&g, p);
1090 }
1091 
1092 template < typename G, typename Property >
1093 typename property_map< subgraph< G >, Property >::const_type get(
1094     Property p, const subgraph< G >& g)
1095 {
1096     typedef typename property_map< subgraph< G >, Property >::const_type PMap;
1097     return PMap(&g, p);
1098 }
1099 
1100 template < typename G, typename Property, typename Key >
1101 typename property_traits<
1102     typename property_map< subgraph< G >, Property >::const_type >::value_type
1103 get(Property p, const subgraph< G >& g, const Key& k)
1104 {
1105     typedef typename property_map< subgraph< G >, Property >::const_type PMap;
1106     PMap pmap(&g, p);
1107     return pmap[k];
1108 }
1109 
1110 template < typename G, typename Property, typename Key, typename Value >
1111 void put(Property p, subgraph< G >& g, const Key& k, const Value& val)
1112 {
1113     typedef typename property_map< subgraph< G >, Property >::type PMap;
1114     PMap pmap(&g, p);
1115     pmap[k] = val;
1116 }
1117 
1118 // ==================================================
1119 // get(global(p), g)
1120 // NOTE: get(global(p), g, k) and put(global(p), g, k, v) not supported
1121 // ==================================================
1122 template < typename G, typename Property >
1123 typename property_map< subgraph< G >, global_property< Property > >::type get(
1124     global_property< Property > p, subgraph< G >& g)
1125 {
1126     typedef typename property_map< subgraph< G >,
1127         global_property< Property > >::type Map;
1128     return Map(&g, p.value);
1129 }
1130 
1131 template < typename G, typename Property >
1132 typename property_map< subgraph< G >, global_property< Property > >::const_type
1133 get(global_property< Property > p, const subgraph< G >& g)
1134 {
1135     typedef typename property_map< subgraph< G >,
1136         global_property< Property > >::const_type Map;
1137     return Map(&g, p.value);
1138 }
1139 
1140 // ==================================================
1141 // get(local(p), g)
1142 // NOTE: get(local(p), g, k) and put(local(p), g, k, v) not supported
1143 // ==================================================
1144 template < typename G, typename Property >
1145 typename property_map< subgraph< G >, local_property< Property > >::type get(
1146     local_property< Property > p, subgraph< G >& g)
1147 {
1148     typedef
1149         typename property_map< subgraph< G >, local_property< Property > >::type
1150             Map;
1151     return Map(&g, p.value);
1152 }
1153 
1154 template < typename G, typename Property >
1155 typename property_map< subgraph< G >, local_property< Property > >::const_type
1156 get(local_property< Property > p, const subgraph< G >& g)
1157 {
1158     typedef typename property_map< subgraph< G >,
1159         local_property< Property > >::const_type Map;
1160     return Map(&g, p.value);
1161 }
1162 
1163 template < typename G, typename Tag >
1164 inline typename graph_property< G, Tag >::type& get_property(
1165     subgraph< G >& g, Tag tag)
1166 {
1167     return get_property(g.m_graph, tag);
1168 }
1169 
1170 template < typename G, typename Tag >
1171 inline const typename graph_property< G, Tag >::type& get_property(
1172     const subgraph< G >& g, Tag tag)
1173 {
1174     return get_property(g.m_graph, tag);
1175 }
1176 
1177 //===========================================================================
1178 // Miscellaneous Functions
1179 
1180 template < typename G >
1181 typename subgraph< G >::vertex_descriptor vertex(
1182     typename subgraph< G >::vertices_size_type n, const subgraph< G >& g)
1183 {
1184     return vertex(n, g.m_graph);
1185 }
1186 
1187 //===========================================================================
1188 // Mutability Traits
1189 // Just pull the mutability traits form the underlying graph. Note that this
1190 // will probably fail (badly) for labeled graphs.
1191 template < typename G > struct graph_mutability_traits< subgraph< G > >
1192 {
1193     typedef typename graph_mutability_traits< G >::category category;
1194 };
1195 
1196 } // namespace boost
1197 
1198 #endif // BOOST_SUBGRAPH_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!