-
-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Expand file tree
/
Copy pathExamplesGraphColoring.html
More file actions
266 lines (264 loc) · 21.8 KB
/
Copy pathExamplesGraphColoring.html
File metadata and controls
266 lines (264 loc) · 21.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
<!-- 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: Graph Coloring</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('ExamplesGraphColoring.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">Graph Coloring</div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
<li class="level1">
<a href="#GCIntroduction">What is Graph Coloring?</a>
</li>
<li class="level1">
<a href="#GCWalkthrough">Concrete Walkthrough</a>
</li>
<li class="level1">
<a href="#GCImplementation">Implementation</a>
</li>
<li class="level1">
<a href="#GCDesignPoints">Design Points</a>
</li>
</ul>
</div>
<div class="textblock"><p>We implement a parallel graph coloring solver using <a class="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> for recursive task parallelism. This example demonstrates branch-and-bound search with symmetry breaking on a dynamically growing task tree, and shows how <a class="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> enables efficient parallel exploration of combinatorial search spaces.</p>
<h1><a class="anchor" id="GCIntroduction"></a>
What is Graph Coloring?</h1>
<p>Graph coloring assigns a color to each vertex of a graph such that no two adjacent vertices (vertices connected by an edge) share the same color. The goal is to find an assignment that uses as few colors as possible. The minimum number of colors needed is called the chromatic number of the graph.</p>
<div class="image">
<object type="image/svg+xml" data="gc_example.svg" style="pointer-events: none;"></object>
</div>
<p>Graph coloring appears throughout computer science and engineering. In compiler register allocation, each variable is a vertex and two variables share an edge if they are live at the same time; coloring the graph assigns registers to variables without conflicts. In exam scheduling, each course is a vertex and two courses share an edge if any student is enrolled in both; coloring assigns time slots with no student taking two exams simultaneously. In wireless network frequency assignment, transmitters that could interfere with each other share an edge; coloring assigns frequencies to avoid interference.</p>
<p>Finding the chromatic number is NP-hard in general. The only known exact algorithms explore an exponential search space, which makes parallelism essential for large graphs. Each branch of the search can be explored independently on a separate CPU core, and branches that cannot improve on the best coloring found so far can be pruned immediately.</p>
<h1><a class="anchor" id="GCWalkthrough"></a>
Concrete Walkthrough</h1>
<p>Consider the following 5-vertex graph, which is a 5-cycle (0-1-2-3-4-0) with one additional edge between vertices 0 and 2:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_gc_graph.svg" width="266" height="276"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>The edges are: 0-1, 0-2, 0-4, 1-2, 2-3, 3-4. The chromatic number of this graph is 3: vertices 0, 1, and 2 form a triangle (all mutually adjacent), so they each need a distinct color, and the remaining vertices can reuse those three colors. The branch-and-bound algorithm assigns colors to vertices one by one in order (0, 1, 2, 3, 4). At each vertex it tries all valid colors and prunes whenever the partial coloring already uses as many colors as the best complete coloring found so far.</p>
<p>Since colors are interchangeable labels, we can apply symmetry breaking to avoid redundancy by swapping all occurrences of color 0 and color 1 throughout a valid coloring gives an equally valid coloring. Without any constraint, the search tree explores all these equivalent relabelings and wastes time on duplicate work. The fix is to require colors to be introduced in order: the first vertex always gets color 0, and a new color <code>k+1</code> may only be assigned to a vertex if color <code>k</code> has already been used somewhere. This ensures each structurally distinct coloring is explored exactly once.</p>
<dl class="section note"><dt>Note</dt><dd>To better understand why this symmetry breaking works, think of colors as being "introduced" for the first time as we assign vertices in order. Color 0 is introduced when we assign vertex 0. Color 1 is introduced the first time we assign a vertex that cannot use color 0. Color 2 is introduced the first time we need a third color. By requiring that colors are always introduced in order 0, 1, 2, ... we pick exactly one canonical representative from all the equivalent relabelings.</dd></dl>
<p>In our example, vertex 0 must be color 0 (only choice by symmetry breaking). Vertex 1 is adjacent to vertex 0, so it cannot be color 0; by symmetry breaking it can only be color 1 (introducing color 1 for the first time). Vertex 2 is adjacent to both 0 and 1, so it cannot be 0 or 1; symmetry breaking allows color 2 (introducing it for the first time). From here the branching opens up for vertex 3.</p>
<p>The figure below shows the complete search tree. Peach nodes are explored, red nodes are pruned, yellow nodes are complete colorings that are not improvements, and the green node is the first optimal 3-coloring found:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_gc_tree.svg" width="502" height="539"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>After the first leaf <code></code>[0,1,2,0,1] establishes <code>best=3</code>, the branches <code>v3=1</code> and <code>v3=3</code> are immediately pruned: assigning color 1 to vertex 3 keeps <code>max_color=2</code> (3 colors) which equals <code>best</code> and cannot improve it, and assigning color 3 to vertex 3 introduces a 4th color which is worse. Only 8 nodes are evaluated out of a much larger unconstrained tree.</p>
<h1><a class="anchor" id="GCImplementation"></a>
Implementation</h1>
<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> N = 5;</div>
<div class="line"><span class="keyword">const</span> std::vector<std::vector<int>> adj = {</div>
<div class="line"> {1, 2, 4}, <span class="comment">// vertex 0: neighbors are 1, 2, 4</span></div>
<div class="line"> {0, 2}, <span class="comment">// vertex 1: neighbors are 0, 2</span></div>
<div class="line"> {0, 1, 3}, <span class="comment">// vertex 2: neighbors are 0, 1, 3</span></div>
<div class="line"> {2, 4}, <span class="comment">// vertex 3: neighbors are 2, 4</span></div>
<div class="line"> {0, 3}, <span class="comment">// vertex 4: neighbors are 0, 3</span></div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line">tf::Executor executor;</div>
<div class="line">std::atomic<int> best_colors{N}; <span class="comment">// worst case: N colors (one per vertex)</span></div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">void</span> color_graph(</div>
<div class="line"> <span class="keywordtype">int</span> v, <span class="comment">// current vertex to color</span></div>
<div class="line"> std::vector<int> colors, <span class="comment">// colors[i] = color assigned to vertex i (-1 if unassigned)</span></div>
<div class="line"> <span class="keywordtype">int</span> max_introduced <span class="comment">// highest color index introduced so far</span></div>
<div class="line">) {</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// pruning: even in the best case, this branch needs at least max_introduced+1</span></div>
<div class="line"> <span class="comment">// colors (those already introduced). if that already equals or exceeds the</span></div>
<div class="line"> <span class="comment">// best known coloring, there is no point exploring further.</span></div>
<div class="line"> <span class="keywordflow">if</span>(max_introduced + 1 >= best_colors.load(std::memory_order_relaxed)) <span class="keywordflow">return</span>;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// all vertices colored: try to update the best known coloring.</span></div>
<div class="line"> <span class="comment">// compare_exchange_weak retries if another worker concurrently updates</span></div>
<div class="line"> <span class="comment">// best_colors, ensuring only the true minimum is stored.</span></div>
<div class="line"> <span class="keywordflow">if</span>(v == N) {</div>
<div class="line"> <span class="keywordtype">int</span> num_colors = max_introduced + 1;</div>
<div class="line"> <span class="keywordtype">int</span> cur = best_colors.load(std::memory_order_relaxed);</div>
<div class="line"> <span class="keywordflow">while</span>(num_colors < cur &&</div>
<div class="line"> !best_colors.compare_exchange_weak(cur, num_colors,</div>
<div class="line"> std::memory_order_relaxed, std::memory_order_relaxed));</div>
<div class="line"> <span class="keywordflow">return</span>;</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// determine which colors are forbidden for vertex v:</span></div>
<div class="line"> <span class="comment">// any color already assigned to one of its neighbors.</span></div>
<div class="line"> std::vector<bool> forbidden(max_introduced + 2, <span class="keyword">false</span>);</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> u : adj[v]) {</div>
<div class="line"> <span class="keywordflow">if</span>(colors[u] >= 0) forbidden[colors[u]] = <span class="keyword">true</span>;</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// try each valid color in order (symmetry breaking: only introduce a new</span></div>
<div class="line"> <span class="comment">// color max_introduced+1 if all lower colors are forbidden for this vertex).</span></div>
<div class="line"> <span class="comment">// this guarantees colors are introduced in strictly increasing order across</span></div>
<div class="line"> <span class="comment">// the entire search, eliminating equivalent relabelings.</span></div>
<div class="line"> <span class="keyword">auto</span> tg = executor.<a class="code hl_function" href="classtf_1_1Executor.html#a8858a119b9ad697748293c4bb1408853">task_group</a>();</div>
<div class="line"> <span class="keywordtype">bool</span> first = <span class="keyword">true</span>;</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> c = 0; c <= max_introduced + 1; c++) {</div>
<div class="line"> <span class="keywordflow">if</span>(forbidden[c]) <span class="keywordflow">continue</span>;</div>
<div class="line"> </div>
<div class="line"> std::vector<int> new_colors = colors;</div>
<div class="line"> new_colors[v] = c;</div>
<div class="line"> <span class="keywordtype">int</span> new_max = std::max(max_introduced, c);</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">if</span>(first) {</div>
<div class="line"> <span class="comment">// explore the first valid color directly on the current worker</span></div>
<div class="line"> first = <span class="keyword">false</span>;</div>
<div class="line"> color_graph(v + 1, new_colors, new_max);</div>
<div class="line"> }</div>
<div class="line"> <span class="keywordflow">else</span> {</div>
<div class="line"> <span class="comment">// spawn remaining valid colors as parallel branches</span></div>
<div class="line"> tg.silent_async([=]() {</div>
<div class="line"> color_graph(v + 1, new_colors, new_max);</div>
<div class="line"> });</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// cooperatively wait for all spawned branches to complete.</span></div>
<div class="line"> <span class="comment">// corun() keeps the worker active in the executor's work-stealing loop</span></div>
<div class="line"> <span class="comment">// rather than blocking, enabling efficient cooperative execution.</span></div>
<div class="line"> tg.<a class="code hl_function" href="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">corun</a>();</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"> std::vector<int> colors(N, -1); <span class="comment">// -1 means unassigned</span></div>
<div class="line"> </div>
<div class="line"> <span class="comment">// the root call must run inside a worker so that task_group() is valid.</span></div>
<div class="line"> <span class="comment">// vertex 0 always gets color 0 by symmetry breaking (max_introduced starts at 0).</span></div>
<div class="line"> executor.<a class="code hl_function" href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">async</a>([&]() {</div>
<div class="line"> colors[0] = 0;</div>
<div class="line"> color_graph(1, colors, 0); <span class="comment">// start from vertex 1 with color 0 already introduced</span></div>
<div class="line"> }).get();</div>
<div class="line"> </div>
<div class="line"> printf(<span class="stringliteral">"Chromatic number: %d\n"</span>, best_colors.load());</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_a8858a119b9ad697748293c4bb1408853"><div class="ttname"><a href="classtf_1_1Executor.html#a8858a119b9ad697748293c4bb1408853">tf::Executor::task_group</a></div><div class="ttdeci">TaskGroup task_group()</div><div class="ttdoc">creates a task group that executes a collection of asynchronous tasks</div><div class="ttdef"><b>Definition</b> task_group.hpp:875</div></div>
<div class="ttc" id="aclasstf_1_1Executor_html_af960048056f7c6b5bc71f4f526f05df7"><div class="ttname"><a href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">tf::Executor::async</a></div><div class="ttdeci">auto async(P &&params, F &&func)</div><div class="ttdoc">creates a parameterized asynchronous task to run the given function</div></div>
<div class="ttc" id="aclasstf_1_1TaskGroup_html_a1f481dc466e3107a08346d1a124677bc"><div class="ttname"><a href="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">tf::TaskGroup::corun</a></div><div class="ttdeci">void corun()</div><div class="ttdoc">corun all tasks spawned by this task group with other workers</div><div class="ttdef"><b>Definition</b> task_group.hpp:725</div></div>
</div><!-- fragment --><p>The expected output is:</p>
<div class="fragment"><div class="line">Chromatic number: 3</div>
</div><!-- fragment --><h1><a class="anchor" id="GCDesignPoints"></a>
Design Points</h1>
<p>There are a few important design points worth noting for this example, which also apply generally to parallel search algorithms:</p>
<ul>
<li>Symmetry breaking eliminates redundant search: Without symmetry breaking, swapping two color labels anywhere in the tree produces a structurally identical coloring that would be explored separately. For a graph with chromatic number <code>k</code>, this causes up to <code>k!</code> times more work than necessary. The constraint that colors must be introduced in order 0, 1, 2, ... ensures each distinct coloring structure is visited exactly once. For our 3-colorable example this is a 3! = 6x reduction in the number of candidate colorings explored.</li>
<li>Pruning propagates instantly across all workers: The shared <code>std::atomic<int></code> <code>best_colors</code> is checked at the entry of every recursive call. When any worker finds a <code>k-coloring</code>, all other workers immediately see the tighter bound and prune any branch that would need <code>k</code> or more colors. This is the same mechanism as in the TSP example: shared atomic state turns the parallel search into a cooperative effort rather than independent races.</li>
<li>TaskGroup per recursive call: Each call to <code>color_graph</code> creates its own <code>tg</code> via <code>executor.task_group()</code>, valid because every call runs inside a worker thread. The first valid color is explored on the current worker to avoid task overhead, and remaining valid colors are spawned as <code>tg.silent_async</code> tasks. <code>tg.corun()</code> then cooperatively waits for all spawned branches without blocking the worker thread.</li>
<li>Vertex ordering affects performance: Coloring vertices in order of decreasing degree (most-constrained-first) tends to find good colorings earlier, tightening the pruning bound sooner and reducing the total search space. The implementation above uses a fixed order for clarity; a production solver would sort vertices by degree before starting.</li>
</ul>
<dl class="section note"><dt>Note</dt><dd>The <code>colors</code> and <code>forbidden</code> vectors are copied on each recursive call, which is simple and correct but not memory-efficient for large graphs. For graphs with hundreds of vertices, a bitmask representation of the color assignment and a single stack-allocated forbidden set would significantly reduce allocation overhead. </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>