summaryrefslogtreecommitdiff
path: root/boost/graph/subgraph.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/graph/subgraph.hpp')
-rw-r--r--boost/graph/subgraph.hpp291
1 files changed, 61 insertions, 230 deletions
diff --git a/boost/graph/subgraph.hpp b/boost/graph/subgraph.hpp
index b98c390267..22706bc617 100644
--- a/boost/graph/subgraph.hpp
+++ b/boost/graph/subgraph.hpp
@@ -24,7 +24,9 @@
#include <boost/static_assert.hpp>
#include <boost/assert.hpp>
-#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/or.hpp>
namespace boost {
@@ -103,13 +105,11 @@ public:
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 typename edge_property_type<Graph>::type edge_property_type;
+ typedef typename vertex_property_type<Graph>::type vertex_property_type;
typedef subgraph_tag graph_tag;
typedef Graph graph_type;
- typedef typename Graph::graph_property_type graph_property_type;
+ typedef typename graph_property_type<Graph>::type graph_property_type;
// Create the main graph, the root of the subgraph tree
subgraph()
@@ -131,15 +131,29 @@ public:
// copy constructor
subgraph(const subgraph& x)
- : m_graph(x.m_graph), m_parent(x.m_parent), m_edge_counter(x.m_edge_counter)
+ : 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)
+ if(x.is_root())
{
- m_children.push_back(new subgraph<Graph>( **i ));
+ m_graph = x.m_graph;
}
+ // Do a deep copy (recursive).
+ // Only the root graph is copied, the subgraphs contain
+ // only references to the global vertices they own.
+ typename subgraph<Graph>::children_iterator i,i_end;
+ boost::tie(i,i_end) = x.children();
+ for(; i != i_end; ++i)
+ {
+ subgraph<Graph> child = this->create_subgraph();
+ child = *i;
+ vertex_iterator vi,vi_end;
+ boost::tie(vi,vi_end) = vertices(*i);
+ for (;vi!=vi_end;++vi)
+ {
+ add_vertex(*vi,child);
+ }
+ }
}
@@ -334,9 +348,6 @@ public: // Probably shouldn't be public....
}
};
-#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>
@@ -346,7 +357,11 @@ template<typename Graph>
struct edge_bundle_type<subgraph<Graph> >
: edge_bundle_type<Graph>
{ };
-#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+
+template<typename Graph>
+struct graph_bundle_type<subgraph<Graph> >
+ : graph_bundle_type<Graph>
+{ };
//===========================================================================
// Functions special to the Subgraph Class
@@ -764,7 +779,10 @@ class subgraph_global_property_map
{
typedef property_traits<PropertyMap> Traits;
public:
- typedef typename Traits::category category;
+ typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
+ readable_property_map_tag,
+ typename Traits::category>::type
+ category;
typedef typename Traits::value_type value_type;
typedef typename Traits::key_type key_type;
typedef typename Traits::reference reference;
@@ -772,18 +790,19 @@ public:
subgraph_global_property_map()
{ }
- subgraph_global_property_map(GraphPtr g)
- : m_g(g)
+ subgraph_global_property_map(GraphPtr g, Tag tag)
+ : m_g(g), m_tag(tag)
{ }
reference operator[](key_type e) const {
- PropertyMap pmap = get(Tag(), m_g->root().m_graph);
+ PropertyMap pmap = get(m_tag, m_g->root().m_graph);
return m_g->is_root()
? pmap[e]
: pmap[m_g->local_to_global(e)];
}
GraphPtr m_g;
+ Tag m_tag;
};
/**
@@ -799,7 +818,10 @@ class subgraph_local_property_map
{
typedef property_traits<PropertyMap> Traits;
public:
- typedef typename Traits::category category;
+ typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>,
+ readable_property_map_tag,
+ typename Traits::category>::type
+ category;
typedef typename Traits::value_type value_type;
typedef typename Traits::key_type key_type;
typedef typename Traits::reference reference;
@@ -810,17 +832,18 @@ public:
subgraph_local_property_map()
{ }
- subgraph_local_property_map(GraphPtr g)
- : m_g(g)
+ subgraph_local_property_map(GraphPtr g, Tag tag)
+ : m_g(g), m_tag(tag)
{ }
reference operator[](key_type e) const {
// Get property map on the underlying graph.
- PropertyMap pmap = get(Tag(), m_g->m_graph);
+ PropertyMap pmap = get(m_tag, m_g->m_graph);
return pmap[e];
}
GraphPtr m_g;
+ Tag m_tag;
};
namespace detail {
@@ -935,139 +958,37 @@ 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) {
+get(Property p, subgraph<G>& g) {
typedef typename property_map< subgraph<G>, Property>::type PMap;
- return PMap(&g);
+ return PMap(&g, p);
}
template <typename G, typename Property>
typename property_map<subgraph<G>, Property>::const_type
-get(Property, const subgraph<G>& g) {
+get(Property p, const subgraph<G>& g) {
typedef typename property_map< subgraph<G>, Property>::const_type PMap;
- return PMap(&g);
+ return PMap(&g, p);
}
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) {
+get(Property p, const subgraph<G>& g, const Key& k) {
typedef typename property_map< subgraph<G>, Property>::const_type PMap;
- PMap pmap(&g);
+ PMap pmap(&g, p);
return pmap[k];
}
template <typename G, typename Property, typename Key, typename Value>
-void put(Property, subgraph<G>& g, const Key& k, const Value& val) {
+void put(Property p, subgraph<G>& g, const Key& k, const Value& val) {
typedef typename property_map< subgraph<G>, Property>::type PMap;
- PMap pmap(&g);
+ PMap pmap(&g, p);
pmap[k] = val;
}
@@ -1077,20 +998,20 @@ void put(Property, subgraph<G>& g, const Key& k, const Value& val) {
// ==================================================
template <typename G, typename Property>
typename property_map<subgraph<G>, global_property<Property> >::type
-get(global_property<Property>, subgraph<G>& g) {
+get(global_property<Property> p, subgraph<G>& g) {
typedef typename property_map<
subgraph<G>, global_property<Property>
>::type Map;
- return Map(&g);
+ return Map(&g, p.value);
}
template <typename G, typename Property>
typename property_map<subgraph<G>, global_property<Property> >::const_type
-get(global_property<Property>, const subgraph<G>& g) {
+get(global_property<Property> p, const subgraph<G>& g) {
typedef typename property_map<
subgraph<G>, global_property<Property>
>::const_type Map;
- return Map(&g);
+ return Map(&g, p.value);
}
// ==================================================
@@ -1099,112 +1020,22 @@ get(global_property<Property>, const subgraph<G>& g) {
// ==================================================
template <typename G, typename Property>
typename property_map<subgraph<G>, local_property<Property> >::type
-get(local_property<Property>, subgraph<G>& g) {
+get(local_property<Property> p, subgraph<G>& g) {
typedef typename property_map<
subgraph<G>, local_property<Property>
>::type Map;
- return Map(&g);
+ return Map(&g, p.value);
}
template <typename G, typename Property>
typename property_map<subgraph<G>, local_property<Property> >::const_type
-get(local_property<Property>, const subgraph<G>& g) {
+get(local_property<Property> p, 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) {