]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2006 The Trustees of Indiana University. |
2 | ||
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) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
9 | #ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP | |
10 | #define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP | |
11 | ||
12 | #ifndef BOOST_GRAPH_USE_MPI | |
13 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
14 | #endif | |
15 | ||
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> | |
24 | #include <utility> | |
25 | #include <boost/optional.hpp> | |
26 | ||
27 | namespace boost { namespace graph { namespace distributed { | |
28 | ||
29 | namespace detail { | |
30 | struct pair_and_or | |
31 | { | |
32 | std::pair<bool, bool> | |
33 | operator()(std::pair<bool, bool> x, std::pair<bool, bool> y) const | |
34 | { | |
35 | return std::pair<bool, bool>(x.first && y.first, | |
36 | x.second || y.second); | |
37 | } | |
38 | }; | |
39 | ||
40 | } // end namespace detail | |
41 | ||
42 | template<typename DistributedGraph, typename ColorMap, typename OwnerMap> | |
43 | bool | |
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) | |
48 | { | |
49 | using boost::graph::parallel::process_group; | |
50 | using boost::graph::parallel::process_group_type; | |
51 | using boost::parallel::all_reduce; | |
52 | ||
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; | |
58 | ||
59 | // Set all vertices to white (unvisited) | |
60 | BGL_FORALL_VERTICES_T(v, g, DistributedGraph) | |
61 | put(color, v, ColorTraits::white()); | |
62 | ||
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); | |
66 | ||
67 | // Vertices found from the source are grey | |
68 | put(color, s, ColorTraits::gray()); | |
69 | ||
70 | // Vertices found from the target are green | |
71 | put(color, t, ColorTraits::green()); | |
72 | ||
73 | ProcessGroup pg = process_group(g); | |
74 | ProcessID rank = process_id(pg); | |
75 | ||
76 | // Build a local queue | |
77 | queue<Vertex> Q; | |
78 | if (get(owner, s) == rank) Q.push(s); | |
79 | if (get(owner, t) == rank) Q.push(t); | |
80 | ||
81 | queue<Vertex> other_Q; | |
82 | ||
83 | while (true) { | |
84 | bool found = false; | |
85 | ||
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); | |
90 | ||
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); | |
98 | ||
99 | // Either push v into the local queue or send it off to its | |
100 | // owner. | |
101 | ProcessID v_owner = get(owner, v); | |
102 | if (v_owner == rank) | |
103 | other_Q.push(v); | |
104 | else | |
105 | send(pg, v_owner, 0, | |
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! | |
109 | found = true; | |
110 | break; | |
111 | } | |
112 | } | |
113 | ||
114 | // u is done, so mark it black | |
115 | put(color, u, ColorTraits::black()); | |
116 | } | |
117 | ||
118 | // Ensure that all transmitted messages have been received. | |
119 | synchronize(pg); | |
120 | ||
121 | // Move all of the send-to-self values into the local Q. | |
122 | other_Q.swap(Q); | |
123 | ||
124 | if (!found) { | |
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); | |
129 | ||
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 | |
137 | // into the queue. | |
138 | Q.push(v); | |
139 | put(color, v, u_color); | |
140 | } else if (v_color != ColorTraits::black() && u_color != v_color) { | |
141 | // Colors have collided. We're done! | |
142 | found = true; | |
143 | break; | |
144 | } | |
145 | } | |
146 | } | |
147 | ||
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()); | |
152 | ||
153 | // If someone found the answer, we're done! | |
154 | if (results.second) | |
155 | return true; | |
156 | ||
157 | // If all queues are empty, we're done. | |
158 | if (results.first) | |
159 | return false; | |
160 | } | |
161 | } | |
162 | ||
163 | template<typename DistributedGraph, typename ColorMap> | |
164 | inline bool | |
165 | st_connected(const DistributedGraph& g, | |
166 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
167 | typename graph_traits<DistributedGraph>::vertex_descriptor t, | |
168 | ColorMap color) | |
169 | { | |
170 | return st_connected(g, s, t, color, get(vertex_owner, g)); | |
171 | } | |
172 | ||
173 | template<typename DistributedGraph> | |
174 | inline bool | |
175 | st_connected(const DistributedGraph& g, | |
176 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
177 | typename graph_traits<DistributedGraph>::vertex_descriptor t) | |
178 | { | |
179 | return st_connected(g, s, t, | |
180 | make_two_bit_color_map(num_vertices(g), | |
181 | get(vertex_index, g))); | |
182 | } | |
183 | ||
184 | } } } // end namespace boost::graph::distributed | |
185 | ||
186 | #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP |