// Copyright (C) 2004-2006 The Trustees of Indiana University. // Use, modification and distribution is subject to 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) // Authors: Douglas Gregor // Andrew Lumsdaine #ifndef BOOST_GRAPH_LOCAL_SUBGRAPH_HPP #define BOOST_GRAPH_LOCAL_SUBGRAPH_HPP #ifndef BOOST_GRAPH_USE_MPI #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" #endif #include <boost/graph/graph_traits.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/type_traits/is_base_and_derived.hpp> #include <boost/graph/parallel/container_traits.hpp> namespace boost { namespace graph { namespace detail { // Optionally, virtually derive from a base class template<bool Derive, typename Base> struct derive_from_if; template<typename Base> struct derive_from_if<true, Base> : virtual Base {}; template<typename Base> struct derive_from_if<false, Base> {}; template<typename NewBase, typename Tag, typename OldBase = NewBase> struct derive_from_if_tag_is : derive_from_if<(is_base_and_derived<OldBase, Tag>::value || is_same<OldBase, Tag>::value), NewBase> { }; } } // end namespace graph::detail template<typename DistributedGraph> class is_local_edge { public: typedef bool result_type; typedef typename graph_traits<DistributedGraph>::edge_descriptor argument_type; is_local_edge() : g(0) {} is_local_edge(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) {} // Since either the source or target vertex must be local, the // equivalence of their owners indicates a local edge. result_type operator()(const argument_type& e) const { return get(owner, source(e, *g)) == get(owner, target(e, *g)); } private: DistributedGraph* g; typename property_map<DistributedGraph, vertex_owner_t>::const_type owner; }; template<typename DistributedGraph> class is_local_vertex { public: typedef bool result_type; typedef typename graph_traits<DistributedGraph>::vertex_descriptor argument_type; is_local_vertex() : g(0) {} is_local_vertex(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) { } // Since either the source or target vertex must be local, the // equivalence of their owners indicates a local edge. result_type operator()(const argument_type& v) const { return get(owner, v) == process_id(process_group(*g)); } private: DistributedGraph* g; typename property_map<DistributedGraph, vertex_owner_t>::const_type owner; }; template<typename DistributedGraph> class local_subgraph : public filtered_graph<DistributedGraph, is_local_edge<DistributedGraph>, is_local_vertex<DistributedGraph> > { typedef filtered_graph<DistributedGraph, is_local_edge<DistributedGraph>, is_local_vertex<DistributedGraph> > inherited; typedef typename graph_traits<DistributedGraph>::traversal_category inherited_category; public: struct traversal_category : graph::detail::derive_from_if_tag_is<incidence_graph_tag, inherited_category>, graph::detail::derive_from_if_tag_is<adjacency_graph_tag, inherited_category>, graph::detail::derive_from_if_tag_is<vertex_list_graph_tag, inherited_category>, graph::detail::derive_from_if_tag_is<edge_list_graph_tag, inherited_category>, graph::detail::derive_from_if_tag_is<vertex_list_graph_tag, inherited_category, distributed_vertex_list_graph_tag>, graph::detail::derive_from_if_tag_is<edge_list_graph_tag, inherited_category, distributed_edge_list_graph_tag> { }; local_subgraph(DistributedGraph& g) : inherited(g, is_local_edge<DistributedGraph>(g), is_local_vertex<DistributedGraph>(g)), g(g) { } // Distributed Container typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type process_group_type; process_group_type& process_group() { using boost::graph::parallel::process_group; return process_group(g); } const process_group_type& process_group() const { using boost::graph::parallel::process_group; return boost::graph::parallel::process_group(g); } DistributedGraph& base() { return g; } const DistributedGraph& base() const { return g; } private: DistributedGraph& g; }; template<typename DistributedGraph, typename PropertyTag> class property_map<local_subgraph<DistributedGraph>, PropertyTag> : public property_map<DistributedGraph, PropertyTag> { }; template<typename DistributedGraph, typename PropertyTag> class property_map<local_subgraph<const DistributedGraph>, PropertyTag> { public: typedef typename property_map<DistributedGraph, PropertyTag>::const_type type; typedef type const_type; }; template<typename PropertyTag, typename DistributedGraph> inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>::type get(PropertyTag p, local_subgraph<DistributedGraph>& g) { return get(p, g.base()); } template<typename PropertyTag, typename DistributedGraph> inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag> ::const_type get(PropertyTag p, const local_subgraph<DistributedGraph>& g) { return get(p, g.base()); } template<typename DistributedGraph> inline local_subgraph<DistributedGraph> make_local_subgraph(DistributedGraph& g) { return local_subgraph<DistributedGraph>(g); } } // end namespace boost #endif // BOOST_GRAPH_LOCAL_SUBGRAPH_HPP