308 lines
10 KiB
C++
308 lines
10 KiB
C++
// 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/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:
|
|
BOOST_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
|