1 // Copyright (C) 2006 The Trustees of Indiana University.
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
7 // Authors: Douglas Gregor
9 #ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
10 #define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
16 #include <boost/graph/graph_traits.hpp>
17 #include <boost/graph/two_bit_color_map.hpp>
18 #include <boost/graph/distributed/queue.hpp>
19 #include <boost/pending/queue.hpp>
20 #include <boost/graph/iteration_macros.hpp>
21 #include <boost/graph/parallel/container_traits.hpp>
22 #include <boost/property_map/property_map.hpp>
23 #include <boost/graph/parallel/algorithm.hpp>
25 #include <boost/optional.hpp>
27 namespace boost { namespace graph { namespace distributed {
33 operator()(std::pair<bool, bool> x, std::pair<bool, bool> y) const
35 return std::pair<bool, bool>(x.first && y.first,
36 x.second || y.second);
40 } // end namespace detail
42 template<typename DistributedGraph, typename ColorMap, typename OwnerMap>
44 st_connected(const DistributedGraph& g,
45 typename graph_traits<DistributedGraph>::vertex_descriptor s,
46 typename graph_traits<DistributedGraph>::vertex_descriptor t,
47 ColorMap color, OwnerMap owner)
49 using boost::graph::parallel::process_group;
50 using boost::graph::parallel::process_group_type;
51 using boost::parallel::all_reduce;
53 typedef typename property_traits<ColorMap>::value_type Color;
54 typedef color_traits<Color> ColorTraits;
55 typedef typename process_group_type<DistributedGraph>::type ProcessGroup;
56 typedef typename ProcessGroup::process_id_type ProcessID;
57 typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;
59 // Set all vertices to white (unvisited)
60 BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
61 put(color, v, ColorTraits::white());
63 // "color" plays the role of a color map, with no synchronization.
64 set_property_map_role(vertex_color, color);
65 color.set_consistency_model(0);
67 // Vertices found from the source are grey
68 put(color, s, ColorTraits::gray());
70 // Vertices found from the target are green
71 put(color, t, ColorTraits::green());
73 ProcessGroup pg = process_group(g);
74 ProcessID rank = process_id(pg);
76 // Build a local queue
78 if (get(owner, s) == rank) Q.push(s);
79 if (get(owner, t) == rank) Q.push(t);
81 queue<Vertex> other_Q;
86 // Process all vertices in the local queue
87 while (!found && !Q.empty()) {
88 Vertex u = Q.top(); Q.pop();
89 Color u_color = get(color, u);
91 BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph) {
92 Vertex v = target(e, g);
93 Color v_color = get(color, v);
94 if (v_color == ColorTraits::white()) {
95 // We have not seen "v" before; mark it with the same color as u
96 Color u_color = get(color, u);
97 put(color, v, u_color);
99 // Either push v into the local queue or send it off to its
101 ProcessID v_owner = get(owner, v);
106 std::make_pair(v, u_color == ColorTraits::gray()));
107 } else if (v_color != ColorTraits::black() && u_color != v_color) {
108 // Colors have collided. We're done!
114 // u is done, so mark it black
115 put(color, u, ColorTraits::black());
118 // Ensure that all transmitted messages have been received.
121 // Move all of the send-to-self values into the local Q.
125 // Receive all messages
126 while (optional<std::pair<ProcessID, int> > msg = probe(pg)) {
127 std::pair<Vertex, bool> data;
128 receive(pg, msg->first, msg->second, data);
130 // Determine the colors of u and v, the source and target
131 // vertices (v is local).
132 Vertex v = data.first;
133 Color v_color = get(color, v);
134 Color u_color = data.second? ColorTraits::gray() : ColorTraits::green();
135 if (v_color == ColorTraits::white()) {
136 // v had no color before, so give it u's color and push it
139 put(color, v, u_color);
140 } else if (v_color != ColorTraits::black() && u_color != v_color) {
141 // Colors have collided. We're done!
148 // Check if either all queues are empty or
149 std::pair<bool, bool> results = all_reduce(pg,
150 boost::parallel::detail::make_untracked_pair(Q.empty(), found),
151 detail::pair_and_or());
153 // If someone found the answer, we're done!
157 // If all queues are empty, we're done.
163 template<typename DistributedGraph, typename ColorMap>
165 st_connected(const DistributedGraph& g,
166 typename graph_traits<DistributedGraph>::vertex_descriptor s,
167 typename graph_traits<DistributedGraph>::vertex_descriptor t,
170 return st_connected(g, s, t, color, get(vertex_owner, g));
173 template<typename DistributedGraph>
175 st_connected(const DistributedGraph& g,
176 typename graph_traits<DistributedGraph>::vertex_descriptor s,
177 typename graph_traits<DistributedGraph>::vertex_descriptor t)
179 return st_connected(g, s, t,
180 make_two_bit_color_map(num_vertices(g),
181 get(vertex_index, g)));
184 } } } // end namespace boost::graph::distributed
186 #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP