Subject: [Boost-commit] svn:boost r53289 - in trunk: boost/graph libs/graph/test
From: asutton_at_[hidden]
Date: 2009-05-26 18:22:56
Author: asutton
Date: 2009-05-26 18:22:55 EDT (Tue, 26 May 2009)
New Revision: 53289
URL: http://svn.boost.org/trac/boost/changeset/53289
Log:
Augmenting property lookup strategies for subgraphs.
Text files modified:
trunk/boost/graph/properties.hpp | 1
trunk/boost/graph/subgraph.hpp | 1316 ++++++++++++++++++++++-----------------
trunk/libs/graph/test/Jamfile.v2 | 4
3 files changed, 732 insertions(+), 589 deletions(-)
Modified: trunk/boost/graph/properties.hpp
==============================================================================
--- trunk/boost/graph/properties.hpp (original)
+++ trunk/boost/graph/properties.hpp 2009-05-26 18:22:55 EDT (Tue, 26 May 2009)
@@ -385,6 +385,7 @@
{ };
}
+ // Specialize the property map template to generate bundled property maps.
template <typename Graph, typename T, typename Bundle>
struct property_map<Graph, T Bundle::*>
{
Modified: trunk/boost/graph/subgraph.hpp
==============================================================================
--- trunk/boost/graph/subgraph.hpp (original)
+++ trunk/boost/graph/subgraph.hpp 2009-05-26 18:22:55 EDT (Tue, 26 May 2009)
@@ -27,40 +27,57 @@
namespace boost {
- struct subgraph_tag { };
+struct subgraph_tag { };
- // 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.
- //
- // NOTE: The requirement of internal indexing causes this to fail for many,
- // many graphs (i.e., those of non-vecS storage, and using bundled
- // properties).
- template <typename Graph>
- class subgraph {
+/** @name Property Lookup
+ * The local_property and global_property functions are used to create
+ * structures that determine the lookup strategy for properties in subgraphs.
+ */
+//@{
+template <typename T>
+struct local_subgraph_property {
+ local_subgraph_property(T x) : value(x) { }
+ T value;
+};
+
+template <typename T>
+inline local_subgraph_property<T> local(T x)
+{ return local_subgraph_property<T>(x); }
+
+template <typename T>
+struct global_subgraph_property {
+ global_subgraph_property(T x) : value(x) { }
+ T value;
+};
+
+template <typename T>
+inline global_subgraph_property<T> global(T x)
+{ return global_subgraph_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;
-
- static vertex_descriptor null_vertex()
- {
- return Traits::null_vertex();
- }
-
+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;
@@ -87,117 +104,109 @@
typedef Graph graph_type;
typedef typename Graph::graph_property_type graph_property_type;
- // Constructors
-
// Create the main graph, the root of the subgraph tree
subgraph()
- : m_parent(0), m_edge_counter(0)
+ : m_parent(0), m_edge_counter(0)
{ }
+
subgraph(const graph_property_type& p)
- : m_graph(p), m_parent(0), m_edge_counter(0)
+ : 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 (tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
- m_global_vertex[i++] = *v;
+
+ 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(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
- for (typename ChildrenList::const_iterator i = x.m_children.begin();
- i != x.m_children.end(); ++i)
- m_children.push_back(new subgraph<Graph>( **i ));
+ : 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;
+ 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();
+ 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();
+ 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 m_global_vertex[u_local];
- }
- vertex_descriptor global_to_local(vertex_descriptor u_global) const
- {
- vertex_descriptor u_local; bool in_subgraph;
- tie(u_local, in_subgraph) = this->find_vertex(u_global);
- assert(in_subgraph == true);
- return u_local;
+ { return m_global_vertex[u_local]; }
+
+ vertex_descriptor global_to_local(vertex_descriptor u_global) const {
+ vertex_descriptor u_local; bool in_subgraph;
+ tie(u_local, in_subgraph) = this->find_vertex(u_global);
+ assert(in_subgraph == true);
+ return u_local;
}
+
edge_descriptor local_to_global(edge_descriptor e_local) const
- {
- return m_global_edge[get(get(edge_index, m_graph), e_local)];
- }
+ { return m_global_edge[get(get(edge_index, m_graph), e_local)]; }
+
edge_descriptor global_to_local(edge_descriptor e_global) const
- {
- return
- (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second;
- }
+ { return (*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
- {
- typename std::map<vertex_descriptor, vertex_descriptor>::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);
+ find_vertex(vertex_descriptor u_global) const {
+ typename std::map<vertex_descriptor, vertex_descriptor>::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);
}
// 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() {
- if (this->is_root())
- return *this;
- else
- return m_parent->root();
- }
- const subgraph& root() const {
- if (this->is_root())
- return *this;
- else
- return m_parent->root();
- }
+ 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
@@ -216,16 +225,12 @@
>
const_children_iterator;
- std::pair<const_children_iterator, const_children_iterator>
- children() const
- {
+ 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()
- {
+ std::pair<children_iterator, children_iterator> children() {
return std::make_pair(children_iterator(m_children.begin()),
children_iterator(m_children.end()));
}
@@ -233,22 +238,41 @@
std::size_t num_children() const { return m_children.size(); }
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
- // Bundled properties support
- template<typename Descriptor>
+ // Defualt property access delegates the lookup to global properties.
+ template <typename Descriptor>
typename graph::detail::bundled_result<Graph, Descriptor>::type&
operator[](Descriptor x)
- {
- if (m_parent == 0) return m_graph[x];
- else return root().m_graph[local_to_global(x)];
- }
+ { return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)]; }
- template<typename Descriptor>
+ template <typename Descriptor>
typename graph::detail::bundled_result<Graph, Descriptor>::type const&
operator[](Descriptor x) const
- {
- if (m_parent == 0) return m_graph[x];
- else return root().m_graph[local_to_global(x)];
- }
+ { 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_subgraph_property<Descriptor> x)
+ { return m_graph[x.value]; }
+
+ template <typename Descriptor>
+ typename graph::detail::bundled_result<Graph, Descriptor>::type const&
+ operator[](local_subgraph_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_subgraph_property<Descriptor> x)
+ { return (*this)[x.value]; }
+
+ template <typename Descriptor>
+ typename graph::detail::bundled_result<Graph, Descriptor>::type const&
+ operator[](global_subgraph_property<Descriptor> x) const
+ { return (*this)[x.value]; }
+
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
// private:
@@ -257,46 +281,62 @@
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;
- std::vector<vertex_descriptor> m_global_vertex; // local -> global
- std::map<vertex_descriptor, vertex_descriptor> m_local_vertex; // global -> local
- std::vector<edge_descriptor> m_global_edge; // local -> global
- std::map<edge_index_type, edge_descriptor> 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;
- 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;
+ 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;
+ 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
- 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> { };
+// 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
+//===========================================================================
+// 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)
- {
+template <typename G>
+typename subgraph<G>::vertex_descriptor
+add_vertex(typename subgraph<G>::vertex_descriptor u_global,
+ subgraph<G>& g)
+{
assert(!g.is_root());
typename subgraph<G>::vertex_descriptor u_local, v_global, uu_global;
typename subgraph<G>::edge_descriptor e_global;
@@ -309,167 +349,163 @@
// remember edge global and local maps
{
- typename subgraph<G>::out_edge_iterator ei, ei_end;
- for (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);
- }
+ typename subgraph<G>::out_edge_iterator ei, ei_end;
+ for (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 (tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
- v_global = *vi;
- if (g.find_vertex(v_global).second)
- for (tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
- e_global = *ei;
- uu_global = target(e_global, r);
- if (uu_global == u_global && g.find_vertex(v_global).second)
- g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
- }
- }
+ typename subgraph<G>::vertex_iterator vi, vi_end;
+ typename subgraph<G>::out_edge_iterator ei, ei_end;
+ for(tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
+ v_global = *vi;
+ if(g.find_vertex(v_global).second)
+ for(tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
+ e_global = *ei;
+ uu_global = target(e_global, r);
+ if(uu_global == u_global && g.find_vertex(v_global).second) {
+ 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
+//===========================================================================
+// 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 u_local,
- const subgraph<G>& g)
- { return out_edges(u_local, g.m_graph); }
-
- template <typename G>
- typename graph_traits<G>::degree_size_type
- out_degree(typename graph_traits<G>::vertex_descriptor u_local,
- const subgraph<G>& g)
- { return out_degree(u_local, g.m_graph); }
-
- template <typename G>
- typename graph_traits<G>::vertex_descriptor
- source(typename graph_traits<G>::edge_descriptor e_local,
- const subgraph<G>& g)
- { return source(e_local, g.m_graph); }
-
- template <typename G>
- typename graph_traits<G>::vertex_descriptor
- target(typename graph_traits<G>::edge_descriptor e_local,
- const subgraph<G>& g)
- { return target(e_local, 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 u_local,
- const subgraph<G>& g)
- { return in_edges(u_local, g.m_graph); }
-
- template <typename G>
- typename graph_traits<G>::degree_size_type
- in_degree(typename graph_traits<G>::vertex_descriptor u_local,
- const subgraph<G>& g)
- { return in_degree(u_local, g.m_graph); }
-
- template <typename G>
- typename graph_traits<G>::degree_size_type
- degree(typename graph_traits<G>::vertex_descriptor u_local,
- const subgraph<G>& g)
- { return degree(u_local, 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 u_local,
- const subgraph<G>& g)
- { return adjacent_vertices(u_local, 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_local,
- typename subgraph<G>::vertex_descriptor v_local,
- const subgraph<G>& g)
- {
- return edge(u_local, v_local, g.m_graph);
- }
+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
+//===========================================================================
+// Functions required by the MutableGraph concept
- namespace detail {
+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);
+ 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);
+ 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)
+ 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;
- tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
- 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);
+ 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;
+ tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
+ 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>
@@ -478,58 +514,57 @@
const typename Graph::edge_property_type& ep,
subgraph<Graph>& g, subgraph<Graph>* orig)
{
- if (g.is_root()) {
- typename subgraph<Graph>::edge_descriptor e_global;
+ if(g.is_root()) {
+ typename subgraph<Graph>::edge_descriptor e_global;
+ bool inserted;
+ 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;
- 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
- // other subgraphs which 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_local,
- typename subgraph<G>::vertex_descriptor v_local,
- const typename G::edge_property_type& ep,
- subgraph<G>& g)
- {
- if (g.is_root()) // u_local and v_local are really global
- return detail::add_edge_recur_up(u_local, v_local, ep, g, &g);
- else {
- typename subgraph<G>::edge_descriptor e_local, e_global;
- bool inserted;
- tie(e_global, inserted) = detail::add_edge_recur_up
- (g.local_to_global(u_local), g.local_to_global(v_local), ep, g, &g);
- e_local = g.local_add_edge(u_local, v_local, 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)
- {
- typename G::edge_property_type ep;
- return add_edge(u, v, ep, g);
- }
-
- namespace detail {
+ 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);
@@ -538,378 +573,481 @@
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);
+ 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);
+ 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);
+ 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 Edge, typename Graph>
void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g);
template <typename Edge, typename Children>
void children_remove_edge(Edge e_global, Children& c)
{
- for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
- if ((*i)->find_vertex(source(e_global, **i)).second
- && (*i)->find_vertex(target(e_global, **i)).second)
- remove_edge_recur_down(source(e_global, **i),
- target(e_global, **i), **i);
+ for(typename Children::iterator i = c.begin(); i != c.end(); ++i) {
+ if((*i)->find_vertex(source(e_global, **i)).second &&
+ (*i)->find_vertex(target(e_global, **i)).second)
+ {
+ remove_edge_recur_down(source(e_global, **i),
+ target(e_global, **i),
+ **i);
+ }
+ }
}
template <typename Edge, typename Graph>
void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g)
{
- remove_edge(g.global_to_local(e_global), g.m_graph);
- children_remove_edge(e_global, g.m_children);
+ remove_edge(g.global_to_local(e_global), g.m_graph);
+ children_remove_edge(e_global, g.m_children);
}
template <typename Edge, typename Graph>
void remove_edge_recur_up(Edge e_global, subgraph<Graph>& g)
{
- if (g.is_root()) {
- remove_edge(e_global, g.m_graph);
- children_remove_edge(e_global, g.m_children);
- } else
- remove_edge_recur_up(e_global, *g.m_parent);
+ if (g.is_root()) {
+ remove_edge(e_global, g.m_graph);
+ children_remove_edge(e_global, g.m_children);
+ } else {
+ remove_edge_recur_up(e_global, *g.m_parent);
+ }
+ }
+
+} // 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);
}
+}
- } // namespace detail
-
- template <typename G>
- void
- remove_edge(typename subgraph<G>::vertex_descriptor u_local,
- typename subgraph<G>::vertex_descriptor v_local,
- subgraph<G>& g)
- {
- if (g.is_root())
- detail::remove_edge_recur_up(u_local, v_local, g);
- else
- detail::remove_edge_recur_up(g.local_to_global(u_local),
- g.local_to_global(v_local), g);
- }
-
- template <typename G>
- void
- remove_edge(typename subgraph<G>::edge_descriptor e_local,
- subgraph<G>& g)
- {
- if (g.is_root())
- detail::remove_edge_recur_up(e_local, g);
- else
- detail::remove_edge_recur_up(g.local_to_global(e_local), g);
- }
-
- template <typename Predicate, typename G>
- void
- remove_edge_if(Predicate p, subgraph<G>& g)
- {
- // This is wrong...
- remove_edge_if(p, g.m_graph);
- }
-
- template <typename G>
- void
- clear_vertex(typename subgraph<G>::vertex_descriptor v_local,
- subgraph<G>& g)
- {
- // this is wrong...
- clear_vertex(v_local, g.m_graph);
- }
+template <typename G>
+void
+remove_edge(typename subgraph<G>::edge_descriptor e, subgraph<G>& g)
+{
+ if(g.is_root()) {
+ detail::remove_edge_recur_up(e, g);
+ } else {
+ detail::remove_edge_recur_up(g.local_to_global(e), g);
+ }
+}
- namespace detail {
+// TODO: This is wrong...
+template <typename Predicate, typename G>
+void
+remove_edge_if(Predicate p, subgraph<G>& g)
+{ remove_edge_if(p, g.m_graph); }
+
+// TODO: Ths is wrong
+template <typename G>
+void
+clear_vertex(typename subgraph<G>::vertex_descriptor v, subgraph<G>& g)
+{ clear_vertex(v, g.m_graph); }
+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()) {
+ 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);
- } else {
- u_global = add_vertex_recur_up(*g.m_parent);
+ 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_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;
- }
+}
- template <typename G>
- typename subgraph<G>::vertex_descriptor
- add_vertex(typename subgraph<G>::vertex_property_type const& vp,
- subgraph<G>& g)
- {
- // UNDER CONSTRUCTION
- assert(false);
- }
-
- template <typename G>
- void remove_vertex(typename subgraph<G>::vertex_descriptor u,
- subgraph<G>& g)
- {
- // UNDER CONSTRUCTION
- assert(false);
- }
- //===========================================================================
- // Functions required by the PropertyGraph concept
-
- template <typename GraphPtr, typename PropertyMap, typename Tag>
- class subgraph_global_property_map
+// TODO: Under Construction
+template <typename G>
+void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
+{ assert(false); }
+
+//===========================================================================
+// 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> >
- {
+ subgraph_global_property_map<GraphPtr, PropertyMap, Tag>
+ >
+{
typedef property_traits<PropertyMap> Traits;
- public:
+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()
+ { }
subgraph_global_property_map(GraphPtr g)
- : m_g(g) { }
+ : m_g(g)
+ { }
- inline reference operator[](key_type e_local) const {
- PropertyMap pmap = get(Tag(), m_g->root().m_graph);
- if (m_g->m_parent == 0)
- return pmap[e_local];
- else
- return pmap[m_g->local_to_global(e_local)];
+ 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;
- };
+};
- template <typename GraphPtr, typename PropertyMap, typename Tag>
- class subgraph_local_property_map
+/**
+ * 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> >
- {
+ subgraph_local_property_map<GraphPtr, PropertyMap, Tag>
+ >
+{
typedef property_traits<PropertyMap> Traits;
- public:
+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_local_property_map() { }
+ subgraph_local_property_map()
+ { }
subgraph_local_property_map(GraphPtr g)
- : m_g(g) { }
+ : m_g(g)
+ { }
- inline reference operator[](key_type e_local) const {
- PropertyMap pmap = get(Tag(), *m_g);
- return pmap[e_local];
+ reference operator[](key_type e) const {
+ PropertyMap pmap = get(Tag(), *m_g);
+ return pmap[e];
}
- GraphPtr m_g;
- };
- namespace detail {
+ GraphPtr m_g;
+};
- struct subgraph_any_pmap {
- template <class Tag, class SubGraph, class Property>
- class bind_ {
- typedef typename SubGraph::graph_type Graph;
- typedef SubGraph* SubGraphPtr;
- typedef const SubGraph* const_SubGraphPtr;
- typedef typename property_map<Graph, Tag>::type PMap;
- typedef typename property_map<Graph, Tag>::const_type const_PMap;
- public:
- typedef subgraph_global_property_map<SubGraphPtr, PMap, Tag> type;
- typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, Tag>
- const_type;
- };
+namespace detail {
+ struct subgraph_global_pmap {
+ template <class Tag, class SubGraph, class Property>
+ class bind_ {
+ typedef typename SubGraph::graph_type Graph;
+ typedef SubGraph* SubGraphPtr;
+ typedef const SubGraph* const_SubGraphPtr;
+ typedef typename property_map<Graph, Tag>::type PMap;
+ typedef typename property_map<Graph, Tag>::const_type const_PMap;
+ public:
+ typedef subgraph_global_property_map<SubGraphPtr, PMap, Tag> type;
+ typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, Tag>
+ const_type;
+ };
};
- struct subgraph_id_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 property_map<Graph, Tag>::type PMap;
- typedef typename property_map<Graph, Tag>::const_type const_PMap;
- public:
- typedef subgraph_local_property_map<SubGraphPtr, PMap, Tag> type;
- typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, Tag>
- 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 property_map<Graph, Tag>::type PMap;
+ typedef typename property_map<Graph, Tag>::const_type const_PMap;
+ public:
+ typedef subgraph_local_property_map<SubGraphPtr, PMap, Tag> type;
+ typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, Tag>
+ 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.
template <class Tag>
struct subgraph_choose_pmap_helper {
- typedef subgraph_any_pmap type;
+ typedef subgraph_global_pmap type;
};
template <>
struct subgraph_choose_pmap_helper<vertex_index_t> {
- typedef subgraph_id_pmap type;
+ 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.
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;
+ 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;
- };
+ 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> {
+template <>
+struct vertex_property_selector<subgraph_tag> {
typedef detail::subgraph_property_generator type;
- };
+};
- template <>
- struct edge_property_selector<subgraph_tag> {
+template <>
+struct edge_property_selector<subgraph_tag> {
typedef detail::subgraph_property_generator type;
- };
+};
+
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+template<typename Graph, typename Descriptor, typename Bundle, typename T>
+struct subgraph_local_bundle_property_map
+ : put_get_helper<
+ T&,
+ subgraph_local_bundle_property_map<Graph, Descriptor, Bundle, T>
+ >
+{
+ typedef Descriptor key_type;
+ typedef typename remove_const<T>::type value_type;
+ typedef T& reference;
+ typedef lvalue_property_map_tag category;
+
+ subgraph_local_bundle_property_map()
+ { }
- template <typename G, typename Property>
- typename property_map< subgraph<G>, Property>::type
- get(Property, subgraph<G>& g)
- {
+ subgraph_local_bundle_property_map(Graph* g, T Bundle::* p)
+ : m_g(g), m_prop(p)
+ { }
+
+ reference operator[](key_type k) const
+ { return (*m_g)[local(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.
+
+template <typename Graph, typename T, typename Bundle>
+struct property_map<subgraph<Graph>, local_subgraph_property<T Bundle::*> >
+{
+private:
+ 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_c<
+ detail::is_vertex_bundle<VertBundled, EdgeBundled, Bundle>::value,
+ typename Traits::vertex_descriptor,
+ typename Traits::edge_descriptor
+ >::type Desc;
+
+ // Deduce the bundled property type
+ typedef typename mpl::if_c<
+ detail::is_vertex_bundle<VertBundled, EdgeBundled, Bundle>::value,
+ VertBundled,
+ EdgeBundled
+ >::type Prop;
+public:
+ typedef subgraph_local_bundle_property_map<SubGraph, Desc, Prop, T> type;
+ typedef subgraph_local_bundle_property_map<const SubGraph, Desc, Prop, const T> const_type;
+};
+#endif
+
+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)
- {
+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)
- {
+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];
- }
+}
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
- 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); }
+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); }
+
+// =========================================================
+// Localized bundled, get
+
+template<typename G, typename T, typename Bundle>
+inline typename property_map<
+ subgraph<G>, local_subgraph_property<T Bundle::*>
+>::type
+get(local_subgraph_property<T Bundle::*> p, subgraph<G>& g) {
+ typedef typename property_map<
+ subgraph<G>, local_subgraph_property<T Bundle::*>
+ >::type Map;
+ return Map(&g, p.value);
+}
+
+template<typename G, typename T, typename Bundle>
+inline typename property_map<
+ subgraph<G>, local_subgraph_property<T Bundle::*>
+>::const_type
+get(local_subgraph_property<T Bundle::*> p, subgraph<G> const& g) {
+ typedef typename property_map<
+ subgraph<G>, local_subgraph_property<T Bundle::*>
+ >::const_type Map;
+ return Map(&g, p.value);
+}
+
+template <typename Graph, typename Type, typename Bundle, typename Key>
+inline Type get(local_subgraph_property<Type Bundle::*> p,
+ subgraph<Graph> const& g,
+ Key const& k)
+{ return get(get(p, g), k); }
+
#endif
- template <typename G, typename Property, typename Key, typename Value>
- void put(Property, subgraph<G>& g, const Key& k, const Value& val) {
+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;
- }
+}
- template <typename G, typename Tag>
- inline typename graph_property<G, Tag>::type&
- get_property(subgraph<G>& g, Tag tag) {
+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) {
+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
+//===========================================================================
+// 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;
- };
+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
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2009-05-26 18:22:55 EDT (Tue, 26 May 2009)
@@ -70,8 +70,12 @@
[ compile reverse_graph_cc.cpp ]
[ run sequential_vertex_coloring.cpp ]
+
+ # TODO: Merge these into a single test framework.
[ run subgraph.cpp ../../test/build//boost_test_exec_monitor ]
[ run subgraph_bundled.cpp ]
+ [ run subgraph_props.cpp ]
+
[ run isomorphism.cpp ../../test/build//boost_test_exec_monitor ]
[ run adjacency_matrix_test.cpp ]
[ compile vector_graph_cc.cpp ]