graph/distributed/depth_first_search.hpp

0001 // Copyright (C) 2004-2008 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_DISTRIBUTED_DFS_HPP
0010 #define BOOST_GRAPH_DISTRIBUTED_DFS_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/property_map/property_map.hpp>
0018 #include <boost/property_map/parallel/parallel_property_maps.hpp>
0019 #include <boost/graph/overloading.hpp>
0020 #include <boost/graph/properties.hpp>
0021 #include <boost/graph/distributed/concepts.hpp>
0022 #include <boost/static_assert.hpp>
0023 #include <boost/assert.hpp>
0024 #include <boost/graph/parallel/process_group.hpp>
0025 #include <boost/graph/parallel/container_traits.hpp>
0026
0027 namespace boost {
0028   namespace graph { namespace distributed { namespace detail {
0029     template<typename DistributedGraph, typename ColorMap, typename ParentMap,
0030              typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
0031     class parallel_dfs
0032     {
0033       typedef typename graph_traits<DistributedGraph>::vertex_iterator
0034         vertex_iterator;
0035       typedef typename graph_traits<DistributedGraph>::vertex_descriptor
0036         vertex_descriptor;
0037       typedef typename graph_traits<DistributedGraph>::out_edge_iterator
0038         out_edge_iterator;
0039
0040       typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
0041         ::type process_group_type;
0042       typedef typename process_group_type::process_id_type process_id_type;
0043
0044       /**
0045        * The first vertex in the pair is the local node (i) and the
0046        * second vertex in the pair is the (possibly remote) node (j).
0047        */
0048       typedef boost::parallel::detail::untracked_pair<vertex_descriptor, vertex_descriptor> vertex_pair;
0049
0050       typedef typename property_traits<ColorMap>::value_type color_type;
0051       typedef color_traits<color_type> Color;
0052
0053       // Message types
0054       enum { discover_msg = 10, return_msg = 50, visited_msg = 100 , done_msg = 150};
0055
0056
0057     public:
0058       parallel_dfs(const DistributedGraph& g, ColorMap color,
0059                    ParentMap parent, ExploreMap explore,
0060                    VertexIndexMap index_map, DFSVisitor vis)
0061         : g(g), color(color), parent(parent), explore(explore),
0062           index_map(index_map), vis(vis), pg(process_group(g)),
0063           owner(get(vertex_owner, g)), next_out_edge(num_vertices(g))
0064       { }
0065
0066       void run(vertex_descriptor s)
0067       {
0068         vertex_iterator vi, vi_end;
0069         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
0070           put(color, *vi, Color::white());
0071           put(parent, *vi, *vi);
0072           put(explore, *vi, *vi);
0073           next_out_edge[get(index_map, *vi)] = out_edges(*vi, g).first;
0074           vis.initialize_vertex(*vi, g);
0075         }
0076
0077         vis.start_vertex(s, g);
0078
0079         if (get(owner, s) == process_id(pg)) {
0080           send_oob(pg, get(owner, s), discover_msg, vertex_pair(s, s));
0081         }
0082
0083         bool done = false;
0084         while (!done) {
0085           std::pair<process_id_type, int> msg = *pg.poll(true);
0086
0087           switch (msg.second) {
0088           case discover_msg:
0089             {
0090               vertex_pair p;
0091               receive_oob(pg, msg.first, msg.second, p);
0092
0093               if (p.first != p.second) {
0094                 // delete j from nomessage(j)
0095                 if (get(color, p.second) != Color::black())
0096                   local_put(color, p.second, Color::gray());
0097
0098                 if (recover(p)) break;
0099               }
0100
0101               if (get(color, p.first) == Color::white()) {
0102                 put(color, p.first, Color::gray());
0103                 put(parent, p.first, p.second);
0104
0105                 vis.discover_vertex(p.first, g);
0106
0107                 if (shift_center_of_activity(p.first)) break;
0108
0109                 out_edge_iterator ei, ei_end;
0110                 for (boost::tie(ei,ei_end) = out_edges(p.first, g); ei != ei_end; ++ei)
0111                 {
0112                   // Notify everyone who may not know that the source
0113                   // vertex has been visited. They can then mark the
0114                   // corresponding color map entry gray.
0115                   if (get(parent, p.first) != target(*ei, g)
0116                       && get(explore, p.first) != target(*ei, g)) {
0117                     vertex_pair visit(target(*ei, g), p.first);
0118
0119                     send_oob(pg, get(owner, target(*ei, g)), visited_msg, visit);
0120                   }
0121                 }
0122               }
0123             }
0124             break;
0125
0126           case visited_msg:
0127             {
0128               vertex_pair p;
0129               receive_oob(pg, msg.first, msg.second, p);
0130
0131               // delete j from nomessage(j)
0132               if (get(color, p.second) != Color::black())
0133                 local_put(color, p.second, Color::gray());
0134
0135               recover(p);
0136             }
0137             break;
0138
0139           case return_msg:
0140             {
0141               vertex_pair p;
0142               receive_oob(pg, msg.first, msg.second, p);
0143
0144               // delete j from nomessage(i)
0145               local_put(color, p.second, Color::black());
0146
0147               shift_center_of_activity(p.first);
0148             }
0149             break;
0150
0151           case done_msg:
0152             {
0153               receive_oob(pg, msg.first, msg.second, done);
0154
0155               // Propagate done message downward in tree
0156               done = true;
0157               process_id_type id = process_id(pg);
0158               process_id_type left = 2*id + 1;
0159               process_id_type right = left + 1;
0160               if (left < num_processes(pg))
0161                 send_oob(pg, left, done_msg, done);
0162               if (right < num_processes(pg))
0163                 send_oob(pg, right, done_msg, done);
0164             }
0165             break;
0166
0167           default:
0168             BOOST_ASSERT(false);
0169           }
0170         }
0171       }
0172
0173     private:
0174       bool recover(const vertex_pair& p)
0175       {
0176         if (get(explore, p.first) == p.second) {
0177           return shift_center_of_activity(p.first);
0178         }
0179         else
0180           return false;
0181       }
0182
0183       bool shift_center_of_activity(vertex_descriptor i)
0184       {
0185         for (out_edge_iterator ei = next_out_edge[get(index_map, i)],
0186                                ei_end = out_edges(i, g).second;
0187              ei != ei_end; ++ei) {
0188           vis.examine_edge(*ei, g);
0189
0190           vertex_descriptor k = target(*ei, g);
0191           color_type target_color = get(color, k);
0192           if (target_color == Color::black()) vis.forward_or_cross_edge(*ei, g);
0193           else if (target_color == Color::gray()) vis.back_edge(*ei, g);
0194           else {
0195             put(explore, i, k);
0196             vis.tree_edge(*ei, g);
0197             vertex_pair p(k, i);
0198             send_oob(pg, get(owner, k), discover_msg, p);
0199             next_out_edge[get(index_map, i)] = ++ei;
0200             return false;
0201           }
0202         }
0203
0204         next_out_edge[get(index_map, i)] = out_edges(i, g).second;
0205         put(explore, i, i);
0206         put(color, i, Color::black());
0207         vis.finish_vertex(i, g);
0208
0209         if (get(parent, i) == i) {
0210           send_oob(pg, 0, done_msg, true);
0211           return true;
0212         }
0213         else {
0214           vertex_pair ret(get(parent, i), i);
0215           send_oob(pg, get(owner, ret.first), return_msg, ret);
0216         }
0217         return false;
0218       }
0219
0220       const DistributedGraph& g;
0221       ColorMap color;
0222       ParentMap parent;
0223       ExploreMap explore;
0224       VertexIndexMap index_map;
0225       DFSVisitor vis;
0226       process_group_type pg;
0227       typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
0228       std::vector<out_edge_iterator> next_out_edge;
0229     };
0230   } // end namespace detail
0231
0232   template<typename DistributedGraph, typename ColorMap, typename ParentMap,
0233            typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
0234   void
0235   tsin_depth_first_visit
0236     (const DistributedGraph& g,
0237      typename graph_traits<DistributedGraph>::vertex_descriptor s,
0238      DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore,
0239      VertexIndexMap index_map)
0240   {
0241     typedef typename graph_traits<DistributedGraph>::directed_category
0242       directed_category;
0243     BOOST_STATIC_ASSERT(
0244       (is_convertible<directed_category, undirected_tag>::value));
0245
0246     set_property_map_role(vertex_color, color);
0247     graph::distributed::detail::parallel_dfs
0248       <DistributedGraph, ColorMap, ParentMap, ExploreMap, VertexIndexMap,
0249        DFSVisitor> do_dfs(g, color, parent, explore, index_map, vis);
0250     do_dfs.run(s);
0251
0252     using boost::graph::parallel::process_group;
0253     synchronize(process_group(g));
0254   }
0255
0256   template<typename DistributedGraph, typename DFSVisitor,
0257            typename VertexIndexMap>
0258   void
0259   tsin_depth_first_visit
0260     (const DistributedGraph& g,
0261      typename graph_traits<DistributedGraph>::vertex_descriptor s,
0262      DFSVisitor vis,
0263      VertexIndexMap index_map)
0264   {
0265     typedef typename graph_traits<DistributedGraph>::vertex_descriptor
0266       vertex_descriptor;
0267
0268     std::vector<default_color_type> colors(num_vertices(g));
0269     std::vector<vertex_descriptor> parent(num_vertices(g));
0270     std::vector<vertex_descriptor> explore(num_vertices(g));
0271     tsin_depth_first_visit
0272       (g, s,
0273        vis,
0274        make_iterator_property_map(colors.begin(), index_map),
0275        make_iterator_property_map(parent.begin(), index_map),
0276        make_iterator_property_map(explore.begin(), index_map),
0277        index_map);
0278   }
0279
0280   template<typename DistributedGraph, typename DFSVisitor,
0281            typename VertexIndexMap>
0282   void
0283   tsin_depth_first_visit
0284     (const DistributedGraph& g,
0285      typename graph_traits<DistributedGraph>::vertex_descriptor s,
0286      DFSVisitor vis)
0287   {
0288     tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
0289   }
0290 } // end namespace distributed
0291
0292 using distributed::tsin_depth_first_visit;
0293
0294 } // end namespace graph
0295
0296 template<typename DistributedGraph, typename DFSVisitor>
0297 void
0298 depth_first_visit
0299   (const DistributedGraph& g,
0300    typename graph_traits<DistributedGraph>::vertex_descriptor s,
0301    DFSVisitor vis)
0302 {
0303   graph::tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
0304 }
0305
0306 } // end namespace boost
0307
0308 #endif // BOOST_GRAPH_DISTRIBUTED_DFS_HPP