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