| // 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 |