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