-
-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Expand file tree
/
Copy pathExamplesBFS.html
More file actions
302 lines (300 loc) · 27.8 KB
/
Copy pathExamplesBFS.html
File metadata and controls
302 lines (300 loc) · 27.8 KB
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
<!-- HTML header for doxygen 1.13.1-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.13.1"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow: A General-purpose Task-parallel Programming System: Parallel Breadth-First Search</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="clipboard.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="cookie.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="custom.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr id="projectrow">
<td id="projectlogo"><img alt="Logo" src="taskflow_logo.png"/></td>
<td id="projectalign">
<div id="projectname"><a href="https://github.com/taskflow/taskflow" style="color:inherit; text-decoration:none;">Taskflow: A General-purpose Task-parallel Programming System</a>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.13.1 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() { codefold.init(0); });
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() {
initMenu('',true,false,'search.php','Search',true);
$(function() { init_search(); });
});
/* @license-end */
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function(){initNavTree('ExamplesBFS.html',''); initResizable(true); });
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<div><div class="header">
<div class="headertitle"><div class="title">Parallel Breadth-First Search</div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
<li class="level1">
<a href="#BFSIntroduction">What is BFS and Why Parallelize It?</a>
</li>
<li class="level1">
<a href="#BFSImplementation">Implementation</a>
</li>
<li class="level1">
<a href="#BFSConditionTask">Encoding the Loop as a Condition Task</a>
</li>
</ul>
</div>
<div class="textblock"><p>We implement a parallel breadth-first search (BFS) using <a class="el" href="classtf_1_1FlowBuilder.html#a2582a216d54dacca2b7022ea7e89452a" title="constructs a parallel-for task over a one- or multi-dimensional index range">tf::Taskflow::for_each_by_index</a> to process each frontier level in parallel. This example demonstrates how an iterative graph algorithm with a data-dependent loop structure maps onto Taskflow's stateful parallel iteration model.</p>
<h1><a class="anchor" id="BFSIntroduction"></a>
What is BFS and Why Parallelize It?</h1>
<p>Breadth-first search (BFS) is one of the most fundamental graph algorithms. Starting from a source node, it visits every reachable node in the graph and records the shortest distance (in number of edges) from the source to each node. It is used in network routing, social network analysis, game AI pathfinding, dependency resolution, and many other applications. The key idea is that BFS discovers nodes layer by layer. All nodes at distance 1 from the source are found first, then all nodes at distance 2, and so on. Each layer is called a frontier: the set of nodes discovered at the same distance from the source.</p>
<p>The following figure illustrates this process on a small graph. <code>S</code> is the source. Nodes at the same distance are at the same level and share the same colour. Edges point from each node to the neighbours it discovers in the next level:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_bfs_frontier.svg" width="531" height="443"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>The sequential algorithm processes one node at a time within each frontier. But notice that all nodes within a frontier are completely independent of each other: they were discovered in the same round and none of them depends on another node at the same level to compute its distance. This means all nodes in a frontier can be processed in parallel, relaxing their outgoing edges simultaneously across multiple CPU cores. For large graphs with wide frontiers (e.g., social networks, web graphs, road networks) this parallelism can be substantial. A frontier of one million nodes with an average degree of ten means ten million edge relaxations that can all run concurrently.</p>
<h1><a class="anchor" id="BFSImplementation"></a>
Implementation</h1>
<p>We represent the graph as an adjacency list and maintain two frontier buffers: <code>curr_frontier</code> holds the nodes being processed in the current level, and <code>next_frontier</code> accumulates the nodes discovered for the next level. An atomic counter <code>next_size</code> tracks how many nodes have been written into <code>next_frontier</code> so far.</p>
<p>Distance values are stored as <code>std::atomic<int></code> so that multiple workers can race to claim an unvisited node safely. The first worker to set <code>distance[v]</code> from <code>INF</code> to a finite value wins; all others see the <code>compare_exchange_strong</code> fail and skip that node. This prevents any node from being added to <code>next_frontier</code> more than once.</p>
<p>Note that <code>curr_frontier</code> is read-only during the sweep and requires no synchronization; only <code>distance[]</code> and <code>next_size</code> are written concurrently.</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <taskflow/taskflow.hpp></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">const</span> <span class="keywordtype">int</span> INF = std::numeric_limits<int>::max();</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">void</span> bfs(</div>
<div class="line"> <span class="keyword">const</span> std::vector<std::vector<int>>& graph,</div>
<div class="line"> <span class="keywordtype">int</span> source,</div>
<div class="line"> std::vector<std::atomic<int>>& <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a></div>
<div class="line">) {</div>
<div class="line"> </div>
<div class="line"> <span class="keyword">const</span> <span class="keywordtype">int</span> N = <span class="keyword">static_cast<</span><span class="keywordtype">int</span><span class="keyword">></span>(graph.size());</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i = 0; i < N; i++) {</div>
<div class="line"> <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>[i].store(INF, std::memory_order_relaxed);</div>
<div class="line"> }</div>
<div class="line"> <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>[source].store(0, std::memory_order_relaxed);</div>
<div class="line"> </div>
<div class="line"> std::vector<int> curr_frontier, next_frontier(N);</div>
<div class="line"> std::atomic<int> next_size{0};</div>
<div class="line"> curr_frontier.reserve(N);</div>
<div class="line"> curr_frontier.push_back(source);</div>
<div class="line"> </div>
<div class="line"> <a class="code hl_class" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div>
<div class="line"> <a class="code hl_class" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// stateful range over the current frontier; reset each level</span></div>
<div class="line"> <a class="code hl_typedef" href="namespacetf.html#a6c928ec9248757ba8276e316ef26846b">tf::IndexRange<int></a> range(0, 0, 1);</div>
<div class="line"> </div>
<div class="line"> <span class="keyword">auto</span> sweep = taskflow.<a class="code hl_function" href="classtf_1_1FlowBuilder.html#a2582a216d54dacca2b7022ea7e89452a">for_each_by_index</a>(</div>
<div class="line"> std::ref(range),</div>
<div class="line"> [&](<span class="keyword">const</span> <a class="code hl_typedef" href="namespacetf.html#a6c928ec9248757ba8276e316ef26846b">tf::IndexRange<int></a>& sub) {</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> idx = sub.<a class="code hl_function" href="classtf_1_1IndexRanges.html#ae37261f0d2f326449c469233561a3da6">begin</a>(); idx < sub.<a class="code hl_function" href="classtf_1_1IndexRanges.html#a253e15e199f974ee26b2e33a5e2b3cf1">end</a>(); idx += sub.<a class="code hl_function" href="classtf_1_1IndexRanges.html#afcb30e2b9567ad685e702201d2265880">step_size</a>()) {</div>
<div class="line"> <span class="keywordtype">int</span> u = curr_frontier[idx];</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> v : graph[u]) {</div>
<div class="line"> <span class="keywordtype">int</span> expected = INF;</div>
<div class="line"> <span class="keywordflow">if</span>(<a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>[v].compare_exchange_strong(</div>
<div class="line"> expected,</div>
<div class="line"> <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>[u].load(std::memory_order_relaxed) + 1)</div>
<div class="line"> ) {</div>
<div class="line"> <span class="comment">// first worker to reach v claims it for the next frontier</span></div>
<div class="line"> <span class="keywordtype">int</span> pos = next_size.fetch_add(1, std::memory_order_relaxed);</div>
<div class="line"> next_frontier[pos] = v;</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line"> );</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// host-driven loop: one executor.run call per frontier level</span></div>
<div class="line"> <span class="keywordflow">while</span>(!curr_frontier.empty()) {</div>
<div class="line"> range.reset(0, <span class="keyword">static_cast<</span><span class="keywordtype">int</span><span class="keyword">></span>(curr_frontier.size()), 1);</div>
<div class="line"> next_size.store(0, std::memory_order_relaxed);</div>
<div class="line"> </div>
<div class="line"> executor.<a class="code hl_function" href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">run</a>(taskflow).wait();</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// promote next_frontier to curr_frontier for the next level</span></div>
<div class="line"> <span class="keywordtype">int</span> sz = next_size.load(std::memory_order_relaxed);</div>
<div class="line"> curr_frontier.assign(next_frontier.begin(), next_frontier.begin() + sz);</div>
<div class="line"> next_size.store(0, std::memory_order_relaxed);</div>
<div class="line"> }</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// example graph (undirected, stored as directed adjacency list)</span></div>
<div class="line"> <span class="comment">//</span></div>
<div class="line"> <span class="comment">// 0 --- 1 --- 3</span></div>
<div class="line"> <span class="comment">// | |</span></div>
<div class="line"> <span class="comment">// 2 --- 4 --- 5</span></div>
<div class="line"> <span class="comment">//</span></div>
<div class="line"> std::vector<std::vector<int>> graph = {</div>
<div class="line"> {1, 2}, <span class="comment">// 0</span></div>
<div class="line"> {0, 3, 4}, <span class="comment">// 1</span></div>
<div class="line"> {0, 4}, <span class="comment">// 2</span></div>
<div class="line"> {1}, <span class="comment">// 3</span></div>
<div class="line"> {1, 2, 5}, <span class="comment">// 4</span></div>
<div class="line"> {4} <span class="comment">// 5</span></div>
<div class="line"> };</div>
<div class="line"> </div>
<div class="line"> <span class="keywordtype">int</span> N = <span class="keyword">static_cast<</span><span class="keywordtype">int</span><span class="keyword">></span>(graph.size());</div>
<div class="line"> std::vector<std::atomic<int>> <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>(N);</div>
<div class="line"> </div>
<div class="line"> bfs(graph, 0, <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>); <span class="comment">// source = 0</span></div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i = 0; i < N; i++) {</div>
<div class="line"> printf(<span class="stringliteral">"distance[%d] = %d\n"</span>, i, <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>[i].load());</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclasstf_1_1Executor_html"><div class="ttname"><a href="classtf_1_1Executor.html">tf::Executor</a></div><div class="ttdoc">class to create an executor</div><div class="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<div class="ttc" id="aclasstf_1_1Executor_html_a519777f5783981d534e9e53b99712069"><div class="ttname"><a href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">tf::Executor::run</a></div><div class="ttdeci">tf::Future< void > run(Taskflow &taskflow)</div><div class="ttdoc">runs a taskflow once</div></div>
<div class="ttc" id="aclasstf_1_1FlowBuilder_html_a2582a216d54dacca2b7022ea7e89452a"><div class="ttname"><a href="classtf_1_1FlowBuilder.html#a2582a216d54dacca2b7022ea7e89452a">tf::FlowBuilder::for_each_by_index</a></div><div class="ttdeci">Task for_each_by_index(R range, C callable, P part=P())</div><div class="ttdoc">constructs a parallel-for task over a one- or multi-dimensional index range</div></div>
<div class="ttc" id="aclasstf_1_1IndexRanges_html_a253e15e199f974ee26b2e33a5e2b3cf1"><div class="ttname"><a href="classtf_1_1IndexRanges.html#a253e15e199f974ee26b2e33a5e2b3cf1">tf::IndexRanges::end</a></div><div class="ttdeci">T end() const</div><div class="ttdoc">queries the ending index of the range (only available when N == 1)</div><div class="ttdef"><b>Definition</b> iterator.hpp:358</div></div>
<div class="ttc" id="aclasstf_1_1IndexRanges_html_ae37261f0d2f326449c469233561a3da6"><div class="ttname"><a href="classtf_1_1IndexRanges.html#ae37261f0d2f326449c469233561a3da6">tf::IndexRanges::begin</a></div><div class="ttdeci">T begin() const</div><div class="ttdoc">queries the starting index of the range (only available when N == 1)</div><div class="ttdef"><b>Definition</b> iterator.hpp:346</div></div>
<div class="ttc" id="aclasstf_1_1IndexRanges_html_afcb30e2b9567ad685e702201d2265880"><div class="ttname"><a href="classtf_1_1IndexRanges.html#afcb30e2b9567ad685e702201d2265880">tf::IndexRanges::step_size</a></div><div class="ttdeci">T step_size() const</div><div class="ttdoc">queries the step size of the range (only available when N == 1)</div><div class="ttdef"><b>Definition</b> iterator.hpp:370</div></div>
<div class="ttc" id="aclasstf_1_1Taskflow_html"><div class="ttname"><a href="classtf_1_1Taskflow.html">tf::Taskflow</a></div><div class="ttdoc">class to create a taskflow object</div><div class="ttdef"><b>Definition</b> taskflow.hpp:64</div></div>
<div class="ttc" id="anamespacetf_html_a6c928ec9248757ba8276e316ef26846b"><div class="ttname"><a href="namespacetf.html#a6c928ec9248757ba8276e316ef26846b">tf::IndexRange</a></div><div class="ttdeci">IndexRanges< T, 1 > IndexRange</div><div class="ttdoc">alias for the common 1D case of tf::IndexRanges</div><div class="ttdef"><b>Definition</b> iterator.hpp:971</div></div>
<div class="ttc" id="anamespacetf_html_a9922bf2ed04b3e630d4e62258d1a4213"><div class="ttname"><a href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">tf::distance</a></div><div class="ttdeci">constexpr size_t distance(T beg, T end, T step)</div><div class="ttdoc">calculates the number of iterations in the given index range</div><div class="ttdef"><b>Definition</b> iterator.hpp:71</div></div>
</div><!-- fragment --><p>The stateful <code>std::ref(range)</code> is the key to making this work without rebuilding the taskflow each level. The <code>sweep</code> task reads the range at execution time, so updating <code>range</code> with <code>reset</code> before each <code>executor.run</code> call is all that is needed to redirect the parallel loop to the new frontier.</p>
<h1><a class="anchor" id="BFSConditionTask"></a>
Encoding the Loop as a Condition Task</h1>
<p>The host loop calls <a class="el" href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069" title="runs a taskflow once">tf::Executor::run</a> once per frontier level, re-entering the executor each time. An alternative is to encode the loop termination check as a condition task inside the graph itself, so the entire BFS runs in a single <a class="el" href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069" title="runs a taskflow once">tf::Executor::run</a> call with minimal synchronization overhead:</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div>
<div class="line"> </div>
<div class="line"><span class="keyword">auto</span> init = taskflow.<a class="code hl_function" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([&](){ </div>
<div class="line"> <span class="comment">// initialize data here ...</span></div>
<div class="line">});</div>
<div class="line"> </div>
<div class="line"><span class="keyword">auto</span> sweep = taskflow.<a class="code hl_function" href="classtf_1_1FlowBuilder.html#a2582a216d54dacca2b7022ea7e89452a">for_each_by_index</a>(</div>
<div class="line"> std::ref(range),</div>
<div class="line"> [&](<span class="keyword">const</span> <a class="code hl_typedef" href="namespacetf.html#a6c928ec9248757ba8276e316ef26846b">tf::IndexRange<int></a>& sub) {</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> idx = sub.<a class="code hl_function" href="classtf_1_1IndexRanges.html#ae37261f0d2f326449c469233561a3da6">begin</a>(); idx < sub.<a class="code hl_function" href="classtf_1_1IndexRanges.html#a253e15e199f974ee26b2e33a5e2b3cf1">end</a>(); idx += sub.<a class="code hl_function" href="classtf_1_1IndexRanges.html#afcb30e2b9567ad685e702201d2265880">step_size</a>()) {</div>
<div class="line"> <span class="keywordtype">int</span> u = curr_frontier[idx];</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> v : graph[u]) {</div>
<div class="line"> <span class="keyword">auto</span> expected = INF;</div>
<div class="line"> <span class="keywordflow">if</span>(<a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>[v].compare_exchange_strong(</div>
<div class="line"> expected,</div>
<div class="line"> <a class="code hl_function" href="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">distance</a>[u].load(std::memory_order_relaxed) + 1)) {</div>
<div class="line"> <span class="keywordtype">int</span> pos = next_size.fetch_add(1, std::memory_order_relaxed);</div>
<div class="line"> next_frontier[pos] = v;</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line">);</div>
<div class="line"> </div>
<div class="line"><span class="keyword">auto</span> check = taskflow.<a class="code hl_function" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([&]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> <span class="comment">// promote next_frontier to curr_frontier</span></div>
<div class="line"> <span class="keywordtype">int</span> sz = next_size.load(std::memory_order_relaxed);</div>
<div class="line"> curr_frontier.assign(next_frontier.begin(), next_frontier.begin() + sz);</div>
<div class="line"> next_size.store(0, std::memory_order_relaxed);</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">if</span>(curr_frontier.empty()) {</div>
<div class="line"> <span class="keywordflow">return</span> 1; <span class="comment">// no more nodes to visit: exit the graph</span></div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// prepare range for the next frontier level</span></div>
<div class="line"> range.reset(0, <span class="keyword">static_cast<</span><span class="keywordtype">int</span><span class="keyword">></span>(curr_frontier.size()), 1);</div>
<div class="line"> <span class="keywordflow">return</span> 0; <span class="comment">// loop back to sweep</span></div>
<div class="line">});</div>
<div class="line"> </div>
<div class="line">sweep.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(check)</div>
<div class="line"> .<a class="code hl_function" href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">succeed</a>(init)</div>
<div class="line">check.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(sweep); <span class="comment">// back-edge: return 0 loops here</span></div>
<div class="line"> </div>
<div class="line"><span class="comment">// initialize for the first frontier level before running</span></div>
<div class="line">range.<a class="code hl_function" href="classtf_1_1Task.html#a302f51ed717d0a4e99edc50f92a571f3">reset</a>(0, 1, 1); <span class="comment">// curr_frontier = {source}, size 1</span></div>
<div class="line">executor.<a class="code hl_function" href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">run</a>(taskflow).wait();</div>
<div class="ttc" id="aclasstf_1_1FlowBuilder_html_a4d52a7fe2814b264846a2085e931652c"><div class="ttname"><a href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">tf::FlowBuilder::emplace</a></div><div class="ttdeci">Task emplace(C &&callable)</div><div class="ttdoc">creates a static task</div><div class="ttdef"><b>Definition</b> flow_builder.hpp:1571</div></div>
<div class="ttc" id="aclasstf_1_1Task_html_a302f51ed717d0a4e99edc50f92a571f3"><div class="ttname"><a href="classtf_1_1Task.html#a302f51ed717d0a4e99edc50f92a571f3">tf::Task::reset</a></div><div class="ttdeci">void reset()</div><div class="ttdoc">resets the task handle to null</div><div class="ttdef"><b>Definition</b> task.hpp:1378</div></div>
<div class="ttc" id="aclasstf_1_1Task_html_a331b1b726555072e7c7d10941257f664"><div class="ttname"><a href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">tf::Task::succeed</a></div><div class="ttdeci">Task & succeed(Ts &&... tasks)</div><div class="ttdoc">adds precedence links from other tasks to this</div><div class="ttdef"><b>Definition</b> task.hpp:1266</div></div>
<div class="ttc" id="aclasstf_1_1Task_html_a8c78c453295a553c1c016e4062da8588"><div class="ttname"><a href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">tf::Task::precede</a></div><div class="ttdeci">Task & precede(Ts &&... tasks)</div><div class="ttdoc">adds precedence links from this to other tasks</div><div class="ttdef"><b>Definition</b> task.hpp:1258</div></div>
</div><!-- fragment --><p>The condition task runs on a single worker after <code>sweep</code> completes, so the promotion of <code>next_frontier</code> into <code>curr_frontier</code> and the <code>range</code> reset are sequenced correctly without any additional synchronization. The back-edge from <code>check</code> to <code>sweep</code> forms the BFS level loop; the executor drives the full traversal end-to-end in a single <code>run</code> call.</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_bfs_taskflow.svg" width="402" height="64"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<dl class="section note"><dt>Note</dt><dd>The <code>compare_exchange_strong</code> on <code>distance</code>[v] is the correctness guarantee that prevents a node from being visited twice. If two workers simultaneously attempt to claim the same unvisited node <code>v</code>, exactly one <code>compare_exchange_strong</code> will succeed (the one that sees <code>distance</code>[v]==INF); the other will fail because <code>distance</code>[v] is no longer <code>INF</code> and will skip <code>v</code>. This ensures <code>next_frontier</code> contains each node at most once and that <code>distance</code>[v] holds the correct shortest-path distance from the source. </dd></dl>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a class="el" href="Examples.html">Learning from Examples</a></li>
<li class="footer">
Maintained by <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1
</li>
</ul>
</div>