graph/distributed/st_connected.hpp

0001 // Copyright (C) 2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
0010 #define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
0011
0012 #ifndef BOOST_GRAPH_USE_MPI
0013 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0014 #endif
0015
0016 #include <boost/graph/graph_traits.hpp>
0017 #include <boost/graph/two_bit_color_map.hpp>
0018 #include <boost/graph/distributed/queue.hpp>
0019 #include <boost/pending/queue.hpp>
0020 #include <boost/graph/iteration_macros.hpp>
0021 #include <boost/graph/parallel/container_traits.hpp>
0022 #include <boost/property_map/property_map.hpp>
0023 #include <boost/property_map/parallel/parallel_property_maps.hpp>
0024 #include <boost/graph/parallel/algorithm.hpp>
0025 #include <utility>
0026 #include <boost/optional.hpp>
0027
0028 namespace boost { namespace graph { namespace distributed {
0029
0030 namespace detail {
0031   struct pair_and_or
0032   {
0033     std::pair<bool, bool>
0034     operator()(std::pair<bool, bool> x, std::pair<bool, bool> y) const
0035     {
0036       return std::pair<bool, bool>(x.first && y.first,
0037                                    x.second || y.second);
0038     }
0039   };
0040
0041 } // end namespace detail
0042
0043 template<typename DistributedGraph, typename ColorMap, typename OwnerMap>
0044 bool
0045 st_connected(const DistributedGraph& g,
0046              typename graph_traits<DistributedGraph>::vertex_descriptor s,
0047              typename graph_traits<DistributedGraph>::vertex_descriptor t,
0048              ColorMap color, OwnerMap owner)
0049 {
0050   using boost::graph::parallel::process_group;
0051   using boost::graph::parallel::process_group_type;
0052   using boost::parallel::all_reduce;
0053
0054   typedef typename property_traits<ColorMap>::value_type Color;
0055   typedef color_traits<Color> ColorTraits;
0056   typedef typename process_group_type<DistributedGraph>::type ProcessGroup;
0057   typedef typename ProcessGroup::process_id_type ProcessID;
0058   typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;
0059
0060   // Set all vertices to white (unvisited)
0061   BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
0062     put(color, v, ColorTraits::white());
0063
0064   // "color" plays the role of a color map, with no synchronization.
0065   set_property_map_role(vertex_color, color);
0066   color.set_consistency_model(0);
0067
0068   // Vertices found from the source are grey
0069   put(color, s, ColorTraits::gray());
0070
0071   // Vertices found from the target are green
0072   put(color, t, ColorTraits::green());
0073
0074   ProcessGroup pg = process_group(g);
0075   ProcessID rank = process_id(pg);
0076
0077   // Build a local queue
0078   queue<Vertex> Q;
0079   if (get(owner, s) == rank) Q.push(s);
0080   if (get(owner, t) == rank) Q.push(t);
0081
0082   queue<Vertex> other_Q;
0083
0084   while (true) {
0085     bool found = false;
0086
0087     // Process all vertices in the local queue
0088     while (!found && !Q.empty()) {
0089       Vertex u = Q.top(); Q.pop();
0090       Color u_color = get(color, u);
0091
0092       BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph) {
0093         Vertex v = target(e, g);
0094         Color v_color = get(color, v);
0095         if (v_color == ColorTraits::white()) {
0096           // We have not seen "v" before; mark it with the same color as u
0097           Color u_color = get(color, u);
0098           put(color, v, u_color);
0099
0100           // Either push v into the local queue or send it off to its
0101           // owner.
0102           ProcessID v_owner = get(owner, v);
0103           if (v_owner == rank)
0104             other_Q.push(v);
0105           else
0106             send(pg, v_owner, 0,
0107                  std::make_pair(v, u_color == ColorTraits::gray()));
0108         } else if (v_color != ColorTraits::black() && u_color != v_color) {
0109           // Colors have collided. We're done!
0110           found = true;
0111           break;
0112         }
0113       }
0114
0115       // u is done, so mark it black
0116       put(color, u, ColorTraits::black());
0117     }
0118
0119     // Ensure that all transmitted messages have been received.
0120     synchronize(pg);
0121
0122     // Move all of the send-to-self values into the local Q.
0123     other_Q.swap(Q);
0124
0125     if (!found) {
0126       // Receive all messages
0127       while (optional<std::pair<ProcessID, int> > msg = probe(pg)) {
0128         std::pair<Vertex, bool> data;
0129         receive(pg, msg->first, msg->second, data);
0130
0131         // Determine the colors of u and v, the source and target
0132         // vertices (v is local).
0133         Vertex v = data.first;
0134         Color v_color = get(color, v);
0135         Color u_color = data.second? ColorTraits::gray() : ColorTraits::green();
0136         if (v_color == ColorTraits::white()) {
0137           // v had no color before, so give it u's color and push it
0138           // into the queue.
0139           Q.push(v);
0140           put(color, v, u_color);
0141         } else if (v_color != ColorTraits::black() && u_color != v_color) {
0142           // Colors have collided. We're done!
0143           found = true;
0144           break;
0145         }
0146       }
0147     }
0148
0149     // Check if either all queues are empty or
0150     std::pair<bool, bool> results = all_reduce(pg,
0151             boost::parallel::detail::make_untracked_pair(Q.empty(), found),
0152             detail::pair_and_or());
0153
0154     // If someone found the answer, we're done!
0155     if (results.second)
0156       return true;
0157
0158     // If all queues are empty, we're done.
0159     if (results.first)
0160       return false;
0161   }
0162 }
0163
0164 template<typename DistributedGraph, typename ColorMap>
0165 inline bool
0166 st_connected(const DistributedGraph& g,
0167              typename graph_traits<DistributedGraph>::vertex_descriptor s,
0168              typename graph_traits<DistributedGraph>::vertex_descriptor t,
0169              ColorMap color)
0170 {
0171   return st_connected(g, s, t, color, get(vertex_owner, g));
0172 }
0173
0174 template<typename DistributedGraph>
0175 inline bool
0176 st_connected(const DistributedGraph& g,
0177              typename graph_traits<DistributedGraph>::vertex_descriptor s,
0178              typename graph_traits<DistributedGraph>::vertex_descriptor t)
0179 {
0180   return st_connected(g, s, t,
0181                       make_two_bit_color_map(num_vertices(g),
0182                                              get(vertex_index, g)));
0183 }
0184
0185 } } } // end namespace boost::graph::distributed
0186
0187 #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP