graph/distributed/local_subgraph.hpp

0001 // Copyright (C) 2004-2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_LOCAL_SUBGRAPH_HPP
0010 #define BOOST_GRAPH_LOCAL_SUBGRAPH_HPP
0011
0012 #ifndef BOOST_GRAPH_USE_MPI
0013 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0014 #endif
0015
0016 #include <boost/graph/graph_traits.hpp>
0017 #include <boost/graph/filtered_graph.hpp>
0018 #include <boost/type_traits/is_same.hpp>
0019 #include <boost/type_traits/is_base_and_derived.hpp>
0020 #include <boost/graph/parallel/container_traits.hpp>
0021
0022 namespace boost {
0023
0024 namespace graph { namespace detail {
0025   // Optionally, virtually derive from a base class
0026   template<bool Derive, typename Base> struct derive_from_if;
0027   template<typename Base> struct derive_from_if<true, Base> : virtual Base {};
0028   template<typename Base> struct derive_from_if<false, Base> {};
0029
0030   template<typename NewBase, typename Tag, typename OldBase = NewBase>
0031   struct derive_from_if_tag_is :
0032     derive_from_if<(is_base_and_derived<OldBase, Tag>::value
0033                     || is_same<OldBase, Tag>::value),
0034                    NewBase>
0035   {
0036   };
0037 } } // end namespace graph::detail
0038
0039 template<typename DistributedGraph>
0040 class is_local_edge
0041 {
0042 public:
0043   typedef bool result_type;
0044   typedef typename graph_traits<DistributedGraph>::edge_descriptor
0045     argument_type;
0046
0047   is_local_edge() : g(0) {}
0048   is_local_edge(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) {}
0049
0050   // Since either the source or target vertex must be local, the
0051   // equivalence of their owners indicates a local edge.
0052   result_type operator()(const argument_type& e) const
0053   { return get(owner, source(e, *g)) == get(owner, target(e, *g)); }
0054
0055 private:
0056   DistributedGraph* g;
0057   typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
0058 };
0059
0060 template<typename DistributedGraph>
0061 class is_local_vertex
0062 {
0063 public:
0064   typedef bool result_type;
0065   typedef typename graph_traits<DistributedGraph>::vertex_descriptor
0066     argument_type;
0067
0068   is_local_vertex() : g(0) {}
0069   is_local_vertex(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) { }
0070
0071   // Since either the source or target vertex must be local, the
0072   // equivalence of their owners indicates a local edge.
0073   result_type operator()(const argument_type& v) const
0074   {
0075     return get(owner, v) == process_id(process_group(*g));
0076   }
0077
0078 private:
0079   DistributedGraph* g;
0080   typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
0081 };
0082
0083 template<typename DistributedGraph>
0084 class local_subgraph
0085   : public filtered_graph<DistributedGraph,
0086                           is_local_edge<DistributedGraph>,
0087                           is_local_vertex<DistributedGraph> >
0088 {
0089   typedef filtered_graph<DistributedGraph,
0090                          is_local_edge<DistributedGraph>,
0091                          is_local_vertex<DistributedGraph> >
0092     inherited;
0093   typedef typename graph_traits<DistributedGraph>::traversal_category
0094     inherited_category;
0095
0096 public:
0097   struct traversal_category :
0098     graph::detail::derive_from_if_tag_is<incidence_graph_tag,
0099                                          inherited_category>,
0100     graph::detail::derive_from_if_tag_is<adjacency_graph_tag,
0101                                          inherited_category>,
0102     graph::detail::derive_from_if_tag_is<vertex_list_graph_tag,
0103                                          inherited_category>,
0104     graph::detail::derive_from_if_tag_is<edge_list_graph_tag,
0105                                          inherited_category>,
0106     graph::detail::derive_from_if_tag_is<vertex_list_graph_tag,
0107                                          inherited_category,
0108                                          distributed_vertex_list_graph_tag>,
0109     graph::detail::derive_from_if_tag_is<edge_list_graph_tag,
0110                                          inherited_category,
0111                                          distributed_edge_list_graph_tag>
0112   { };
0113
0114   local_subgraph(DistributedGraph& g)
0115     : inherited(g,
0116                 is_local_edge<DistributedGraph>(g),
0117                 is_local_vertex<DistributedGraph>(g)),
0118       g(g)
0119   {
0120   }
0121
0122   // Distributed Container
0123   typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
0124     process_group_type;
0125
0126   process_group_type&       process_group()
0127   {
0128     using boost::graph::parallel::process_group;
0129     return process_group(g);
0130   }
0131   const process_group_type& process_group() const
0132   {
0133     using boost::graph::parallel::process_group;
0134     return boost::graph::parallel::process_group(g);
0135   }
0136
0137   DistributedGraph&         base()               { return g; }
0138   const DistributedGraph&   base() const         { return g; }
0139
0140 private:
0141   DistributedGraph& g;
0142 };
0143
0144 template<typename DistributedGraph, typename PropertyTag>
0145 class property_map<local_subgraph<DistributedGraph>, PropertyTag>
0146   : public property_map<DistributedGraph, PropertyTag> { };
0147
0148 template<typename DistributedGraph, typename PropertyTag>
0149 class property_map<local_subgraph<const DistributedGraph>, PropertyTag>
0150 {
0151  public:
0152   typedef typename property_map<DistributedGraph, PropertyTag>::const_type
0153     type;
0154   typedef type const_type;
0155 };
0156
0157 template<typename PropertyTag, typename DistributedGraph>
0158 inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>::type
0159 get(PropertyTag p, local_subgraph<DistributedGraph>& g)
0160 { return get(p, g.base()); }
0161
0162 template<typename PropertyTag, typename DistributedGraph>
0163 inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>
0164   ::const_type
0165 get(PropertyTag p, const local_subgraph<DistributedGraph>& g)
0166 { return get(p, g.base()); }
0167
0168 template<typename DistributedGraph>
0169 inline local_subgraph<DistributedGraph>
0170 make_local_subgraph(DistributedGraph& g)
0171 { return local_subgraph<DistributedGraph>(g); }
0172
0173 } // end namespace boost
0174
0175 #endif // BOOST_GRAPH_LOCAL_SUBGRAPH_HPP