1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/subgraph.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,872 @@
1.4 +//=======================================================================
1.5 +// Copyright 2001 University of Notre Dame.
1.6 +// Authors: Jeremy G. Siek and Lie-Quan Lee
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +
1.13 +#ifndef BOOST_SUBGRAPH_HPP
1.14 +#define BOOST_SUBGRAPH_HPP
1.15 +
1.16 +// UNDER CONSTRUCTION
1.17 +
1.18 +#include <boost/config.hpp>
1.19 +#include <list>
1.20 +#include <vector>
1.21 +#include <map>
1.22 +#include <cassert>
1.23 +#include <boost/graph/graph_traits.hpp>
1.24 +#include <boost/graph/properties.hpp>
1.25 +#include <boost/iterator/indirect_iterator.hpp>
1.26 +
1.27 +#include <boost/static_assert.hpp>
1.28 +#include <boost/type_traits/is_same.hpp>
1.29 +
1.30 +namespace boost {
1.31 +
1.32 + struct subgraph_tag { };
1.33 +
1.34 + // Invariants of an induced subgraph:
1.35 + // - If vertex u is in subgraph g, then u must be in g.parent().
1.36 + // - If edge e is in subgraph g, then e must be in g.parent().
1.37 + // - If edge e=(u,v) is in the root graph, then edge e
1.38 + // is also in any subgraph that contains both vertex u and v.
1.39 +
1.40 + // The Graph template parameter must have a vertex_index
1.41 + // and edge_index internal property. It is assumed that
1.42 + // the vertex indices are assigned automatically by the
1.43 + // graph during a call to add_vertex(). It is not
1.44 + // assumed that the edge vertices are assigned automatically,
1.45 + // they are explicitly assigned here.
1.46 +
1.47 + template <typename Graph>
1.48 + class subgraph {
1.49 + typedef graph_traits<Graph> Traits;
1.50 + typedef std::list<subgraph<Graph>*> ChildrenList;
1.51 + public:
1.52 + // Graph requirements
1.53 + typedef typename Traits::vertex_descriptor vertex_descriptor;
1.54 + typedef typename Traits::edge_descriptor edge_descriptor;
1.55 + typedef typename Traits::directed_category directed_category;
1.56 + typedef typename Traits::edge_parallel_category edge_parallel_category;
1.57 + typedef typename Traits::traversal_category traversal_category;
1.58 +
1.59 + static vertex_descriptor null_vertex()
1.60 + {
1.61 + return Traits::null_vertex();
1.62 + }
1.63 +
1.64 +
1.65 + // IncidenceGraph requirements
1.66 + typedef typename Traits::out_edge_iterator out_edge_iterator;
1.67 + typedef typename Traits::degree_size_type degree_size_type;
1.68 +
1.69 + // AdjacencyGraph requirements
1.70 + typedef typename Traits::adjacency_iterator adjacency_iterator;
1.71 +
1.72 + // VertexListGraph requirements
1.73 + typedef typename Traits::vertex_iterator vertex_iterator;
1.74 + typedef typename Traits::vertices_size_type vertices_size_type;
1.75 +
1.76 + // EdgeListGraph requirements
1.77 + typedef typename Traits::edge_iterator edge_iterator;
1.78 + typedef typename Traits::edges_size_type edges_size_type;
1.79 +
1.80 + typedef typename Traits::in_edge_iterator in_edge_iterator;
1.81 +
1.82 + typedef typename Graph::edge_property_type edge_property_type;
1.83 + typedef typename Graph::vertex_property_type vertex_property_type;
1.84 + typedef subgraph_tag graph_tag;
1.85 + typedef Graph graph_type;
1.86 + typedef typename Graph::graph_property_type graph_property_type;
1.87 +
1.88 + // Constructors
1.89 +
1.90 + // Create the main graph, the root of the subgraph tree
1.91 + subgraph()
1.92 + : m_parent(0), m_edge_counter(0)
1.93 + { }
1.94 + subgraph(const graph_property_type& p)
1.95 + : m_graph(p), m_parent(0), m_edge_counter(0)
1.96 + { }
1.97 + subgraph(vertices_size_type n,
1.98 + const graph_property_type& p = graph_property_type())
1.99 + : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
1.100 + {
1.101 + typename Graph::vertex_iterator v, v_end;
1.102 + vertices_size_type i = 0;
1.103 + for (tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
1.104 + m_global_vertex[i++] = *v;
1.105 + }
1.106 +
1.107 + // copy constructor
1.108 + subgraph(const subgraph& x)
1.109 + : m_graph(x.m_graph), m_parent(x.m_parent),
1.110 + m_edge_counter(x.m_edge_counter),
1.111 + m_global_vertex(x.m_global_vertex),
1.112 + m_global_edge(x.m_global_edge)
1.113 + {
1.114 + // Do a deep copy
1.115 + for (typename ChildrenList::const_iterator i = x.m_children.begin();
1.116 + i != x.m_children.end(); ++i)
1.117 + m_children.push_back(new subgraph<Graph>( **i ));
1.118 + }
1.119 +
1.120 +
1.121 + ~subgraph() {
1.122 + for (typename ChildrenList::iterator i = m_children.begin();
1.123 + i != m_children.end(); ++i)
1.124 + delete *i;
1.125 + }
1.126 +
1.127 +
1.128 + // Create a subgraph
1.129 + subgraph<Graph>& create_subgraph() {
1.130 + m_children.push_back(new subgraph<Graph>());
1.131 + m_children.back()->m_parent = this;
1.132 + return *m_children.back();
1.133 + }
1.134 +
1.135 + // Create a subgraph with the specified vertex set.
1.136 + template <typename VertexIterator>
1.137 + subgraph<Graph>& create_subgraph(VertexIterator first,
1.138 + VertexIterator last)
1.139 + {
1.140 + m_children.push_back(new subgraph<Graph>());
1.141 + m_children.back()->m_parent = this;
1.142 + for (; first != last; ++first)
1.143 + add_vertex(*first, *m_children.back());
1.144 + return *m_children.back();
1.145 + }
1.146 +
1.147 + // local <-> global descriptor conversion functions
1.148 + vertex_descriptor local_to_global(vertex_descriptor u_local) const
1.149 + {
1.150 + return m_global_vertex[u_local];
1.151 + }
1.152 + vertex_descriptor global_to_local(vertex_descriptor u_global) const
1.153 + {
1.154 + vertex_descriptor u_local; bool in_subgraph;
1.155 + tie(u_local, in_subgraph) = this->find_vertex(u_global);
1.156 + assert(in_subgraph == true);
1.157 + return u_local;
1.158 + }
1.159 + edge_descriptor local_to_global(edge_descriptor e_local) const
1.160 + {
1.161 + return m_global_edge[get(get(edge_index, m_graph), e_local)];
1.162 + }
1.163 + edge_descriptor global_to_local(edge_descriptor e_global) const
1.164 + {
1.165 + return
1.166 + (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second;
1.167 + }
1.168 +
1.169 + // Is vertex u (of the root graph) contained in this subgraph?
1.170 + // If so, return the matching local vertex.
1.171 + std::pair<vertex_descriptor, bool>
1.172 + find_vertex(vertex_descriptor u_global) const
1.173 + {
1.174 + typename std::map<vertex_descriptor, vertex_descriptor>::const_iterator
1.175 + i = m_local_vertex.find(u_global);
1.176 + bool valid = i != m_local_vertex.end();
1.177 + return std::make_pair((valid ? (*i).second : null_vertex()), valid);
1.178 + }
1.179 +
1.180 + // Return the parent graph.
1.181 + subgraph& parent() { return *m_parent; }
1.182 + const subgraph& parent() const { return *m_parent; }
1.183 +
1.184 + bool is_root() const { return m_parent == 0; }
1.185 +
1.186 + // Return the root graph of the subgraph tree.
1.187 + subgraph& root() {
1.188 + if (this->is_root())
1.189 + return *this;
1.190 + else
1.191 + return m_parent->root();
1.192 + }
1.193 + const subgraph& root() const {
1.194 + if (this->is_root())
1.195 + return *this;
1.196 + else
1.197 + return m_parent->root();
1.198 + }
1.199 +
1.200 + // Return the children subgraphs of this graph/subgraph.
1.201 + // Use a list of pointers because the VC++ std::list doesn't like
1.202 + // storing incomplete type.
1.203 + typedef indirect_iterator<
1.204 + typename ChildrenList::const_iterator
1.205 + , subgraph<Graph>
1.206 + , std::bidirectional_iterator_tag
1.207 + >
1.208 + children_iterator;
1.209 +
1.210 + typedef indirect_iterator<
1.211 + typename ChildrenList::const_iterator
1.212 + , subgraph<Graph> const
1.213 + , std::bidirectional_iterator_tag
1.214 + >
1.215 + const_children_iterator;
1.216 +
1.217 + std::pair<const_children_iterator, const_children_iterator>
1.218 + children() const
1.219 + {
1.220 + return std::make_pair(const_children_iterator(m_children.begin()),
1.221 + const_children_iterator(m_children.end()));
1.222 + }
1.223 +
1.224 + std::pair<children_iterator, children_iterator>
1.225 + children()
1.226 + {
1.227 + return std::make_pair(children_iterator(m_children.begin()),
1.228 + children_iterator(m_children.end()));
1.229 + }
1.230 +
1.231 + std::size_t num_children() const { return m_children.size(); }
1.232 +
1.233 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.234 + // Bundled properties support
1.235 + template<typename Descriptor>
1.236 + typename graph::detail::bundled_result<Graph, Descriptor>::type&
1.237 + operator[](Descriptor x)
1.238 + {
1.239 + if (m_parent == 0) return m_graph[x];
1.240 + else return root().m_graph[local_to_global(x)];
1.241 + }
1.242 +
1.243 + template<typename Descriptor>
1.244 + typename graph::detail::bundled_result<Graph, Descriptor>::type const&
1.245 + operator[](Descriptor x) const
1.246 + {
1.247 + if (m_parent == 0) return m_graph[x];
1.248 + else return root().m_graph[local_to_global(x)];
1.249 + }
1.250 +#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.251 +
1.252 + // private:
1.253 + typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap;
1.254 + typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type;
1.255 + BOOST_STATIC_ASSERT((!is_same<edge_index_type,
1.256 + boost::detail::error_property_not_found>::value));
1.257 +
1.258 + Graph m_graph;
1.259 + subgraph<Graph>* m_parent;
1.260 + edge_index_type m_edge_counter; // for generating unique edge indices
1.261 + ChildrenList m_children;
1.262 + std::vector<vertex_descriptor> m_global_vertex; // local -> global
1.263 + std::map<vertex_descriptor, vertex_descriptor> m_local_vertex; // global -> local
1.264 + std::vector<edge_descriptor> m_global_edge; // local -> global
1.265 + std::map<edge_index_type, edge_descriptor> m_local_edge; // global -> local
1.266 +
1.267 + edge_descriptor
1.268 + local_add_edge(vertex_descriptor u_local, vertex_descriptor v_local,
1.269 + edge_descriptor e_global)
1.270 + {
1.271 + edge_descriptor e_local;
1.272 + bool inserted;
1.273 + tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
1.274 + put(edge_index, m_graph, e_local, m_edge_counter++);
1.275 + m_global_edge.push_back(e_global);
1.276 + m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
1.277 + return e_local;
1.278 + }
1.279 +
1.280 + };
1.281 +
1.282 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.283 + template<typename Graph>
1.284 + struct vertex_bundle_type<subgraph<Graph> > : vertex_bundle_type<Graph> { };
1.285 +
1.286 + template<typename Graph>
1.287 + struct edge_bundle_type<subgraph<Graph> > : edge_bundle_type<Graph> { };
1.288 +#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.289 +
1.290 + //===========================================================================
1.291 + // Functions special to the Subgraph Class
1.292 +
1.293 + template <typename G>
1.294 + typename subgraph<G>::vertex_descriptor
1.295 + add_vertex(typename subgraph<G>::vertex_descriptor u_global,
1.296 + subgraph<G>& g)
1.297 + {
1.298 + assert(!g.is_root());
1.299 + typename subgraph<G>::vertex_descriptor u_local, v_global, uu_global;
1.300 + typename subgraph<G>::edge_descriptor e_global;
1.301 +
1.302 + u_local = add_vertex(g.m_graph);
1.303 + g.m_global_vertex.push_back(u_global);
1.304 + g.m_local_vertex[u_global] = u_local;
1.305 +
1.306 + subgraph<G>& r = g.root();
1.307 +
1.308 + // remember edge global and local maps
1.309 + {
1.310 + typename subgraph<G>::out_edge_iterator ei, ei_end;
1.311 + for (tie(ei, ei_end) = out_edges(u_global, r);
1.312 + ei != ei_end; ++ei) {
1.313 + e_global = *ei;
1.314 + v_global = target(e_global, r);
1.315 + if (g.find_vertex(v_global).second == true)
1.316 + g.local_add_edge(u_local, g.global_to_local(v_global), e_global);
1.317 + }
1.318 + }
1.319 + if (is_directed(g)) { // not necessary for undirected graph
1.320 + typename subgraph<G>::vertex_iterator vi, vi_end;
1.321 + typename subgraph<G>::out_edge_iterator ei, ei_end;
1.322 + for (tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
1.323 + v_global = *vi;
1.324 + if (g.find_vertex(v_global).second)
1.325 + for (tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
1.326 + e_global = *ei;
1.327 + uu_global = target(e_global, r);
1.328 + if (uu_global == u_global && g.find_vertex(v_global).second)
1.329 + g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
1.330 + }
1.331 + }
1.332 + }
1.333 +
1.334 + return u_local;
1.335 + }
1.336 +
1.337 + //===========================================================================
1.338 + // Functions required by the IncidenceGraph concept
1.339 +
1.340 + template <typename G>
1.341 + std::pair<typename graph_traits<G>::out_edge_iterator,
1.342 + typename graph_traits<G>::out_edge_iterator>
1.343 + out_edges(typename graph_traits<G>::vertex_descriptor u_local,
1.344 + const subgraph<G>& g)
1.345 + { return out_edges(u_local, g.m_graph); }
1.346 +
1.347 + template <typename G>
1.348 + typename graph_traits<G>::degree_size_type
1.349 + out_degree(typename graph_traits<G>::vertex_descriptor u_local,
1.350 + const subgraph<G>& g)
1.351 + { return out_degree(u_local, g.m_graph); }
1.352 +
1.353 + template <typename G>
1.354 + typename graph_traits<G>::vertex_descriptor
1.355 + source(typename graph_traits<G>::edge_descriptor e_local,
1.356 + const subgraph<G>& g)
1.357 + { return source(e_local, g.m_graph); }
1.358 +
1.359 + template <typename G>
1.360 + typename graph_traits<G>::vertex_descriptor
1.361 + target(typename graph_traits<G>::edge_descriptor e_local,
1.362 + const subgraph<G>& g)
1.363 + { return target(e_local, g.m_graph); }
1.364 +
1.365 + //===========================================================================
1.366 + // Functions required by the BidirectionalGraph concept
1.367 +
1.368 + template <typename G>
1.369 + std::pair<typename graph_traits<G>::in_edge_iterator,
1.370 + typename graph_traits<G>::in_edge_iterator>
1.371 + in_edges(typename graph_traits<G>::vertex_descriptor u_local,
1.372 + const subgraph<G>& g)
1.373 + { return in_edges(u_local, g.m_graph); }
1.374 +
1.375 + template <typename G>
1.376 + typename graph_traits<G>::degree_size_type
1.377 + in_degree(typename graph_traits<G>::vertex_descriptor u_local,
1.378 + const subgraph<G>& g)
1.379 + { return in_degree(u_local, g.m_graph); }
1.380 +
1.381 + template <typename G>
1.382 + typename graph_traits<G>::degree_size_type
1.383 + degree(typename graph_traits<G>::vertex_descriptor u_local,
1.384 + const subgraph<G>& g)
1.385 + { return degree(u_local, g.m_graph); }
1.386 +
1.387 + //===========================================================================
1.388 + // Functions required by the AdjacencyGraph concept
1.389 +
1.390 + template <typename G>
1.391 + std::pair<typename subgraph<G>::adjacency_iterator,
1.392 + typename subgraph<G>::adjacency_iterator>
1.393 + adjacent_vertices(typename subgraph<G>::vertex_descriptor u_local,
1.394 + const subgraph<G>& g)
1.395 + { return adjacent_vertices(u_local, g.m_graph); }
1.396 +
1.397 + //===========================================================================
1.398 + // Functions required by the VertexListGraph concept
1.399 +
1.400 + template <typename G>
1.401 + std::pair<typename subgraph<G>::vertex_iterator,
1.402 + typename subgraph<G>::vertex_iterator>
1.403 + vertices(const subgraph<G>& g)
1.404 + { return vertices(g.m_graph); }
1.405 +
1.406 + template <typename G>
1.407 + typename subgraph<G>::vertices_size_type
1.408 + num_vertices(const subgraph<G>& g)
1.409 + { return num_vertices(g.m_graph); }
1.410 +
1.411 + //===========================================================================
1.412 + // Functions required by the EdgeListGraph concept
1.413 +
1.414 + template <typename G>
1.415 + std::pair<typename subgraph<G>::edge_iterator,
1.416 + typename subgraph<G>::edge_iterator>
1.417 + edges(const subgraph<G>& g)
1.418 + { return edges(g.m_graph); }
1.419 +
1.420 + template <typename G>
1.421 + typename subgraph<G>::edges_size_type
1.422 + num_edges(const subgraph<G>& g)
1.423 + { return num_edges(g.m_graph); }
1.424 +
1.425 + //===========================================================================
1.426 + // Functions required by the AdjacencyMatrix concept
1.427 +
1.428 + template <typename G>
1.429 + std::pair<typename subgraph<G>::edge_descriptor, bool>
1.430 + edge(typename subgraph<G>::vertex_descriptor u_local,
1.431 + typename subgraph<G>::vertex_descriptor v_local,
1.432 + const subgraph<G>& g)
1.433 + {
1.434 + return edge(u_local, v_local, g.m_graph);
1.435 + }
1.436 +
1.437 + //===========================================================================
1.438 + // Functions required by the MutableGraph concept
1.439 +
1.440 + namespace detail {
1.441 +
1.442 + template <typename Vertex, typename Edge, typename Graph>
1.443 + void add_edge_recur_down
1.444 + (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g);
1.445 +
1.446 + template <typename Vertex, typename Edge, typename Children, typename G>
1.447 + void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
1.448 + Children& c, subgraph<G>* orig)
1.449 + {
1.450 + for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
1.451 + if ((*i)->find_vertex(u_global).second
1.452 + && (*i)->find_vertex(v_global).second)
1.453 + add_edge_recur_down(u_global, v_global, e_global, **i, orig);
1.454 + }
1.455 +
1.456 + template <typename Vertex, typename Edge, typename Graph>
1.457 + void add_edge_recur_down
1.458 + (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g,
1.459 + subgraph<Graph>* orig)
1.460 + {
1.461 + if (&g != orig ) {
1.462 + // add local edge only if u_global and v_global are in subgraph g
1.463 + Vertex u_local, v_local;
1.464 + bool u_in_subgraph, v_in_subgraph;
1.465 + tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
1.466 + tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
1.467 + if (u_in_subgraph && v_in_subgraph)
1.468 + g.local_add_edge(u_local, v_local, e_global);
1.469 + }
1.470 + children_add_edge(u_global, v_global, e_global, g.m_children, orig);
1.471 + }
1.472 +
1.473 + template <typename Vertex, typename Graph>
1.474 + std::pair<typename subgraph<Graph>::edge_descriptor, bool>
1.475 + add_edge_recur_up(Vertex u_global, Vertex v_global,
1.476 + const typename Graph::edge_property_type& ep,
1.477 + subgraph<Graph>& g, subgraph<Graph>* orig)
1.478 + {
1.479 + if (g.is_root()) {
1.480 + typename subgraph<Graph>::edge_descriptor e_global;
1.481 + bool inserted;
1.482 + tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);
1.483 + put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
1.484 + g.m_global_edge.push_back(e_global);
1.485 + children_add_edge(u_global, v_global, e_global, g.m_children, orig);
1.486 + return std::make_pair(e_global, inserted);
1.487 + } else
1.488 + return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
1.489 + }
1.490 +
1.491 + } // namespace detail
1.492 +
1.493 + // Add an edge to the subgraph g, specified by the local vertex
1.494 + // descriptors u and v. In addition, the edge will be added to any
1.495 + // other subgraphs which contain vertex descriptors u and v.
1.496 +
1.497 + template <typename G>
1.498 + std::pair<typename subgraph<G>::edge_descriptor, bool>
1.499 + add_edge(typename subgraph<G>::vertex_descriptor u_local,
1.500 + typename subgraph<G>::vertex_descriptor v_local,
1.501 + const typename G::edge_property_type& ep,
1.502 + subgraph<G>& g)
1.503 + {
1.504 + if (g.is_root()) // u_local and v_local are really global
1.505 + return detail::add_edge_recur_up(u_local, v_local, ep, g, &g);
1.506 + else {
1.507 + typename subgraph<G>::edge_descriptor e_local, e_global;
1.508 + bool inserted;
1.509 + tie(e_global, inserted) = detail::add_edge_recur_up
1.510 + (g.local_to_global(u_local), g.local_to_global(v_local), ep, g, &g);
1.511 + e_local = g.local_add_edge(u_local, v_local, e_global);
1.512 + return std::make_pair(e_local, inserted);
1.513 + }
1.514 + }
1.515 +
1.516 + template <typename G>
1.517 + std::pair<typename subgraph<G>::edge_descriptor, bool>
1.518 + add_edge(typename subgraph<G>::vertex_descriptor u,
1.519 + typename subgraph<G>::vertex_descriptor v,
1.520 + subgraph<G>& g)
1.521 + {
1.522 + typename G::edge_property_type ep;
1.523 + return add_edge(u, v, ep, g);
1.524 + }
1.525 +
1.526 + namespace detail {
1.527 +
1.528 + //-------------------------------------------------------------------------
1.529 + // implementation of remove_edge(u,v,g)
1.530 +
1.531 + template <typename Vertex, typename Graph>
1.532 + void remove_edge_recur_down(Vertex u_global, Vertex v_global,
1.533 + subgraph<Graph>& g);
1.534 +
1.535 + template <typename Vertex, typename Children>
1.536 + void children_remove_edge(Vertex u_global, Vertex v_global,
1.537 + Children& c)
1.538 + {
1.539 + for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
1.540 + if ((*i)->find_vertex(u_global).second
1.541 + && (*i)->find_vertex(v_global).second)
1.542 + remove_edge_recur_down(u_global, v_global, **i);
1.543 + }
1.544 +
1.545 + template <typename Vertex, typename Graph>
1.546 + void remove_edge_recur_down(Vertex u_global, Vertex v_global,
1.547 + subgraph<Graph>& g)
1.548 + {
1.549 + Vertex u_local, v_local;
1.550 + u_local = g.m_local_vertex[u_global];
1.551 + v_local = g.m_local_vertex[v_global];
1.552 + remove_edge(u_local, v_local, g.m_graph);
1.553 + children_remove_edge(u_global, v_global, g.m_children);
1.554 + }
1.555 +
1.556 + template <typename Vertex, typename Graph>
1.557 + void remove_edge_recur_up(Vertex u_global, Vertex v_global,
1.558 + subgraph<Graph>& g)
1.559 + {
1.560 + if (g.is_root()) {
1.561 + remove_edge(u_global, v_global, g.m_graph);
1.562 + children_remove_edge(u_global, v_global, g.m_children);
1.563 + } else
1.564 + remove_edge_recur_up(u_global, v_global, *g.m_parent);
1.565 + }
1.566 +
1.567 + //-------------------------------------------------------------------------
1.568 + // implementation of remove_edge(e,g)
1.569 +
1.570 + template <typename Edge, typename Graph>
1.571 + void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g);
1.572 +
1.573 + template <typename Edge, typename Children>
1.574 + void children_remove_edge(Edge e_global, Children& c)
1.575 + {
1.576 + for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
1.577 + if ((*i)->find_vertex(source(e_global, **i)).second
1.578 + && (*i)->find_vertex(target(e_global, **i)).second)
1.579 + remove_edge_recur_down(source(e_global, **i),
1.580 + target(e_global, **i), **i);
1.581 + }
1.582 +
1.583 + template <typename Edge, typename Graph>
1.584 + void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g)
1.585 + {
1.586 + remove_edge(g.global_to_local(e_global), g.m_graph);
1.587 + children_remove_edge(e_global, g.m_children);
1.588 + }
1.589 +
1.590 + template <typename Edge, typename Graph>
1.591 + void remove_edge_recur_up(Edge e_global, subgraph<Graph>& g)
1.592 + {
1.593 + if (g.is_root()) {
1.594 + remove_edge(e_global, g.m_graph);
1.595 + children_remove_edge(e_global, g.m_children);
1.596 + } else
1.597 + remove_edge_recur_up(e_global, *g.m_parent);
1.598 + }
1.599 +
1.600 + } // namespace detail
1.601 +
1.602 + template <typename G>
1.603 + void
1.604 + remove_edge(typename subgraph<G>::vertex_descriptor u_local,
1.605 + typename subgraph<G>::vertex_descriptor v_local,
1.606 + subgraph<G>& g)
1.607 + {
1.608 + if (g.is_root())
1.609 + detail::remove_edge_recur_up(u_local, v_local, g);
1.610 + else
1.611 + detail::remove_edge_recur_up(g.local_to_global(u_local),
1.612 + g.local_to_global(v_local), g);
1.613 + }
1.614 +
1.615 + template <typename G>
1.616 + void
1.617 + remove_edge(typename subgraph<G>::edge_descriptor e_local,
1.618 + subgraph<G>& g)
1.619 + {
1.620 + if (g.is_root())
1.621 + detail::remove_edge_recur_up(e_local, g);
1.622 + else
1.623 + detail::remove_edge_recur_up(g.local_to_global(e_local), g);
1.624 + }
1.625 +
1.626 + template <typename Predicate, typename G>
1.627 + void
1.628 + remove_edge_if(Predicate p, subgraph<G>& g)
1.629 + {
1.630 + // This is wrong...
1.631 + remove_edge_if(p, g.m_graph);
1.632 + }
1.633 +
1.634 + template <typename G>
1.635 + void
1.636 + clear_vertex(typename subgraph<G>::vertex_descriptor v_local,
1.637 + subgraph<G>& g)
1.638 + {
1.639 + // this is wrong...
1.640 + clear_vertex(v_local, g.m_graph);
1.641 + }
1.642 +
1.643 + namespace detail {
1.644 +
1.645 + template <typename G>
1.646 + typename subgraph<G>::vertex_descriptor
1.647 + add_vertex_recur_up(subgraph<G>& g)
1.648 + {
1.649 + typename subgraph<G>::vertex_descriptor u_local, u_global;
1.650 + if (g.is_root()) {
1.651 + u_global = add_vertex(g.m_graph);
1.652 + g.m_global_vertex.push_back(u_global);
1.653 + } else {
1.654 + u_global = add_vertex_recur_up(*g.m_parent);
1.655 + u_local = add_vertex(g.m_graph);
1.656 + g.m_global_vertex.push_back(u_global);
1.657 + g.m_local_vertex[u_global] = u_local;
1.658 + }
1.659 + return u_global;
1.660 + }
1.661 +
1.662 + } // namespace detail
1.663 +
1.664 + template <typename G>
1.665 + typename subgraph<G>::vertex_descriptor
1.666 + add_vertex(subgraph<G>& g)
1.667 + {
1.668 + typename subgraph<G>::vertex_descriptor u_local, u_global;
1.669 + if (g.is_root()) {
1.670 + u_global = add_vertex(g.m_graph);
1.671 + g.m_global_vertex.push_back(u_global);
1.672 + u_local = u_global;
1.673 + } else {
1.674 + u_global = detail::add_vertex_recur_up(g.parent());
1.675 + u_local = add_vertex(g.m_graph);
1.676 + g.m_global_vertex.push_back(u_global);
1.677 + g.m_local_vertex[u_global] = u_local;
1.678 + }
1.679 + return u_local;
1.680 + }
1.681 +
1.682 + template <typename G>
1.683 + void remove_vertex(typename subgraph<G>::vertex_descriptor u,
1.684 + subgraph<G>& g)
1.685 + {
1.686 + // UNDER CONSTRUCTION
1.687 + assert(false);
1.688 + }
1.689 +
1.690 +
1.691 + //===========================================================================
1.692 + // Functions required by the PropertyGraph concept
1.693 +
1.694 + template <typename GraphPtr, typename PropertyMap, typename Tag>
1.695 + class subgraph_global_property_map
1.696 + : public put_get_helper<
1.697 + typename property_traits<PropertyMap>::reference,
1.698 + subgraph_global_property_map<GraphPtr, PropertyMap, Tag> >
1.699 + {
1.700 + typedef property_traits<PropertyMap> Traits;
1.701 + public:
1.702 + typedef typename Traits::category category;
1.703 + typedef typename Traits::value_type value_type;
1.704 + typedef typename Traits::key_type key_type;
1.705 + typedef typename Traits::reference reference;
1.706 +
1.707 + subgraph_global_property_map() { }
1.708 +
1.709 + subgraph_global_property_map(GraphPtr g)
1.710 + : m_g(g) { }
1.711 +
1.712 + inline reference operator[](key_type e_local) const {
1.713 + PropertyMap pmap = get(Tag(), m_g->root().m_graph);
1.714 + if (m_g->m_parent == 0)
1.715 + return pmap[e_local];
1.716 + else
1.717 + return pmap[m_g->local_to_global(e_local)];
1.718 + }
1.719 + GraphPtr m_g;
1.720 + };
1.721 +
1.722 + template <typename GraphPtr, typename PropertyMap, typename Tag>
1.723 + class subgraph_local_property_map
1.724 + : public put_get_helper<
1.725 + typename property_traits<PropertyMap>::reference,
1.726 + subgraph_local_property_map<GraphPtr, PropertyMap, Tag> >
1.727 + {
1.728 + typedef property_traits<PropertyMap> Traits;
1.729 + public:
1.730 + typedef typename Traits::category category;
1.731 + typedef typename Traits::value_type value_type;
1.732 + typedef typename Traits::key_type key_type;
1.733 + typedef typename Traits::reference reference;
1.734 +
1.735 + subgraph_local_property_map() { }
1.736 +
1.737 + subgraph_local_property_map(GraphPtr g)
1.738 + : m_g(g) { }
1.739 +
1.740 + inline reference operator[](key_type e_local) const {
1.741 + PropertyMap pmap = get(Tag(), *m_g);
1.742 + return pmap[e_local];
1.743 + }
1.744 + GraphPtr m_g;
1.745 + };
1.746 +
1.747 + namespace detail {
1.748 +
1.749 + struct subgraph_any_pmap {
1.750 + template <class Tag, class SubGraph, class Property>
1.751 + class bind_ {
1.752 + typedef typename SubGraph::graph_type Graph;
1.753 + typedef SubGraph* SubGraphPtr;
1.754 + typedef const SubGraph* const_SubGraphPtr;
1.755 + typedef typename property_map<Graph, Tag>::type PMap;
1.756 + typedef typename property_map<Graph, Tag>::const_type const_PMap;
1.757 + public:
1.758 + typedef subgraph_global_property_map<SubGraphPtr, PMap, Tag> type;
1.759 + typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, Tag>
1.760 + const_type;
1.761 + };
1.762 + };
1.763 + struct subgraph_id_pmap {
1.764 + template <class Tag, class SubGraph, class Property>
1.765 + struct bind_ {
1.766 + typedef typename SubGraph::graph_type Graph;
1.767 + typedef SubGraph* SubGraphPtr;
1.768 + typedef const SubGraph* const_SubGraphPtr;
1.769 + typedef typename property_map<Graph, Tag>::type PMap;
1.770 + typedef typename property_map<Graph, Tag>::const_type const_PMap;
1.771 + public:
1.772 + typedef subgraph_local_property_map<SubGraphPtr, PMap, Tag> type;
1.773 + typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, Tag>
1.774 + const_type;
1.775 + };
1.776 + };
1.777 + template <class Tag>
1.778 + struct subgraph_choose_pmap_helper {
1.779 + typedef subgraph_any_pmap type;
1.780 + };
1.781 + template <>
1.782 + struct subgraph_choose_pmap_helper<vertex_index_t> {
1.783 + typedef subgraph_id_pmap type;
1.784 + };
1.785 + template <class Tag, class Graph, class Property>
1.786 + struct subgraph_choose_pmap {
1.787 + typedef typename subgraph_choose_pmap_helper<Tag>::type Helper;
1.788 + typedef typename Helper::template bind_<Tag, Graph, Property> Bind;
1.789 + typedef typename Bind::type type;
1.790 + typedef typename Bind::const_type const_type;
1.791 + };
1.792 + struct subgraph_property_generator {
1.793 + template <class SubGraph, class Property, class Tag>
1.794 + struct bind_ {
1.795 + typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice;
1.796 + typedef typename Choice::type type;
1.797 + typedef typename Choice::const_type const_type;
1.798 + };
1.799 + };
1.800 +
1.801 + } // namespace detail
1.802 +
1.803 + template <>
1.804 + struct vertex_property_selector<subgraph_tag> {
1.805 + typedef detail::subgraph_property_generator type;
1.806 + };
1.807 +
1.808 + template <>
1.809 + struct edge_property_selector<subgraph_tag> {
1.810 + typedef detail::subgraph_property_generator type;
1.811 + };
1.812 +
1.813 + template <typename G, typename Property>
1.814 + typename property_map< subgraph<G>, Property>::type
1.815 + get(Property, subgraph<G>& g)
1.816 + {
1.817 + typedef typename property_map< subgraph<G>, Property>::type PMap;
1.818 + return PMap(&g);
1.819 + }
1.820 +
1.821 + template <typename G, typename Property>
1.822 + typename property_map< subgraph<G>, Property>::const_type
1.823 + get(Property, const subgraph<G>& g)
1.824 + {
1.825 + typedef typename property_map< subgraph<G>, Property>::const_type PMap;
1.826 + return PMap(&g);
1.827 + }
1.828 +
1.829 + template <typename G, typename Property, typename Key>
1.830 + typename property_traits<
1.831 + typename property_map< subgraph<G>, Property>::const_type
1.832 + >::value_type
1.833 + get(Property, const subgraph<G>& g, const Key& k)
1.834 + {
1.835 + typedef typename property_map< subgraph<G>, Property>::const_type PMap;
1.836 + PMap pmap(&g);
1.837 + return pmap[k];
1.838 + }
1.839 +
1.840 + template <typename G, typename Property, typename Key, typename Value>
1.841 + void
1.842 + put(Property, subgraph<G>& g, const Key& k, const Value& val)
1.843 + {
1.844 + typedef typename property_map< subgraph<G>, Property>::type PMap;
1.845 + PMap pmap(&g);
1.846 + pmap[k] = val;
1.847 + }
1.848 +
1.849 + template <typename G, typename Tag>
1.850 + inline
1.851 + typename graph_property<G, Tag>::type&
1.852 + get_property(subgraph<G>& g, Tag tag) {
1.853 + return get_property(g.m_graph, tag);
1.854 + }
1.855 +
1.856 + template <typename G, typename Tag>
1.857 + inline
1.858 + const typename graph_property<G, Tag>::type&
1.859 + get_property(const subgraph<G>& g, Tag tag) {
1.860 + return get_property(g.m_graph, tag);
1.861 + }
1.862 +
1.863 + //===========================================================================
1.864 + // Miscellaneous Functions
1.865 +
1.866 + template <typename G>
1.867 + typename subgraph<G>::vertex_descriptor
1.868 + vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g)
1.869 + {
1.870 + return vertex(n, g.m_graph);
1.871 + }
1.872 +
1.873 +} // namespace boost
1.874 +
1.875 +#endif // BOOST_SUBGRAPH_HPP