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

   1 // Copyright (C) 2004-2008 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_DFS_HPP
  10 #define BOOST_GRAPH_DISTRIBUTED_DFS_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/property_map/property_map.hpp>
  18 #include <boost/graph/overloading.hpp>
  19 #include <boost/graph/properties.hpp>
  20 #include <boost/graph/distributed/concepts.hpp>
  21 #include <boost/static_assert.hpp>
  22 #include <boost/assert.hpp>
  23 #include <boost/graph/parallel/process_group.hpp>
  24 #include <boost/graph/parallel/container_traits.hpp>
  25
  26 namespace boost {
  27   namespace graph { namespace distributed { namespace detail {
  28     template<typename DistributedGraph, typename ColorMap, typename ParentMap,
  29              typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
  30     class parallel_dfs
  31     {
  32       typedef typename graph_traits<DistributedGraph>::vertex_iterator
  33         vertex_iterator;
  34       typedef typename graph_traits<DistributedGraph>::vertex_descriptor
  35         vertex_descriptor;
  36       typedef typename graph_traits<DistributedGraph>::out_edge_iterator
  37         out_edge_iterator;
  38
  39       typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
  40         ::type process_group_type;
  41       typedef typename process_group_type::process_id_type process_id_type;
  42
  43       /**
  44        * The first vertex in the pair is the local node (i) and the
  45        * second vertex in the pair is the (possibly remote) node (j).
  46        */
  47       typedef boost::parallel::detail::untracked_pair<vertex_descriptor, vertex_descriptor> vertex_pair;
  48
  49       typedef typename property_traits<ColorMap>::value_type color_type;
  50       typedef color_traits<color_type> Color;
  51
  52       // Message types
  53       enum { discover_msg = 10, return_msg = 50, visited_msg = 100 , done_msg = 150};
  54
  55
  56     public:
  57       parallel_dfs(const DistributedGraph& g, ColorMap color,
  58                    ParentMap parent, ExploreMap explore,
  59                    VertexIndexMap index_map, DFSVisitor vis)
  60         : g(g), color(color), parent(parent), explore(explore),
  61           index_map(index_map), vis(vis), pg(process_group(g)),
  62           owner(get(vertex_owner, g)), next_out_edge(num_vertices(g))
  63       { }
  64
  65       void run(vertex_descriptor s)
  66       {
  67         vertex_iterator vi, vi_end;
  68         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
  69           put(color, *vi, Color::white());
  70           put(parent, *vi, *vi);
  71           put(explore, *vi, *vi);
  72           next_out_edge[get(index_map, *vi)] = out_edges(*vi, g).first;
  73           vis.initialize_vertex(*vi, g);
  74         }
  75
  76         vis.start_vertex(s, g);
  77
  78         if (get(owner, s) == process_id(pg)) {
  79           send_oob(pg, get(owner, s), discover_msg, vertex_pair(s, s));
  80         }
  81
  82         bool done = false;
  83         while (!done) {
  84           std::pair<process_id_type, int> msg = *pg.poll(true);
  85
  86           switch (msg.second) {
  87           case discover_msg:
  88             {
  89               vertex_pair p;
  90               receive_oob(pg, msg.first, msg.second, p);
  91
  92               if (p.first != p.second) {
  93                 // delete j from nomessage(j)
  94                 if (get(color, p.second) != Color::black())
  95                   local_put(color, p.second, Color::gray());
  96
  97                 if (recover(p)) break;
  98               }
  99
 100               if (get(color, p.first) == Color::white()) {
 101                 put(color, p.first, Color::gray());
 102                 put(parent, p.first, p.second);
 103
 104                 vis.discover_vertex(p.first, g);
 105
 106                 if (shift_center_of_activity(p.first)) break;
 107
 108                 out_edge_iterator ei, ei_end;
 109                 for (boost::tie(ei,ei_end) = out_edges(p.first, g); ei != ei_end; ++ei)
 110                 {
 111                   // Notify everyone who may not know that the source
 112                   // vertex has been visited. They can then mark the
 113                   // corresponding color map entry gray.
 114                   if (get(parent, p.first) != target(*ei, g)
 115                       && get(explore, p.first) != target(*ei, g)) {
 116                     vertex_pair visit(target(*ei, g), p.first);
 117
 118                     send_oob(pg, get(owner, target(*ei, g)), visited_msg, visit);
 119                   }
 120                 }
 121               }
 122             }
 123             break;
 124
 125           case visited_msg:
 126             {
 127               vertex_pair p;
 128               receive_oob(pg, msg.first, msg.second, p);
 129
 130               // delete j from nomessage(j)
 131               if (get(color, p.second) != Color::black())
 132                 local_put(color, p.second, Color::gray());
 133
 134               recover(p);
 135             }
 136             break;
 137
 138           case return_msg:
 139             {
 140               vertex_pair p;
 141               receive_oob(pg, msg.first, msg.second, p);
 142
 143               // delete j from nomessage(i)
 144               local_put(color, p.second, Color::black());
 145
 146               shift_center_of_activity(p.first);
 147             }
 148             break;
 149
 150           case done_msg:
 151             {
 152               receive_oob(pg, msg.first, msg.second, done);
 153
 154               // Propagate done message downward in tree
 155               done = true;
 156               process_id_type id = process_id(pg);
 157               process_id_type left = 2*id + 1;
 158               process_id_type right = left + 1;
 159               if (left < num_processes(pg))
 160                 send_oob(pg, left, done_msg, done);
 161               if (right < num_processes(pg))
 162                 send_oob(pg, right, done_msg, done);
 163             }
 164             break;
 165
 166           default:
 167             BOOST_ASSERT(false);
 168           }
 169         }
 170       }
 171
 172     private:
 173       bool recover(const vertex_pair& p)
 174       {
 175         if (get(explore, p.first) == p.second) {
 176           return shift_center_of_activity(p.first);
 177         }
 178         else
 179           return false;
 180       }
 181
 182       bool shift_center_of_activity(vertex_descriptor i)
 183       {
 184         for (out_edge_iterator ei = next_out_edge[get(index_map, i)],
 185                                ei_end = out_edges(i, g).second;
 186              ei != ei_end; ++ei) {
 187           vis.examine_edge(*ei, g);
 188
 189           vertex_descriptor k = target(*ei, g);
 190           color_type target_color = get(color, k);
 191           if (target_color == Color::black()) vis.forward_or_cross_edge(*ei, g);
 192           else if (target_color == Color::gray()) vis.back_edge(*ei, g);
 193           else {
 194             put(explore, i, k);
 195             vis.tree_edge(*ei, g);
 196             vertex_pair p(k, i);
 197             send_oob(pg, get(owner, k), discover_msg, p);
 198             next_out_edge[get(index_map, i)] = ++ei;
 199             return false;
 200           }
 201         }
 202
 203         next_out_edge[get(index_map, i)] = out_edges(i, g).second;
 204         put(explore, i, i);
 205         put(color, i, Color::black());
 206         vis.finish_vertex(i, g);
 207
 208         if (get(parent, i) == i) {
 209           send_oob(pg, 0, done_msg, true);
 210           return true;
 211         }
 212         else {
 213           vertex_pair ret(get(parent, i), i);
 214           send_oob(pg, get(owner, ret.first), return_msg, ret);
 215         }
 216         return false;
 217       }
 218
 219       const DistributedGraph& g;
 220       ColorMap color;
 221       ParentMap parent;
 222       ExploreMap explore;
 223       VertexIndexMap index_map;
 224       DFSVisitor vis;
 225       process_group_type pg;
 226       typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
 227       std::vector<out_edge_iterator> next_out_edge;
 228     };
 229   } // end namespace detail
 230
 231   template<typename DistributedGraph, typename ColorMap, typename ParentMap,
 232            typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
 233   void
 234   tsin_depth_first_visit
 235     (const DistributedGraph& g,
 236      typename graph_traits<DistributedGraph>::vertex_descriptor s,
 237      DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore,
 238      VertexIndexMap index_map)
 239   {
 240     typedef typename graph_traits<DistributedGraph>::directed_category
 241       directed_category;
 242     BOOST_STATIC_ASSERT(
 243       (is_convertible<directed_category, undirected_tag>::value));
 244
 245     set_property_map_role(vertex_color, color);
 246     graph::distributed::detail::parallel_dfs
 247       <DistributedGraph, ColorMap, ParentMap, ExploreMap, VertexIndexMap,
 248        DFSVisitor> do_dfs(g, color, parent, explore, index_map, vis);
 249     do_dfs.run(s);
 250
 251     using boost::graph::parallel::process_group;
 252     synchronize(process_group(g));
 253   }
 254
 255   template<typename DistributedGraph, typename DFSVisitor,
 256            typename VertexIndexMap>
 257   void
 258   tsin_depth_first_visit
 259     (const DistributedGraph& g,
 260      typename graph_traits<DistributedGraph>::vertex_descriptor s,
 261      DFSVisitor vis,
 262      VertexIndexMap index_map)
 263   {
 264     typedef typename graph_traits<DistributedGraph>::vertex_descriptor
 265       vertex_descriptor;
 266
 267     std::vector<default_color_type> colors(num_vertices(g));
 268     std::vector<vertex_descriptor> parent(num_vertices(g));
 269     std::vector<vertex_descriptor> explore(num_vertices(g));
 270     tsin_depth_first_visit
 271       (g, s,
 272        vis,
 273        make_iterator_property_map(colors.begin(), index_map),
 274        make_iterator_property_map(parent.begin(), index_map),
 275        make_iterator_property_map(explore.begin(), index_map),
 276        index_map);
 277   }
 278
 279   template<typename DistributedGraph, typename DFSVisitor,
 280            typename VertexIndexMap>
 281   void
 282   tsin_depth_first_visit
 283     (const DistributedGraph& g,
 284      typename graph_traits<DistributedGraph>::vertex_descriptor s,
 285      DFSVisitor vis)
 286   {
 287     tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
 288   }
 289 } // end namespace distributed
 290
 291 using distributed::tsin_depth_first_visit;
 292
 293 } // end namespace graph
 294
 295 template<typename DistributedGraph, typename DFSVisitor>
 296 void
 297 depth_first_visit
 298   (const DistributedGraph& g,
 299    typename graph_traits<DistributedGraph>::vertex_descriptor s,
 300    DFSVisitor vis)
 301 {
 302   graph::tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
 303 }
 304
 305 } // end namespace boost
 306
 307 #endif // BOOST_GRAPH_DISTRIBUTED_DFS_HPP