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