/usr/include/boost/graph/distributed
Edit: /usr/include/boost/graph/distributed/st_connected.hpp (6158B)
// Copyright (C) 2006 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_ST_CONNECTED_HPP
#define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless
has been included"
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost { namespace graph { namespace distributed {
namespace detail {
struct pair_and_or
{
std::pair
operator()(std::pair x, std::pair y) const
{
return std::pair(x.first && y.first,
x.second || y.second);
}
};
} // end namespace detail
template
bool
st_connected(const DistributedGraph& g,
typename graph_traits::vertex_descriptor s,
typename graph_traits::vertex_descriptor t,
ColorMap color, OwnerMap owner)
{
using boost::graph::parallel::process_group;
using boost::graph::parallel::process_group_type;
using boost::parallel::all_reduce;
typedef typename property_traits::value_type Color;
typedef color_traits ColorTraits;
typedef typename process_group_type::type ProcessGroup;
typedef typename ProcessGroup::process_id_type ProcessID;
typedef typename graph_traits::vertex_descriptor Vertex;
// Set all vertices to white (unvisited)
BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
put(color, v, ColorTraits::white());
// "color" plays the role of a color map, with no synchronization.
set_property_map_role(vertex_color, color);
color.set_consistency_model(0);
// Vertices found from the source are grey
put(color, s, ColorTraits::gray());
// Vertices found from the target are green
put(color, t, ColorTraits::green());
ProcessGroup pg = process_group(g);
ProcessID rank = process_id(pg);
// Build a local queue
queue Q;
if (get(owner, s) == rank) Q.push(s);
if (get(owner, t) == rank) Q.push(t);
queue other_Q;
while (true) {
bool found = false;
// Process all vertices in the local queue
while (!found && !Q.empty()) {
Vertex u = Q.top(); Q.pop();
Color u_color = get(color, u);
BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph) {
Vertex v = target(e, g);
Color v_color = get(color, v);
if (v_color == ColorTraits::white()) {
// We have not seen "v" before; mark it with the same color as u
Color u_color = get(color, u);
put(color, v, u_color);
// Either push v into the local queue or send it off to its
// owner.
ProcessID v_owner = get(owner, v);
if (v_owner == rank)
other_Q.push(v);
else
send(pg, v_owner, 0,
std::make_pair(v, u_color == ColorTraits::gray()));
} else if (v_color != ColorTraits::black() && u_color != v_color) {
// Colors have collided. We're done!
found = true;
break;
}
}
// u is done, so mark it black
put(color, u, ColorTraits::black());
}
// Ensure that all transmitted messages have been received.
synchronize(pg);
// Move all of the send-to-self values into the local Q.
other_Q.swap(Q);
if (!found) {
// Receive all messages
while (optional > msg = probe(pg)) {
std::pair data;
receive(pg, msg->first, msg->second, data);
// Determine the colors of u and v, the source and target
// vertices (v is local).
Vertex v = data.first;
Color v_color = get(color, v);
Color u_color = data.second? ColorTraits::gray() : ColorTraits::green();
if (v_color == ColorTraits::white()) {
// v had no color before, so give it u's color and push it
// into the queue.
Q.push(v);
put(color, v, u_color);
} else if (v_color != ColorTraits::black() && u_color != v_color) {
// Colors have collided. We're done!
found = true;
break;
}
}
}
// Check if either all queues are empty or
std::pair results = all_reduce(pg,
boost::parallel::detail::make_untracked_pair(Q.empty(), found),
detail::pair_and_or());
// If someone found the answer, we're done!
if (results.second)
return true;
// If all queues are empty, we're done.
if (results.first)
return false;
}
}
template
inline bool
st_connected(const DistributedGraph& g,
typename graph_traits::vertex_descriptor s,
typename graph_traits::vertex_descriptor t,
ColorMap color)
{
return st_connected(g, s, t, color, get(vertex_owner, g));
}
template
inline bool
st_connected(const DistributedGraph& g,
typename graph_traits::vertex_descriptor s,
typename graph_traits::vertex_descriptor t)
{
return st_connected(g, s, t,
make_two_bit_color_map(num_vertices(g),
get(vertex_index, g)));
}
} } } // end namespace boost::graph::distributed
#endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP