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