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

   1 // Copyright (C) 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_DISTRIBUTED_ST_CONNECTED_HPP
  10 #define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_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/two_bit_color_map.hpp>
  18 #include <boost/graph/distributed/queue.hpp>
  19 #include <boost/pending/queue.hpp>
  20 #include <boost/graph/iteration_macros.hpp>
  21 #include <boost/graph/parallel/container_traits.hpp>
  22 #include <boost/property_map/property_map.hpp>
  23 #include <boost/graph/parallel/algorithm.hpp>
  24 #include <utility>
  25 #include <boost/optional.hpp>
  26
  27 namespace boost { namespace graph { namespace distributed {
  28
  29 namespace detail {
  30   struct pair_and_or
  31   {
  32     std::pair<bool, bool>
  33     operator()(std::pair<bool, bool> x, std::pair<bool, bool> y) const
  34     {
  35       return std::pair<bool, bool>(x.first && y.first,
  36                                    x.second || y.second);
  37     }
  38   };
  39
  40 } // end namespace detail
  41
  42 template<typename DistributedGraph, typename ColorMap, typename OwnerMap>
  43 bool
  44 st_connected(const DistributedGraph& g,
  45              typename graph_traits<DistributedGraph>::vertex_descriptor s,
  46              typename graph_traits<DistributedGraph>::vertex_descriptor t,
  47              ColorMap color, OwnerMap owner)
  48 {
  49   using boost::graph::parallel::process_group;
  50   using boost::graph::parallel::process_group_type;
  51   using boost::parallel::all_reduce;
  52
  53   typedef typename property_traits<ColorMap>::value_type Color;
  54   typedef color_traits<Color> ColorTraits;
  55   typedef typename process_group_type<DistributedGraph>::type ProcessGroup;
  56   typedef typename ProcessGroup::process_id_type ProcessID;
  57   typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;
  58
  59   // Set all vertices to white (unvisited)
  60   BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
  61     put(color, v, ColorTraits::white());
  62
  63   // "color" plays the role of a color map, with no synchronization.
  64   set_property_map_role(vertex_color, color);
  65   color.set_consistency_model(0);
  66
  67   // Vertices found from the source are grey
  68   put(color, s, ColorTraits::gray());
  69
  70   // Vertices found from the target are green
  71   put(color, t, ColorTraits::green());
  72
  73   ProcessGroup pg = process_group(g);
  74   ProcessID rank = process_id(pg);
  75
  76   // Build a local queue
  77   queue<Vertex> Q;
  78   if (get(owner, s) == rank) Q.push(s);
  79   if (get(owner, t) == rank) Q.push(t);
  80
  81   queue<Vertex> other_Q;
  82
  83   while (true) {
  84     bool found = false;
  85
  86     // Process all vertices in the local queue
  87     while (!found && !Q.empty()) {
  88       Vertex u = Q.top(); Q.pop();
  89       Color u_color = get(color, u);
  90
  91       BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph) {
  92         Vertex v = target(e, g);
  93         Color v_color = get(color, v);
  94         if (v_color == ColorTraits::white()) {
  95           // We have not seen "v" before; mark it with the same color as u
  96           Color u_color = get(color, u);
  97           put(color, v, u_color);
  98
  99           // Either push v into the local queue or send it off to its
 100           // owner.
 101           ProcessID v_owner = get(owner, v);
 102           if (v_owner == rank)
 103             other_Q.push(v);
 104           else
 105             send(pg, v_owner, 0,
 106                  std::make_pair(v, u_color == ColorTraits::gray()));
 107         } else if (v_color != ColorTraits::black() && u_color != v_color) {
 108           // Colors have collided. We're done!
 109           found = true;
 110           break;
 111         }
 112       }
 113
 114       // u is done, so mark it black
 115       put(color, u, ColorTraits::black());
 116     }
 117
 118     // Ensure that all transmitted messages have been received.
 119     synchronize(pg);
 120
 121     // Move all of the send-to-self values into the local Q.
 122     other_Q.swap(Q);
 123
 124     if (!found) {
 125       // Receive all messages
 126       while (optional<std::pair<ProcessID, int> > msg = probe(pg)) {
 127         std::pair<Vertex, bool> data;
 128         receive(pg, msg->first, msg->second, data);
 129
 130         // Determine the colors of u and v, the source and target
 131         // vertices (v is local).
 132         Vertex v = data.first;
 133         Color v_color = get(color, v);
 134         Color u_color = data.second? ColorTraits::gray() : ColorTraits::green();
 135         if (v_color == ColorTraits::white()) {
 136           // v had no color before, so give it u's color and push it
 137           // into the queue.
 138           Q.push(v);
 139           put(color, v, u_color);
 140         } else if (v_color != ColorTraits::black() && u_color != v_color) {
 141           // Colors have collided. We're done!
 142           found = true;
 143           break;
 144         }
 145       }
 146     }
 147
 148     // Check if either all queues are empty or
 149     std::pair<bool, bool> results = all_reduce(pg,
 150             boost::parallel::detail::make_untracked_pair(Q.empty(), found),
 151             detail::pair_and_or());
 152
 153     // If someone found the answer, we're done!
 154     if (results.second)
 155       return true;
 156
 157     // If all queues are empty, we're done.
 158     if (results.first)
 159       return false;
 160   }
 161 }
 162
 163 template<typename DistributedGraph, typename ColorMap>
 164 inline bool
 165 st_connected(const DistributedGraph& g,
 166              typename graph_traits<DistributedGraph>::vertex_descriptor s,
 167              typename graph_traits<DistributedGraph>::vertex_descriptor t,
 168              ColorMap color)
 169 {
 170   return st_connected(g, s, t, color, get(vertex_owner, g));
 171 }
 172
 173 template<typename DistributedGraph>
 174 inline bool
 175 st_connected(const DistributedGraph& g,
 176              typename graph_traits<DistributedGraph>::vertex_descriptor s,
 177              typename graph_traits<DistributedGraph>::vertex_descriptor t)
 178 {
 179   return st_connected(g, s, t,
 180                       make_two_bit_color_map(num_vertices(g),
 181                                              get(vertex_index, g)));
 182 }
 183
 184 } } } // end namespace boost::graph::distributed
 185
 186 #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP