source: NonGTP/Boost/boost/graph/subgraph.hpp @ 857

Revision 857, 30.1 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]1//=======================================================================
2// Copyright 2001 University of Notre Dame.
3// Authors: Jeremy G. Siek and Lie-Quan Lee
4//
5// Distributed under the Boost Software License, Version 1.0. (See
6// accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//=======================================================================
9
10#ifndef BOOST_SUBGRAPH_HPP
11#define BOOST_SUBGRAPH_HPP
12
13// UNDER CONSTRUCTION
14
15#include <boost/config.hpp>
16#include <list>
17#include <vector>
18#include <map>
19#include <cassert>
20#include <boost/graph/graph_traits.hpp>
21#include <boost/graph/properties.hpp>
22#include <boost/iterator/indirect_iterator.hpp>
23
24#include <boost/static_assert.hpp>
25#include <boost/type_traits/is_same.hpp>
26
27namespace boost {
28
29  struct subgraph_tag { };
30
31  // Invariants of an induced subgraph:
32  //   - If vertex u is in subgraph g, then u must be in g.parent().
33  //   - If edge e is in subgraph g, then e must be in g.parent().
34  //   - If edge e=(u,v) is in the root graph, then edge e
35  //     is also in any subgraph that contains both vertex u and v.
36
37  // The Graph template parameter must have a vertex_index
38  // and edge_index internal property. It is assumed that
39  // the vertex indices are assigned automatically by the
40  // graph during a call to add_vertex(). It is not
41  // assumed that the edge vertices are assigned automatically,
42  // they are explicitly assigned here.
43
44  template <typename Graph>
45  class subgraph {
46    typedef graph_traits<Graph> Traits;
47    typedef std::list<subgraph<Graph>*> ChildrenList;
48  public:
49    // Graph requirements
50    typedef typename Traits::vertex_descriptor         vertex_descriptor;
51    typedef typename Traits::edge_descriptor           edge_descriptor;
52    typedef typename Traits::directed_category         directed_category;
53    typedef typename Traits::edge_parallel_category    edge_parallel_category;
54    typedef typename Traits::traversal_category        traversal_category;
55
56    static vertex_descriptor null_vertex()
57    {
58      return Traits::null_vertex();
59    }
60
61
62    // IncidenceGraph requirements
63    typedef typename Traits::out_edge_iterator         out_edge_iterator;
64    typedef typename Traits::degree_size_type          degree_size_type;
65
66    // AdjacencyGraph requirements
67    typedef typename Traits::adjacency_iterator        adjacency_iterator;
68
69    // VertexListGraph requirements
70    typedef typename Traits::vertex_iterator           vertex_iterator;
71    typedef typename Traits::vertices_size_type        vertices_size_type;
72
73    // EdgeListGraph requirements
74    typedef typename Traits::edge_iterator             edge_iterator;
75    typedef typename Traits::edges_size_type           edges_size_type;
76
77    typedef typename Traits::in_edge_iterator          in_edge_iterator;
78
79    typedef typename Graph::edge_property_type         edge_property_type;
80    typedef typename Graph::vertex_property_type       vertex_property_type;
81    typedef subgraph_tag                               graph_tag;
82    typedef Graph                                      graph_type;
83    typedef typename Graph::graph_property_type        graph_property_type;
84
85    // Constructors
86
87    // Create the main graph, the root of the subgraph tree
88    subgraph()
89      : m_parent(0), m_edge_counter(0)
90    { }
91    subgraph(const graph_property_type& p)
92      : m_graph(p), m_parent(0), m_edge_counter(0)
93    { }
94    subgraph(vertices_size_type n,
95             const graph_property_type& p = graph_property_type())
96      : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
97    {
98      typename Graph::vertex_iterator v, v_end;
99      vertices_size_type i = 0;
100      for (tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
101        m_global_vertex[i++] = *v;
102    }
103
104    // copy constructor
105    subgraph(const subgraph& x)
106      : m_graph(x.m_graph), m_parent(x.m_parent),
107      m_edge_counter(x.m_edge_counter),
108      m_global_vertex(x.m_global_vertex),
109      m_global_edge(x.m_global_edge)
110    {
111      // Do a deep copy
112      for (typename ChildrenList::const_iterator i = x.m_children.begin();
113           i != x.m_children.end(); ++i)
114        m_children.push_back(new subgraph<Graph>( **i ));
115    }
116
117
118    ~subgraph() {
119      for (typename ChildrenList::iterator i = m_children.begin();
120           i != m_children.end(); ++i)
121        delete *i;
122    }
123
124
125    // Create a subgraph
126    subgraph<Graph>& create_subgraph() {
127      m_children.push_back(new subgraph<Graph>());
128      m_children.back()->m_parent = this;
129      return *m_children.back();
130    }
131
132    // Create a subgraph with the specified vertex set.
133    template <typename VertexIterator>
134    subgraph<Graph>& create_subgraph(VertexIterator first,
135                                     VertexIterator last)
136    {
137      m_children.push_back(new subgraph<Graph>());
138      m_children.back()->m_parent = this;
139      for (; first != last; ++first)
140        add_vertex(*first, *m_children.back());
141      return *m_children.back();
142    }
143
144    // local <-> global descriptor conversion functions
145    vertex_descriptor local_to_global(vertex_descriptor u_local) const
146    {
147      return m_global_vertex[u_local];
148    }
149    vertex_descriptor global_to_local(vertex_descriptor u_global) const
150    {
151      vertex_descriptor u_local; bool in_subgraph;
152      tie(u_local, in_subgraph) = this->find_vertex(u_global);
153      assert(in_subgraph == true);
154      return u_local;
155    }
156    edge_descriptor local_to_global(edge_descriptor e_local) const
157    {
158      return m_global_edge[get(get(edge_index, m_graph), e_local)];
159    }
160    edge_descriptor global_to_local(edge_descriptor e_global) const
161    {
162      return
163        (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second;
164    }
165
166    // Is vertex u (of the root graph) contained in this subgraph?
167    // If so, return the matching local vertex.
168    std::pair<vertex_descriptor, bool>
169    find_vertex(vertex_descriptor u_global) const
170    {
171      typename std::map<vertex_descriptor, vertex_descriptor>::const_iterator
172        i = m_local_vertex.find(u_global);
173      bool valid = i != m_local_vertex.end();
174      return std::make_pair((valid ? (*i).second : null_vertex()), valid);
175    }
176
177    // Return the parent graph.
178    subgraph& parent() { return *m_parent; }
179    const subgraph& parent() const { return *m_parent; }
180
181    bool is_root() const { return m_parent == 0; }
182
183    // Return the root graph of the subgraph tree.
184    subgraph& root() {
185      if (this->is_root())
186        return *this;
187      else
188        return m_parent->root();
189    }
190    const subgraph& root() const {
191      if (this->is_root())
192        return *this;
193      else
194        return m_parent->root();
195    }
196
197    // Return the children subgraphs of this graph/subgraph.
198    // Use a list of pointers because the VC++ std::list doesn't like
199    // storing incomplete type.
200    typedef indirect_iterator<
201        typename ChildrenList::const_iterator
202      , subgraph<Graph>
203      , std::bidirectional_iterator_tag
204    >
205    children_iterator;
206
207    typedef indirect_iterator<
208        typename ChildrenList::const_iterator
209      , subgraph<Graph> const
210      , std::bidirectional_iterator_tag
211    >
212    const_children_iterator;
213
214    std::pair<const_children_iterator, const_children_iterator>
215    children() const
216    {
217      return std::make_pair(const_children_iterator(m_children.begin()),
218                            const_children_iterator(m_children.end()));
219    }
220
221    std::pair<children_iterator, children_iterator>
222    children()
223    {
224      return std::make_pair(children_iterator(m_children.begin()),
225                            children_iterator(m_children.end()));
226    }
227
228    std::size_t num_children() const { return m_children.size(); }
229
230#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
231    // Bundled properties support
232    template<typename Descriptor>
233    typename graph::detail::bundled_result<Graph, Descriptor>::type&
234    operator[](Descriptor x)
235    {
236      if (m_parent == 0) return m_graph[x];
237      else return root().m_graph[local_to_global(x)];
238    }
239
240    template<typename Descriptor>
241    typename graph::detail::bundled_result<Graph, Descriptor>::type const&
242    operator[](Descriptor x) const
243    {
244      if (m_parent == 0) return m_graph[x];
245      else return root().m_graph[local_to_global(x)];
246    }
247#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
248
249    //  private:
250    typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap;
251    typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type;
252    BOOST_STATIC_ASSERT((!is_same<edge_index_type,
253                        boost::detail::error_property_not_found>::value));
254
255    Graph m_graph;
256    subgraph<Graph>* m_parent;
257    edge_index_type m_edge_counter; // for generating unique edge indices
258    ChildrenList m_children;
259    std::vector<vertex_descriptor> m_global_vertex; // local -> global
260    std::map<vertex_descriptor, vertex_descriptor> m_local_vertex;  // global -> local
261    std::vector<edge_descriptor> m_global_edge;              // local -> global
262    std::map<edge_index_type, edge_descriptor> m_local_edge; // global -> local
263
264    edge_descriptor
265    local_add_edge(vertex_descriptor u_local, vertex_descriptor v_local,
266                   edge_descriptor e_global)
267    {
268      edge_descriptor e_local;
269      bool inserted;
270      tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
271      put(edge_index, m_graph, e_local, m_edge_counter++);
272      m_global_edge.push_back(e_global);
273      m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
274      return e_local;
275    }
276
277  };
278
279#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
280  template<typename Graph>
281  struct vertex_bundle_type<subgraph<Graph> > : vertex_bundle_type<Graph> { };
282
283  template<typename Graph>
284  struct edge_bundle_type<subgraph<Graph> > : edge_bundle_type<Graph> { };
285#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
286
287  //===========================================================================
288  // Functions special to the Subgraph Class
289
290  template <typename G>
291  typename subgraph<G>::vertex_descriptor
292  add_vertex(typename subgraph<G>::vertex_descriptor u_global,
293             subgraph<G>& g)
294  {
295    assert(!g.is_root());
296    typename subgraph<G>::vertex_descriptor u_local, v_global, uu_global;
297    typename subgraph<G>::edge_descriptor e_global;
298
299    u_local = add_vertex(g.m_graph);
300    g.m_global_vertex.push_back(u_global);
301    g.m_local_vertex[u_global] = u_local;
302
303    subgraph<G>& r = g.root();
304
305    // remember edge global and local maps
306    {
307      typename subgraph<G>::out_edge_iterator ei, ei_end;
308      for (tie(ei, ei_end) = out_edges(u_global, r);
309           ei != ei_end; ++ei) {
310        e_global = *ei;
311        v_global = target(e_global, r);
312        if (g.find_vertex(v_global).second == true)
313          g.local_add_edge(u_local, g.global_to_local(v_global), e_global);
314      }
315    }
316    if (is_directed(g)) { // not necessary for undirected graph
317      typename subgraph<G>::vertex_iterator vi, vi_end;
318      typename subgraph<G>::out_edge_iterator ei, ei_end;
319      for (tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
320        v_global = *vi;
321        if (g.find_vertex(v_global).second)
322          for (tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
323            e_global = *ei;
324            uu_global = target(e_global, r);
325            if (uu_global == u_global && g.find_vertex(v_global).second)
326              g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
327          }
328      }
329    }
330
331    return u_local;
332  }
333
334  //===========================================================================
335  // Functions required by the IncidenceGraph concept
336
337  template <typename G>
338  std::pair<typename graph_traits<G>::out_edge_iterator,
339            typename graph_traits<G>::out_edge_iterator>
340  out_edges(typename graph_traits<G>::vertex_descriptor u_local,
341            const subgraph<G>& g)
342    { return out_edges(u_local, g.m_graph); }
343
344  template <typename G>
345  typename graph_traits<G>::degree_size_type
346  out_degree(typename graph_traits<G>::vertex_descriptor u_local,
347             const subgraph<G>& g)
348    { return out_degree(u_local, g.m_graph); }
349
350  template <typename G>
351  typename graph_traits<G>::vertex_descriptor
352  source(typename graph_traits<G>::edge_descriptor e_local,
353         const subgraph<G>& g)
354    { return source(e_local, g.m_graph); }
355
356  template <typename G>
357  typename graph_traits<G>::vertex_descriptor
358  target(typename graph_traits<G>::edge_descriptor e_local,
359         const subgraph<G>& g)
360    { return target(e_local, g.m_graph); }
361
362  //===========================================================================
363  // Functions required by the BidirectionalGraph concept
364
365  template <typename G>
366  std::pair<typename graph_traits<G>::in_edge_iterator,
367            typename graph_traits<G>::in_edge_iterator>
368  in_edges(typename graph_traits<G>::vertex_descriptor u_local,
369            const subgraph<G>& g)
370    { return in_edges(u_local, g.m_graph); }
371
372  template <typename G>
373  typename graph_traits<G>::degree_size_type
374  in_degree(typename graph_traits<G>::vertex_descriptor u_local,
375             const subgraph<G>& g)
376    { return in_degree(u_local, g.m_graph); }
377
378  template <typename G>
379  typename graph_traits<G>::degree_size_type
380  degree(typename graph_traits<G>::vertex_descriptor u_local,
381             const subgraph<G>& g)
382    { return degree(u_local, g.m_graph); }
383
384  //===========================================================================
385  // Functions required by the AdjacencyGraph concept
386
387  template <typename G>
388  std::pair<typename subgraph<G>::adjacency_iterator,
389            typename subgraph<G>::adjacency_iterator>
390  adjacent_vertices(typename subgraph<G>::vertex_descriptor u_local,
391                    const subgraph<G>& g)
392    { return adjacent_vertices(u_local, g.m_graph); }
393
394  //===========================================================================
395  // Functions required by the VertexListGraph concept
396
397  template <typename G>
398  std::pair<typename subgraph<G>::vertex_iterator,
399            typename subgraph<G>::vertex_iterator>
400  vertices(const subgraph<G>& g)
401    { return vertices(g.m_graph); }
402
403  template <typename G>
404  typename subgraph<G>::vertices_size_type
405  num_vertices(const subgraph<G>& g)
406    { return num_vertices(g.m_graph); }
407
408  //===========================================================================
409  // Functions required by the EdgeListGraph concept
410
411  template <typename G>
412  std::pair<typename subgraph<G>::edge_iterator,
413            typename subgraph<G>::edge_iterator>
414  edges(const subgraph<G>& g)
415    { return edges(g.m_graph); }
416
417  template <typename G>
418  typename subgraph<G>::edges_size_type
419  num_edges(const subgraph<G>& g)
420    { return num_edges(g.m_graph); }
421
422  //===========================================================================
423  // Functions required by the AdjacencyMatrix concept
424
425  template <typename G>
426  std::pair<typename subgraph<G>::edge_descriptor, bool>
427  edge(typename subgraph<G>::vertex_descriptor u_local,
428       typename subgraph<G>::vertex_descriptor v_local,
429       const subgraph<G>& g)
430  {
431    return edge(u_local, v_local, g.m_graph);
432  }
433
434  //===========================================================================
435  // Functions required by the MutableGraph concept
436
437  namespace detail {
438
439    template <typename Vertex, typename Edge, typename Graph>
440    void add_edge_recur_down
441    (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g);
442
443    template <typename Vertex, typename Edge, typename Children, typename G>
444    void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
445                           Children& c, subgraph<G>* orig)
446    {
447      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
448        if ((*i)->find_vertex(u_global).second
449            && (*i)->find_vertex(v_global).second)
450          add_edge_recur_down(u_global, v_global, e_global, **i, orig);
451    }
452
453    template <typename Vertex, typename Edge, typename Graph>
454    void add_edge_recur_down
455      (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g,
456       subgraph<Graph>* orig)
457    {
458      if (&g != orig ) {
459        // add local edge only if u_global and v_global are in subgraph g
460        Vertex u_local, v_local;
461        bool u_in_subgraph, v_in_subgraph;
462        tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
463        tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
464        if (u_in_subgraph && v_in_subgraph)
465          g.local_add_edge(u_local, v_local, e_global);
466      }
467      children_add_edge(u_global, v_global, e_global, g.m_children, orig);
468    }
469
470    template <typename Vertex, typename Graph>
471    std::pair<typename subgraph<Graph>::edge_descriptor, bool>
472    add_edge_recur_up(Vertex u_global, Vertex v_global,
473                      const typename Graph::edge_property_type& ep,
474                      subgraph<Graph>& g, subgraph<Graph>* orig)
475    {
476      if (g.is_root()) {
477        typename subgraph<Graph>::edge_descriptor e_global;
478        bool inserted;
479        tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);
480        put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
481        g.m_global_edge.push_back(e_global);
482        children_add_edge(u_global, v_global, e_global, g.m_children, orig);
483        return std::make_pair(e_global, inserted);
484      } else
485        return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
486    }
487
488  } // namespace detail
489
490  // Add an edge to the subgraph g, specified by the local vertex
491  // descriptors u and v. In addition, the edge will be added to any
492  // other subgraphs which contain vertex descriptors u and v.
493
494  template <typename G>
495  std::pair<typename subgraph<G>::edge_descriptor, bool>
496  add_edge(typename subgraph<G>::vertex_descriptor u_local,
497           typename subgraph<G>::vertex_descriptor v_local,
498           const typename G::edge_property_type& ep,
499           subgraph<G>& g)
500  {
501    if (g.is_root()) // u_local and v_local are really global
502      return detail::add_edge_recur_up(u_local, v_local, ep, g, &g);
503    else {
504      typename subgraph<G>::edge_descriptor e_local, e_global;
505      bool inserted;
506      tie(e_global, inserted) = detail::add_edge_recur_up
507        (g.local_to_global(u_local), g.local_to_global(v_local), ep, g, &g);
508      e_local = g.local_add_edge(u_local, v_local, e_global);
509      return std::make_pair(e_local, inserted);
510    }
511  }
512
513  template <typename G>
514  std::pair<typename subgraph<G>::edge_descriptor, bool>
515  add_edge(typename subgraph<G>::vertex_descriptor u,
516           typename subgraph<G>::vertex_descriptor v,
517           subgraph<G>& g)
518  {
519    typename G::edge_property_type ep;
520    return add_edge(u, v, ep, g);
521  }
522
523  namespace detail {
524
525    //-------------------------------------------------------------------------
526    // implementation of remove_edge(u,v,g)
527
528    template <typename Vertex, typename Graph>
529    void remove_edge_recur_down(Vertex u_global, Vertex v_global,
530                                subgraph<Graph>& g);
531
532    template <typename Vertex, typename Children>
533    void children_remove_edge(Vertex u_global, Vertex v_global,
534                              Children& c)
535    {
536      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
537        if ((*i)->find_vertex(u_global).second
538            && (*i)->find_vertex(v_global).second)
539          remove_edge_recur_down(u_global, v_global, **i);
540    }
541
542    template <typename Vertex, typename Graph>
543    void remove_edge_recur_down(Vertex u_global, Vertex v_global,
544                                subgraph<Graph>& g)
545    {
546      Vertex u_local, v_local;
547      u_local = g.m_local_vertex[u_global];
548      v_local = g.m_local_vertex[v_global];
549      remove_edge(u_local, v_local, g.m_graph);
550      children_remove_edge(u_global, v_global, g.m_children);
551    }
552
553    template <typename Vertex, typename Graph>
554    void remove_edge_recur_up(Vertex u_global, Vertex v_global,
555                              subgraph<Graph>& g)
556    {
557      if (g.is_root()) {
558        remove_edge(u_global, v_global, g.m_graph);
559        children_remove_edge(u_global, v_global, g.m_children);
560      } else
561        remove_edge_recur_up(u_global, v_global, *g.m_parent);
562    }
563
564    //-------------------------------------------------------------------------
565    // implementation of remove_edge(e,g)
566
567    template <typename Edge, typename Graph>
568    void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g);
569
570    template <typename Edge, typename Children>
571    void children_remove_edge(Edge e_global, Children& c)
572    {
573      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
574        if ((*i)->find_vertex(source(e_global, **i)).second
575            && (*i)->find_vertex(target(e_global, **i)).second)
576          remove_edge_recur_down(source(e_global, **i),
577                                 target(e_global, **i), **i);
578    }
579
580    template <typename Edge, typename Graph>
581    void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g)
582    {
583      remove_edge(g.global_to_local(e_global), g.m_graph);
584      children_remove_edge(e_global, g.m_children);
585    }
586
587    template <typename Edge, typename Graph>
588    void remove_edge_recur_up(Edge e_global, subgraph<Graph>& g)
589    {
590      if (g.is_root()) {
591        remove_edge(e_global, g.m_graph);
592        children_remove_edge(e_global, g.m_children);
593      } else
594        remove_edge_recur_up(e_global, *g.m_parent);
595    }
596
597  } // namespace detail
598
599  template <typename G>
600  void
601  remove_edge(typename subgraph<G>::vertex_descriptor u_local,
602              typename subgraph<G>::vertex_descriptor v_local,
603              subgraph<G>& g)
604  {
605    if (g.is_root())
606      detail::remove_edge_recur_up(u_local, v_local, g);
607    else
608      detail::remove_edge_recur_up(g.local_to_global(u_local),
609                                   g.local_to_global(v_local), g);
610  }
611
612  template <typename G>
613  void
614  remove_edge(typename subgraph<G>::edge_descriptor e_local,
615              subgraph<G>& g)
616  {
617    if (g.is_root())
618      detail::remove_edge_recur_up(e_local, g);
619    else
620      detail::remove_edge_recur_up(g.local_to_global(e_local), g);
621  }
622
623  template <typename Predicate, typename G>
624  void
625  remove_edge_if(Predicate p, subgraph<G>& g)
626  {
627    // This is wrong...
628    remove_edge_if(p, g.m_graph);
629  }
630
631  template <typename G>
632  void
633  clear_vertex(typename subgraph<G>::vertex_descriptor v_local,
634               subgraph<G>& g)
635  {
636    // this is wrong...
637    clear_vertex(v_local, g.m_graph);
638  }
639
640  namespace detail {
641
642    template <typename G>
643    typename subgraph<G>::vertex_descriptor
644    add_vertex_recur_up(subgraph<G>& g)
645    {
646      typename subgraph<G>::vertex_descriptor u_local, u_global;
647      if (g.is_root()) {
648        u_global = add_vertex(g.m_graph);
649        g.m_global_vertex.push_back(u_global);
650      } else {
651        u_global = add_vertex_recur_up(*g.m_parent);
652        u_local = add_vertex(g.m_graph);
653        g.m_global_vertex.push_back(u_global);
654        g.m_local_vertex[u_global] = u_local;
655      }
656      return u_global;
657    }
658
659  } // namespace detail
660
661  template <typename G>
662  typename subgraph<G>::vertex_descriptor
663  add_vertex(subgraph<G>& g)
664  {
665    typename subgraph<G>::vertex_descriptor  u_local, u_global;
666    if (g.is_root()) {
667      u_global = add_vertex(g.m_graph);
668      g.m_global_vertex.push_back(u_global);
669      u_local = u_global;
670    } else {
671      u_global = detail::add_vertex_recur_up(g.parent());
672      u_local = add_vertex(g.m_graph);
673      g.m_global_vertex.push_back(u_global);
674      g.m_local_vertex[u_global] = u_local;
675    }
676    return u_local;
677  }
678
679  template <typename G>
680  void remove_vertex(typename subgraph<G>::vertex_descriptor u,
681                     subgraph<G>& g)
682  {
683    // UNDER CONSTRUCTION
684    assert(false);
685  }
686
687
688  //===========================================================================
689  // Functions required by the PropertyGraph concept
690
691  template <typename GraphPtr, typename PropertyMap, typename Tag>
692  class subgraph_global_property_map
693    : public put_get_helper<
694        typename property_traits<PropertyMap>::reference,
695        subgraph_global_property_map<GraphPtr, PropertyMap, Tag> >
696  {
697    typedef property_traits<PropertyMap> Traits;
698  public:
699    typedef typename Traits::category category;
700    typedef typename Traits::value_type value_type;
701    typedef typename Traits::key_type key_type;
702    typedef typename Traits::reference reference;
703
704    subgraph_global_property_map() { }
705
706    subgraph_global_property_map(GraphPtr g)
707      : m_g(g) { }
708
709    inline reference operator[](key_type e_local) const {
710      PropertyMap pmap = get(Tag(), m_g->root().m_graph);
711      if (m_g->m_parent == 0)
712        return pmap[e_local];
713      else
714        return pmap[m_g->local_to_global(e_local)];
715    }
716    GraphPtr m_g;
717  };
718
719  template <typename GraphPtr, typename PropertyMap, typename Tag>
720  class subgraph_local_property_map
721    : public put_get_helper<
722        typename property_traits<PropertyMap>::reference,
723        subgraph_local_property_map<GraphPtr, PropertyMap, Tag> >
724  {
725    typedef property_traits<PropertyMap> Traits;
726  public:
727    typedef typename Traits::category category;
728    typedef typename Traits::value_type value_type;
729    typedef typename Traits::key_type key_type;
730    typedef typename Traits::reference reference;
731
732    subgraph_local_property_map() { }
733
734    subgraph_local_property_map(GraphPtr g)
735      : m_g(g) { }
736
737    inline reference operator[](key_type e_local) const {
738      PropertyMap pmap = get(Tag(), *m_g);
739      return pmap[e_local];
740    }
741    GraphPtr m_g;
742  };
743
744  namespace detail {
745
746    struct subgraph_any_pmap {
747      template <class Tag, class SubGraph, class Property>
748      class bind_ {
749        typedef typename SubGraph::graph_type Graph;
750        typedef SubGraph* SubGraphPtr;
751        typedef const SubGraph* const_SubGraphPtr;
752        typedef typename property_map<Graph, Tag>::type PMap;
753        typedef typename property_map<Graph, Tag>::const_type const_PMap;
754      public:
755        typedef subgraph_global_property_map<SubGraphPtr, PMap, Tag> type;
756        typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, Tag>
757          const_type;
758      };
759    };
760    struct subgraph_id_pmap {
761      template <class Tag, class SubGraph, class Property>
762      struct bind_ {
763        typedef typename SubGraph::graph_type Graph;
764        typedef SubGraph* SubGraphPtr;
765        typedef const SubGraph* const_SubGraphPtr;
766        typedef typename property_map<Graph, Tag>::type PMap;
767        typedef typename property_map<Graph, Tag>::const_type const_PMap;
768      public:
769        typedef subgraph_local_property_map<SubGraphPtr, PMap, Tag> type;
770        typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, Tag>
771          const_type;
772      };
773    };
774    template <class Tag>
775    struct subgraph_choose_pmap_helper {
776      typedef subgraph_any_pmap type;
777    };
778    template <>
779    struct subgraph_choose_pmap_helper<vertex_index_t> {
780      typedef subgraph_id_pmap type;
781    };
782    template <class Tag, class Graph, class Property>
783    struct subgraph_choose_pmap {
784      typedef typename subgraph_choose_pmap_helper<Tag>::type Helper;
785      typedef typename Helper::template bind_<Tag, Graph, Property> Bind;
786      typedef typename Bind::type type;
787      typedef typename Bind::const_type const_type;
788    };
789    struct subgraph_property_generator {
790      template <class SubGraph, class Property, class Tag>
791      struct bind_ {
792        typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice;
793        typedef typename Choice::type type;
794        typedef typename Choice::const_type const_type;
795      };
796    };
797
798  } // namespace detail
799
800  template <>
801  struct vertex_property_selector<subgraph_tag> {
802    typedef detail::subgraph_property_generator type;
803  };
804
805  template <>
806  struct edge_property_selector<subgraph_tag> {
807    typedef detail::subgraph_property_generator type;
808  };
809
810  template <typename G, typename Property>
811  typename property_map< subgraph<G>, Property>::type
812  get(Property, subgraph<G>& g)
813  {
814    typedef typename property_map< subgraph<G>, Property>::type PMap;
815    return PMap(&g);
816  }
817
818  template <typename G, typename Property>
819  typename property_map< subgraph<G>, Property>::const_type
820  get(Property, const subgraph<G>& g)
821  {
822    typedef typename property_map< subgraph<G>, Property>::const_type PMap;
823    return PMap(&g);
824  }
825
826  template <typename G, typename Property, typename Key>
827  typename property_traits<
828    typename property_map< subgraph<G>, Property>::const_type
829  >::value_type
830  get(Property, const subgraph<G>& g, const Key& k)
831  {
832    typedef typename property_map< subgraph<G>, Property>::const_type PMap;
833    PMap pmap(&g);
834    return pmap[k];
835  }
836
837  template <typename G, typename Property, typename Key, typename Value>
838  void
839  put(Property, subgraph<G>& g, const Key& k, const Value& val)
840  {
841    typedef typename property_map< subgraph<G>, Property>::type PMap;
842    PMap pmap(&g);
843    pmap[k] = val;
844  }
845
846  template <typename G, typename Tag>
847  inline
848  typename graph_property<G, Tag>::type&
849  get_property(subgraph<G>& g, Tag tag) {
850    return get_property(g.m_graph, tag);
851  }
852
853  template <typename G, typename Tag>
854  inline
855  const typename graph_property<G, Tag>::type&
856  get_property(const subgraph<G>& g, Tag tag) {
857    return get_property(g.m_graph, tag);
858  }
859
860  //===========================================================================
861  // Miscellaneous Functions
862
863  template <typename G>
864  typename subgraph<G>::vertex_descriptor
865  vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g)
866  {
867    return vertex(n, g.m_graph);
868  }
869
870} // namespace boost
871
872#endif // BOOST_SUBGRAPH_HPP
Note: See TracBrowser for help on using the repository browser.