// 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 <boost/graph/use_mpi.hpp> has been included" | |
#endif | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/graph/two_bit_color_map.hpp> | |
#include <boost/graph/distributed/queue.hpp> | |
#include <boost/pending/queue.hpp> | |
#include <boost/graph/iteration_macros.hpp> | |
#include <boost/graph/parallel/container_traits.hpp> | |
#include <boost/property_map/property_map.hpp> | |
#include <boost/graph/parallel/algorithm.hpp> | |
#include <utility> | |
#include <boost/optional.hpp> | |
namespace boost { namespace graph { namespace distributed { | |
namespace detail { | |
struct pair_and_or | |
{ | |
std::pair<bool, bool> | |
operator()(std::pair<bool, bool> x, std::pair<bool, bool> y) const | |
{ | |
return std::pair<bool, bool>(x.first && y.first, | |
x.second || y.second); | |
} | |
}; | |
} // end namespace detail | |
template<typename DistributedGraph, typename ColorMap, typename OwnerMap> | |
bool | |
st_connected(const DistributedGraph& g, | |
typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
typename graph_traits<DistributedGraph>::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<ColorMap>::value_type Color; | |
typedef color_traits<Color> ColorTraits; | |
typedef typename process_group_type<DistributedGraph>::type ProcessGroup; | |
typedef typename ProcessGroup::process_id_type ProcessID; | |
typedef typename graph_traits<DistributedGraph>::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<Vertex> Q; | |
if (get(owner, s) == rank) Q.push(s); | |
if (get(owner, t) == rank) Q.push(t); | |
queue<Vertex> 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<std::pair<ProcessID, int> > msg = probe(pg)) { | |
std::pair<Vertex, bool> 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<bool, bool> 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<typename DistributedGraph, typename ColorMap> | |
inline bool | |
st_connected(const DistributedGraph& g, | |
typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
typename graph_traits<DistributedGraph>::vertex_descriptor t, | |
ColorMap color) | |
{ | |
return st_connected(g, s, t, color, get(vertex_owner, g)); | |
} | |
template<typename DistributedGraph> | |
inline bool | |
st_connected(const DistributedGraph& g, | |
typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
typename graph_traits<DistributedGraph>::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 |