diff options
Diffstat (limited to 'boost/graph/subgraph.hpp')
-rw-r--r-- | boost/graph/subgraph.hpp | 291 |
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) { |