| // 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 |