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