1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
// 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
|
