Chris@16: // Copyright (C) 2004-2008 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_DISTRIBUTED_DFS_HPP
Chris@16: #define BOOST_GRAPH_DISTRIBUTED_DFS_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/overloading.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/graph/distributed/concepts.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/graph/parallel/process_group.hpp>
Chris@16: #include <boost/graph/parallel/container_traits.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16:   namespace graph { namespace distributed { namespace detail {
Chris@16:     template<typename DistributedGraph, typename ColorMap, typename ParentMap,
Chris@16:              typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
Chris@16:     class parallel_dfs
Chris@16:     {
Chris@16:       typedef typename graph_traits<DistributedGraph>::vertex_iterator
Chris@16:         vertex_iterator;
Chris@16:       typedef typename graph_traits<DistributedGraph>::vertex_descriptor
Chris@16:         vertex_descriptor;
Chris@16:       typedef typename graph_traits<DistributedGraph>::out_edge_iterator
Chris@16:         out_edge_iterator;
Chris@16: 
Chris@16:       typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
Chris@16:         ::type process_group_type;
Chris@16:       typedef typename process_group_type::process_id_type process_id_type;
Chris@16: 
Chris@16:       /**
Chris@16:        * The first vertex in the pair is the local node (i) and the
Chris@16:        * second vertex in the pair is the (possibly remote) node (j).
Chris@16:        */
Chris@16:       typedef boost::parallel::detail::untracked_pair<vertex_descriptor, vertex_descriptor> vertex_pair;
Chris@16: 
Chris@16:       typedef typename property_traits<ColorMap>::value_type color_type;
Chris@16:       typedef color_traits<color_type> Color;
Chris@16: 
Chris@16:       // Message types
Chris@16:       enum { discover_msg = 10, return_msg = 50, visited_msg = 100 , done_msg = 150};
Chris@16:         
Chris@16: 
Chris@16:     public:
Chris@16:       parallel_dfs(const DistributedGraph& g, ColorMap color,
Chris@16:                    ParentMap parent, ExploreMap explore,
Chris@16:                    VertexIndexMap index_map, DFSVisitor vis)
Chris@16:         : g(g), color(color), parent(parent), explore(explore),
Chris@16:           index_map(index_map), vis(vis), pg(process_group(g)),
Chris@16:           owner(get(vertex_owner, g)), next_out_edge(num_vertices(g))
Chris@16:       { }
Chris@16: 
Chris@16:       void run(vertex_descriptor s)
Chris@16:       {
Chris@16:         vertex_iterator vi, vi_end;
Chris@16:         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
Chris@16:           put(color, *vi, Color::white());
Chris@16:           put(parent, *vi, *vi); 
Chris@16:           put(explore, *vi, *vi);
Chris@16:           next_out_edge[get(index_map, *vi)] = out_edges(*vi, g).first;
Chris@16:           vis.initialize_vertex(*vi, g);
Chris@16:         }
Chris@16: 
Chris@16:         vis.start_vertex(s, g);
Chris@16:         
Chris@16:         if (get(owner, s) == process_id(pg)) {
Chris@16:           send_oob(pg, get(owner, s), discover_msg, vertex_pair(s, s));
Chris@16:         }
Chris@16:         
Chris@16:         bool done = false;
Chris@16:         while (!done) {
Chris@16:           std::pair<process_id_type, int> msg = *pg.poll(true);
Chris@16: 
Chris@16:           switch (msg.second) {
Chris@16:           case discover_msg:
Chris@16:             {
Chris@16:               vertex_pair p;
Chris@16:               receive_oob(pg, msg.first, msg.second, p);
Chris@16: 
Chris@16:               if (p.first != p.second) {
Chris@16:                 // delete j from nomessage(j)
Chris@16:                 if (get(color, p.second) != Color::black())
Chris@16:                   local_put(color, p.second, Color::gray());
Chris@16: 
Chris@16:                 if (recover(p)) break;
Chris@16:               }
Chris@16: 
Chris@16:               if (get(color, p.first) == Color::white()) {
Chris@16:                 put(color, p.first, Color::gray());
Chris@16:                 put(parent, p.first, p.second);
Chris@16: 
Chris@16:                 vis.discover_vertex(p.first, g);
Chris@16: 
Chris@16:                 if (shift_center_of_activity(p.first)) break;
Chris@16:                 
Chris@16:                 out_edge_iterator ei, ei_end;
Chris@16:                 for (boost::tie(ei,ei_end) = out_edges(p.first, g); ei != ei_end; ++ei)
Chris@16:                 {
Chris@16:                   // Notify everyone who may not know that the source
Chris@16:                   // vertex has been visited. They can then mark the
Chris@16:                   // corresponding color map entry gray.
Chris@16:                   if (get(parent, p.first) != target(*ei, g)
Chris@16:                       && get(explore, p.first) != target(*ei, g)) {
Chris@16:                     vertex_pair visit(target(*ei, g), p.first);
Chris@16:                     
Chris@16:                     send_oob(pg, get(owner, target(*ei, g)), visited_msg, visit);
Chris@16:                   }
Chris@16:                 }
Chris@16:               }
Chris@16:             }
Chris@16:             break;
Chris@16:             
Chris@16:           case visited_msg:
Chris@16:             {
Chris@16:               vertex_pair p;
Chris@16:               receive_oob(pg, msg.first, msg.second, p);
Chris@16:               
Chris@16:               // delete j from nomessage(j)
Chris@16:               if (get(color, p.second) != Color::black())
Chris@16:                 local_put(color, p.second, Color::gray());
Chris@16: 
Chris@16:               recover(p);
Chris@16:             }
Chris@16:             break;
Chris@16:             
Chris@16:           case return_msg:
Chris@16:             {
Chris@16:               vertex_pair p;
Chris@16:               receive_oob(pg, msg.first, msg.second, p);
Chris@16:               
Chris@16:               // delete j from nomessage(i)
Chris@16:               local_put(color, p.second, Color::black());
Chris@16: 
Chris@16:               shift_center_of_activity(p.first);
Chris@16:             }
Chris@16:             break;
Chris@16:             
Chris@16:           case done_msg:
Chris@16:             {
Chris@16:               receive_oob(pg, msg.first, msg.second, done);
Chris@16: 
Chris@16:               // Propagate done message downward in tree
Chris@16:               done = true;
Chris@16:               process_id_type id = process_id(pg);
Chris@16:               process_id_type left = 2*id + 1;
Chris@16:               process_id_type right = left + 1;
Chris@16:               if (left < num_processes(pg))
Chris@16:                 send_oob(pg, left, done_msg, done);
Chris@16:               if (right < num_processes(pg))
Chris@16:                 send_oob(pg, right, done_msg, done);
Chris@16:             }
Chris@16:             break;
Chris@16: 
Chris@16:           default:
Chris@16:             BOOST_ASSERT(false);
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:       
Chris@16:     private:
Chris@16:       bool recover(const vertex_pair& p)
Chris@16:       {
Chris@16:         if (get(explore, p.first) == p.second) {
Chris@16:           return shift_center_of_activity(p.first);
Chris@16:         }
Chris@16:         else
Chris@16:           return false;
Chris@16:       }
Chris@16:       
Chris@16:       bool shift_center_of_activity(vertex_descriptor i)
Chris@16:       {
Chris@16:         for (out_edge_iterator ei = next_out_edge[get(index_map, i)],
Chris@16:                                ei_end = out_edges(i, g).second;
Chris@16:              ei != ei_end; ++ei) {
Chris@16:           vis.examine_edge(*ei, g);
Chris@16: 
Chris@16:           vertex_descriptor k = target(*ei, g);
Chris@16:           color_type target_color = get(color, k);
Chris@16:           if (target_color == Color::black()) vis.forward_or_cross_edge(*ei, g);
Chris@16:           else if (target_color == Color::gray()) vis.back_edge(*ei, g);
Chris@16:           else {
Chris@16:             put(explore, i, k);
Chris@16:             vis.tree_edge(*ei, g);
Chris@16:             vertex_pair p(k, i);
Chris@16:             send_oob(pg, get(owner, k), discover_msg, p);
Chris@16:             next_out_edge[get(index_map, i)] = ++ei;
Chris@16:             return false;
Chris@16:           } 
Chris@16:         }
Chris@16: 
Chris@16:         next_out_edge[get(index_map, i)] = out_edges(i, g).second;
Chris@16:         put(explore, i, i);
Chris@16:         put(color, i, Color::black());
Chris@16:         vis.finish_vertex(i, g);
Chris@16:           
Chris@16:         if (get(parent, i) == i) {
Chris@16:           send_oob(pg, 0, done_msg, true);
Chris@16:           return true;
Chris@16:         }
Chris@16:         else {
Chris@16:           vertex_pair ret(get(parent, i), i);
Chris@16:           send_oob(pg, get(owner, ret.first), return_msg, ret);
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16: 
Chris@16:       const DistributedGraph& g; 
Chris@16:       ColorMap color;
Chris@16:       ParentMap parent; 
Chris@16:       ExploreMap explore;
Chris@16:       VertexIndexMap index_map;
Chris@16:       DFSVisitor vis;
Chris@16:       process_group_type pg;
Chris@16:       typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
Chris@16:       std::vector<out_edge_iterator> next_out_edge; 
Chris@16:     };
Chris@16:   } // end namespace detail
Chris@16: 
Chris@16:   template<typename DistributedGraph, typename ColorMap, typename ParentMap,
Chris@16:            typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
Chris@16:   void
Chris@16:   tsin_depth_first_visit
Chris@16:     (const DistributedGraph& g,
Chris@16:      typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:      DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore, 
Chris@16:      VertexIndexMap index_map)
Chris@16:   {
Chris@16:     typedef typename graph_traits<DistributedGraph>::directed_category
Chris@16:       directed_category;
Chris@16:     BOOST_STATIC_ASSERT(
Chris@16:       (is_convertible<directed_category, undirected_tag>::value));
Chris@16: 
Chris@16:     set_property_map_role(vertex_color, color);
Chris@16:     graph::distributed::detail::parallel_dfs
Chris@16:       <DistributedGraph, ColorMap, ParentMap, ExploreMap, VertexIndexMap, 
Chris@16:        DFSVisitor> do_dfs(g, color, parent, explore, index_map, vis);
Chris@16:     do_dfs.run(s);
Chris@16: 
Chris@16:     using boost::graph::parallel::process_group;
Chris@16:     synchronize(process_group(g));
Chris@16:   }
Chris@16:     
Chris@16:   template<typename DistributedGraph, typename DFSVisitor, 
Chris@16:            typename VertexIndexMap>
Chris@16:   void
Chris@16:   tsin_depth_first_visit
Chris@16:     (const DistributedGraph& g,
Chris@16:      typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:      DFSVisitor vis,
Chris@16:      VertexIndexMap index_map)
Chris@16:   {
Chris@16:     typedef typename graph_traits<DistributedGraph>::vertex_descriptor
Chris@16:       vertex_descriptor;
Chris@16: 
Chris@16:     std::vector<default_color_type> colors(num_vertices(g));
Chris@16:     std::vector<vertex_descriptor> parent(num_vertices(g));
Chris@16:     std::vector<vertex_descriptor> explore(num_vertices(g));
Chris@16:     tsin_depth_first_visit
Chris@16:       (g, s,
Chris@16:        vis,
Chris@16:        make_iterator_property_map(colors.begin(), index_map),
Chris@16:        make_iterator_property_map(parent.begin(), index_map),
Chris@16:        make_iterator_property_map(explore.begin(), index_map),
Chris@16:        index_map);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename DistributedGraph, typename DFSVisitor, 
Chris@16:            typename VertexIndexMap>
Chris@16:   void
Chris@16:   tsin_depth_first_visit
Chris@16:     (const DistributedGraph& g,
Chris@16:      typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:      DFSVisitor vis)
Chris@16:   {
Chris@16:     tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
Chris@16:   }
Chris@16: } // end namespace distributed
Chris@16: 
Chris@16: using distributed::tsin_depth_first_visit;
Chris@16: 
Chris@16: } // end namespace graph
Chris@16: 
Chris@16: template<typename DistributedGraph, typename DFSVisitor>
Chris@16: void
Chris@16: depth_first_visit
Chris@16:   (const DistributedGraph& g,
Chris@16:    typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:    DFSVisitor vis)
Chris@16: {
Chris@16:   graph::tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
Chris@16: }
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DISTRIBUTED_DFS_HPP