<ahref="#BFSIntroduction">What is BFS and Why Parallelize It?</a>
</li>
<liclass="level1">
<ahref="#BFSImplementation">Implementation</a>
</li>
<liclass="level1">
<ahref="#BFSConditionTask">Encoding the Loop as a Condition Task</a>
</li>
</ul>
</div>
<divclass="textblock"><p>We implement a parallel breadth-first search (BFS) using <aclass="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><aclass="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>
<divclass="dotgraph">
<iframescrolling="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><aclass="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>
<divclass="line"><spanclass="keyword">const</span><spanclass="keywordtype">int</span> N = <spanclass="keyword">static_cast<</span><spanclass="keywordtype">int</span><spanclass="keyword">></span>(graph.size());</div>
<divclass="line"></div>
<divclass="line"><spanclass="keywordflow">for</span>(<spanclass="keywordtype">int</span> i = 0; i < N; i++) {</div>
<divclass="line"><spanclass="keywordtype">int</span> N = <spanclass="keyword">static_cast<</span><spanclass="keywordtype">int</span><spanclass="keyword">></span>(graph.size());</div>
<divclass="ttc" id="aclasstf_1_1Executor_html"><divclass="ttname"><ahref="classtf_1_1Executor.html">tf::Executor</a></div><divclass="ttdoc">class to create an executor</div><divclass="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_a519777f5783981d534e9e53b99712069"><divclass="ttname"><ahref="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">tf::Executor::run</a></div><divclass="ttdeci">tf::Future< void > run(Taskflow &taskflow)</div><divclass="ttdoc">runs a taskflow once</div></div>
<divclass="ttc" id="aclasstf_1_1FlowBuilder_html_a2582a216d54dacca2b7022ea7e89452a"><divclass="ttname"><ahref="classtf_1_1FlowBuilder.html#a2582a216d54dacca2b7022ea7e89452a">tf::FlowBuilder::for_each_by_index</a></div><divclass="ttdeci">Task for_each_by_index(R range, C callable, P part=P())</div><divclass="ttdoc">constructs a parallel-for task over a one- or multi-dimensional index range</div></div>
<divclass="ttc" id="aclasstf_1_1IndexRanges_html_a253e15e199f974ee26b2e33a5e2b3cf1"><divclass="ttname"><ahref="classtf_1_1IndexRanges.html#a253e15e199f974ee26b2e33a5e2b3cf1">tf::IndexRanges::end</a></div><divclass="ttdeci">T end() const</div><divclass="ttdoc">queries the ending index of the range (only available when N == 1)</div><divclass="ttdef"><b>Definition</b> iterator.hpp:358</div></div>
<divclass="ttc" id="aclasstf_1_1IndexRanges_html_ae37261f0d2f326449c469233561a3da6"><divclass="ttname"><ahref="classtf_1_1IndexRanges.html#ae37261f0d2f326449c469233561a3da6">tf::IndexRanges::begin</a></div><divclass="ttdeci">T begin() const</div><divclass="ttdoc">queries the starting index of the range (only available when N == 1)</div><divclass="ttdef"><b>Definition</b> iterator.hpp:346</div></div>
<divclass="ttc" id="aclasstf_1_1IndexRanges_html_afcb30e2b9567ad685e702201d2265880"><divclass="ttname"><ahref="classtf_1_1IndexRanges.html#afcb30e2b9567ad685e702201d2265880">tf::IndexRanges::step_size</a></div><divclass="ttdeci">T step_size() const</div><divclass="ttdoc">queries the step size of the range (only available when N == 1)</div><divclass="ttdef"><b>Definition</b> iterator.hpp:370</div></div>
<divclass="ttc" id="aclasstf_1_1Taskflow_html"><divclass="ttname"><ahref="classtf_1_1Taskflow.html">tf::Taskflow</a></div><divclass="ttdoc">class to create a taskflow object</div><divclass="ttdef"><b>Definition</b> taskflow.hpp:64</div></div>
<divclass="ttc" id="anamespacetf_html_a6c928ec9248757ba8276e316ef26846b"><divclass="ttname"><ahref="namespacetf.html#a6c928ec9248757ba8276e316ef26846b">tf::IndexRange</a></div><divclass="ttdeci">IndexRanges< T, 1 > IndexRange</div><divclass="ttdoc">alias for the common 1D case of tf::IndexRanges</div><divclass="ttdef"><b>Definition</b> iterator.hpp:612</div></div>
<divclass="ttc" id="anamespacetf_html_a9922bf2ed04b3e630d4e62258d1a4213"><divclass="ttname"><ahref="namespacetf.html#a9922bf2ed04b3e630d4e62258d1a4213">tf::distance</a></div><divclass="ttdeci">constexpr size_t distance(T beg, T end, T step)</div><divclass="ttdoc">calculates the number of iterations in the given index range</div><divclass="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><aclass="anchor" id="BFSConditionTask"></a>
Encoding the Loop as a Condition Task</h1>
<p>The host loop calls <aclass="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 <aclass="el" href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069" title="runs a taskflow once">tf::Executor::run</a> call with minimal synchronization overhead:</p>
<divclass="ttc" id="aclasstf_1_1FlowBuilder_html_a4d52a7fe2814b264846a2085e931652c"><divclass="ttname"><ahref="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">tf::FlowBuilder::emplace</a></div><divclass="ttdeci">Task emplace(C &&callable)</div><divclass="ttdoc">creates a static task</div><divclass="ttdef"><b>Definition</b> flow_builder.hpp:1781</div></div>
<divclass="ttc" id="aclasstf_1_1Task_html_a302f51ed717d0a4e99edc50f92a571f3"><divclass="ttname"><ahref="classtf_1_1Task.html#a302f51ed717d0a4e99edc50f92a571f3">tf::Task::reset</a></div><divclass="ttdeci">void reset()</div><divclass="ttdoc">resets the task handle to null</div><divclass="ttdef"><b>Definition</b> task.hpp:1425</div></div>
<divclass="ttc" id="aclasstf_1_1Task_html_a331b1b726555072e7c7d10941257f664"><divclass="ttname"><ahref="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">tf::Task::succeed</a></div><divclass="ttdeci">Task & succeed(Ts &&... tasks)</div><divclass="ttdoc">adds precedence links from other tasks to this</div><divclass="ttdef"><b>Definition</b> task.hpp:1313</div></div>
<divclass="ttc" id="aclasstf_1_1Task_html_a8c78c453295a553c1c016e4062da8588"><divclass="ttname"><ahref="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">tf::Task::precede</a></div><divclass="ttdeci">Task & precede(Ts &&... tasks)</div><divclass="ttdoc">adds precedence links from this to other tasks</div><divclass="ttdef"><b>Definition</b> task.hpp:1305</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>
<divclass="dotgraph">
<iframescrolling="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>
<dlclass="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 -->
<divid="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<liclass="navelem"><aclass="el" href="Examples.html">Learning from Examples</a></li>
<liclass="footer">
Maintained by <ahref="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <ahref="https://www.doxygen.org/index.html"><imgclass="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1