ceph/src/boost/libs/graph_parallel/include/boost/graph/distributed/local_subgraph.hpp

   1 // Copyright (C) 2004-2006 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_GRAPH_LOCAL_SUBGRAPH_HPP
  10 #define BOOST_GRAPH_LOCAL_SUBGRAPH_HPP
  11
  12 #ifndef BOOST_GRAPH_USE_MPI
  13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  14 #endif
  15
  16 #include <boost/graph/graph_traits.hpp>
  17 #include <boost/graph/filtered_graph.hpp>
  18 #include <boost/type_traits/is_same.hpp>
  19 #include <boost/type_traits/is_base_and_derived.hpp>
  20 #include <boost/graph/parallel/container_traits.hpp>
  21
  22 namespace boost {
  23
  24 namespace graph { namespace detail {
  25   // Optionally, virtually derive from a base class
  26   template<bool Derive, typename Base> struct derive_from_if;
  27   template<typename Base> struct derive_from_if<true, Base> : virtual Base {};
  28   template<typename Base> struct derive_from_if<false, Base> {};
  29
  30   template<typename NewBase, typename Tag, typename OldBase = NewBase>
  31   struct derive_from_if_tag_is :
  32     derive_from_if<(is_base_and_derived<OldBase, Tag>::value
  33                     || is_same<OldBase, Tag>::value),
  34                    NewBase>
  35   {
  36   };
  37 } } // end namespace graph::detail
  38
  39 template<typename DistributedGraph>
  40 class is_local_edge
  41 {
  42 public:
  43   typedef bool result_type;
  44   typedef typename graph_traits<DistributedGraph>::edge_descriptor
  45     argument_type;
  46
  47   is_local_edge() : g(0) {}
  48   is_local_edge(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) {}
  49
  50   // Since either the source or target vertex must be local, the
  51   // equivalence of their owners indicates a local edge.
  52   result_type operator()(const argument_type& e) const
  53   { return get(owner, source(e, *g)) == get(owner, target(e, *g)); }
  54
  55 private:
  56   DistributedGraph* g;
  57   typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
  58 };
  59
  60 template<typename DistributedGraph>
  61 class is_local_vertex
  62 {
  63 public:
  64   typedef bool result_type;
  65   typedef typename graph_traits<DistributedGraph>::vertex_descriptor
  66     argument_type;
  67
  68   is_local_vertex() : g(0) {}
  69   is_local_vertex(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) { }
  70
  71   // Since either the source or target vertex must be local, the
  72   // equivalence of their owners indicates a local edge.
  73   result_type operator()(const argument_type& v) const
  74   {
  75     return get(owner, v) == process_id(process_group(*g));
  76   }
  77
  78 private:
  79   DistributedGraph* g;
  80   typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
  81 };
  82
  83 template<typename DistributedGraph>
  84 class local_subgraph
  85   : public filtered_graph<DistributedGraph,
  86                           is_local_edge<DistributedGraph>,
  87                           is_local_vertex<DistributedGraph> >
  88 {
  89   typedef filtered_graph<DistributedGraph,
  90                          is_local_edge<DistributedGraph>,
  91                          is_local_vertex<DistributedGraph> >
  92     inherited;
  93   typedef typename graph_traits<DistributedGraph>::traversal_category
  94     inherited_category;
  95
  96 public:
  97   struct traversal_category :
  98     graph::detail::derive_from_if_tag_is<incidence_graph_tag,
  99                                          inherited_category>,
 100     graph::detail::derive_from_if_tag_is<adjacency_graph_tag,
 101                                          inherited_category>,
 102     graph::detail::derive_from_if_tag_is<vertex_list_graph_tag,
 103                                          inherited_category>,
 104     graph::detail::derive_from_if_tag_is<edge_list_graph_tag,
 105                                          inherited_category>,
 106     graph::detail::derive_from_if_tag_is<vertex_list_graph_tag,
 107                                          inherited_category,
 108                                          distributed_vertex_list_graph_tag>,
 109     graph::detail::derive_from_if_tag_is<edge_list_graph_tag,
 110                                          inherited_category,
 111                                          distributed_edge_list_graph_tag>
 112   { };
 113
 114   local_subgraph(DistributedGraph& g)
 115     : inherited(g,
 116                 is_local_edge<DistributedGraph>(g),
 117                 is_local_vertex<DistributedGraph>(g)),
 118       g(g)
 119   {
 120   }
 121
 122   // Distributed Container
 123   typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
 124     process_group_type;
 125
 126   process_group_type&       process_group()
 127   {
 128     using boost::graph::parallel::process_group;
 129     return process_group(g);
 130   }
 131   const process_group_type& process_group() const
 132   {
 133     using boost::graph::parallel::process_group;
 134     return boost::graph::parallel::process_group(g);
 135   }
 136
 137   DistributedGraph&         base()               { return g; }
 138   const DistributedGraph&   base() const         { return g; }
 139
 140 private:
 141   DistributedGraph& g;
 142 };
 143
 144 template<typename DistributedGraph, typename PropertyTag>
 145 class property_map<local_subgraph<DistributedGraph>, PropertyTag>
 146   : public property_map<DistributedGraph, PropertyTag> { };
 147
 148 template<typename DistributedGraph, typename PropertyTag>
 149 class property_map<local_subgraph<const DistributedGraph>, PropertyTag>
 150 {
 151  public:
 152   typedef typename property_map<DistributedGraph, PropertyTag>::const_type
 153     type;
 154   typedef type const_type;
 155 };
 156
 157 template<typename PropertyTag, typename DistributedGraph>
 158 inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>::type
 159 get(PropertyTag p, local_subgraph<DistributedGraph>& g)
 160 { return get(p, g.base()); }
 161
 162 template<typename PropertyTag, typename DistributedGraph>
 163 inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>
 164   ::const_type
 165 get(PropertyTag p, const local_subgraph<DistributedGraph>& g)
 166 { return get(p, g.base()); }
 167
 168 template<typename DistributedGraph>
 169 inline local_subgraph<DistributedGraph>
 170 make_local_subgraph(DistributedGraph& g)
 171 { return local_subgraph<DistributedGraph>(g); }
 172
 173 } // end namespace boost
 174
 175 #endif // BOOST_GRAPH_LOCAL_SUBGRAPH_HPP