-
Notifications
You must be signed in to change notification settings - Fork 5
Expand file tree
/
Copy pathkahns_algorithm.html
More file actions
819 lines (796 loc) · 80 KB
/
kahns_algorithm.html
File metadata and controls
819 lines (796 loc) · 80 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
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
<!--
This file has been auto-generated by main.rs from a markdown file of the same name.
Do not edit it by hand.
-->
<!DOCTYPE html>
<html>
<head>
<title>Cycle detection in graphs does not have to be hard: A lesser known, simple way with Kahn's algorithm</title>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link type="application/atom+xml" href="/blog/feed.xml" rel="self">
<link rel="shortcut icon" type="image/ico" href="/blog/favicon.ico">
<link rel="stylesheet" type="text/css" href="main.css">
<link rel="stylesheet" href="https://unpkg.com/@highlightjs/cdn-assets@11.8.0/styles/default.min.css">
<script type="module" src="main.js" async></script>
<script type="module" src="search.js" async></script>
</head>
<body>
<div id="banner">
<div id="name">
<img id="me" src="me.jpeg">
<span>Philippe Gaultier</span>
</div>
<input id="search" placeholder="🔎 Search" autocomplete=off>
<ul>
<li> <button id="dark-light-mode">Dark/Light</button> </li>
<li> <a href="/blog/body_of_work.html">Body of work</a> </li>
<li> <a href="/blog/articles-by-tag.html">Tags</a> </li>
<li> <a href="https://github.com/gaultier/resume/raw/master/Philippe_Gaultier_resume_en.pdf">
Resume
</a> </li>
<li> <a href="/blog/feed.xml">
<svg viewBox="0 0 24 24" fill="currentColor" xmlns="http://www.w3.org/2000/svg">
<path fill-rule="evenodd" clip-rule="evenodd" d="M5.5 3.5C4.39543 3.5 3.5 4.39543 3.5 5.5V18.5C3.5 19.6046 4.39543 20.5 5.5 20.5H18.5C19.6046 20.5 20.5 19.6046 20.5 18.5V5.5C20.5 4.39543 19.6046 3.5 18.5 3.5H5.5ZM7 19C8.10457 19 9 18.1046 9 17C9 15.8954 8.10457 15 7 15C5.89543 15 5 15.8954 5 17C5 18.1046 5.89543 19 7 19ZM6.14863 10.5052C6.14863 10.0379 6.52746 9.65906 6.99478 9.65906C7.95949 9.65906 8.91476 9.84908 9.80603 10.2183C10.6973 10.5874 11.5071 11.1285 12.1893 11.8107C12.8715 12.4929 13.4126 13.3027 13.7817 14.194C14.1509 15.0852 14.3409 16.0405 14.3409 17.0052C14.3409 17.4725 13.9621 17.8514 13.4948 17.8514C13.0275 17.8514 12.6486 17.4725 12.6486 17.0052C12.6486 16.2627 12.5024 15.5275 12.2183 14.8416C11.9341 14.1556 11.5177 13.5324 10.9927 13.0073C10.4676 12.4823 9.84437 12.0659 9.15842 11.7817C8.47246 11.4976 7.73726 11.3514 6.99478 11.3514C6.52746 11.3514 6.14863 10.9725 6.14863 10.5052ZM7 5.15385C6.53268 5.15385 6.15385 5.53268 6.15385 6C6.15385 6.46732 6.53268 6.84615 7 6.84615C8.33342 6.84615 9.65379 7.10879 10.8857 7.61907C12.1176 8.12935 13.237 8.87728 14.1799 9.82015C15.1227 10.763 15.8707 11.8824 16.3809 13.1143C16.8912 14.3462 17.1538 15.6666 17.1538 17C17.1538 17.4673 17.5327 17.8462 18 17.8462C18.4673 17.8462 18.8462 17.4673 18.8462 17C18.8462 15.4443 18.5397 13.9039 17.9444 12.4667C17.3491 11.0294 16.4765 9.72352 15.3765 8.6235C14.2765 7.52349 12.9706 6.65091 11.5333 6.05558C10.0961 5.46026 8.55566 5.15385 7 5.15385Z" fill="currentColor"/>
</svg>
</a> </li>
<li> <a href="https://www.linkedin.com/in/philippegaultier/">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" data-supported-dps="24x24" fill="currentColor" width="24" height="24" focusable="false">
<path d="M20.5 2h-17A1.5 1.5 0 002 3.5v17A1.5 1.5 0 003.5 22h17a1.5 1.5 0 001.5-1.5v-17A1.5 1.5 0 0020.5 2zM8 19H5v-9h3zM6.5 8.25A1.75 1.75 0 118.3 6.5a1.78 1.78 0 01-1.8 1.75zM19 19h-3v-4.74c0-1.42-.6-1.93-1.38-1.93A1.74 1.74 0 0013 14.19a.66.66 0 000 .14V19h-3v-9h2.9v1.3a3.11 3.11 0 012.7-1.4c1.55 0 3.36.86 3.36 3.66z"/>
</svg>
</a> </li>
<li> <a href="https://github.com/gaultier">
<svg height="32" aria-hidden="true" viewBox="0 0 24 24" version="1.1" width="32" data-view-component="true" fill="currentColor">
<path d="M12.5.75C6.146.75 1 5.896 1 12.25c0 5.089 3.292 9.387 7.863 10.91.575.101.79-.244.79-.546 0-.273-.014-1.178-.014-2.142-2.889.532-3.636-.704-3.866-1.35-.13-.331-.69-1.352-1.18-1.625-.402-.216-.977-.748-.014-.762.906-.014 1.553.834 1.769 1.179 1.035 1.74 2.688 1.25 3.349.948.1-.747.402-1.25.733-1.538-2.559-.287-5.232-1.279-5.232-5.678 0-1.25.445-2.285 1.178-3.09-.115-.288-.517-1.467.115-3.048 0 0 .963-.302 3.163 1.179.92-.259 1.897-.388 2.875-.388.977 0 1.955.13 2.875.388 2.2-1.495 3.162-1.179 3.162-1.179.633 1.581.23 2.76.115 3.048.733.805 1.179 1.825 1.179 3.09 0 4.413-2.688 5.39-5.247 5.678.417.36.776 1.05.776 2.128 0 1.538-.014 2.774-.014 3.162 0 .302.216.662.79.547C20.709 21.637 24 17.324 24 12.25 24 5.896 18.854.75 12.5.75Z"/>
</svg>
</a> </li>
<li> <a href="https://hachyderm.io/@pg">
<svg width="75" height="79" viewBox="0 0 75 79" xmlns="http://www.w3.org/2000/svg" fill="currentColor">
<path d="M73.8393 17.4898C72.6973 9.00165 65.2994 2.31235 56.5296 1.01614C55.05 0.797115 49.4441 0 36.4582 0H36.3612C23.3717 0 20.585 0.797115 19.1054 1.01614C10.5798 2.27644 2.79399 8.28712 0.904997 16.8758C-0.00358524 21.1056 -0.100549 25.7949 0.0682394 30.0965C0.308852 36.2651 0.355538 42.423 0.91577 48.5665C1.30307 52.6474 1.97872 56.6957 2.93763 60.6812C4.73325 68.042 12.0019 74.1676 19.1233 76.6666C26.7478 79.2728 34.9474 79.7055 42.8039 77.9162C43.6682 77.7151 44.5217 77.4817 45.3645 77.216C47.275 76.6092 49.5123 75.9305 51.1571 74.7385C51.1797 74.7217 51.1982 74.7001 51.2112 74.6753C51.2243 74.6504 51.2316 74.6229 51.2325 74.5948V68.6416C51.2321 68.6154 51.2259 68.5896 51.2142 68.5661C51.2025 68.5426 51.1858 68.522 51.1651 68.5058C51.1444 68.4896 51.1204 68.4783 51.0948 68.4726C51.0692 68.4669 51.0426 68.467 51.0171 68.4729C45.9835 69.675 40.8254 70.2777 35.6502 70.2682C26.7439 70.2682 24.3486 66.042 23.6626 64.2826C23.1113 62.762 22.7612 61.1759 22.6212 59.5646C22.6197 59.5375 22.6247 59.5105 22.6357 59.4857C22.6466 59.4609 22.6633 59.4391 22.6843 59.422C22.7053 59.4048 22.73 59.3929 22.7565 59.3871C22.783 59.3813 22.8104 59.3818 22.8367 59.3886C27.7864 60.5826 32.8604 61.1853 37.9522 61.1839C39.1768 61.1839 40.3978 61.1839 41.6224 61.1516C46.7435 61.008 52.1411 60.7459 57.1796 59.7621C57.3053 59.7369 57.431 59.7154 57.5387 59.6831C65.4861 58.157 73.0493 53.3672 73.8178 41.2381C73.8465 40.7606 73.9184 36.2364 73.9184 35.7409C73.9219 34.0569 74.4606 23.7949 73.8393 17.4898Z"/>
<path d="M61.2484 27.0263V48.114H52.8916V27.6475C52.8916 23.3388 51.096 21.1413 47.4437 21.1413C43.4287 21.1413 41.4177 23.7409 41.4177 28.8755V40.0782H33.1111V28.8755C33.1111 23.7409 31.0965 21.1413 27.0815 21.1413C23.4507 21.1413 21.6371 23.3388 21.6371 27.6475V48.114H13.2839V27.0263C13.2839 22.7176 14.384 19.2946 16.5843 16.7572C18.8539 14.2258 21.8311 12.926 25.5264 12.926C29.8036 12.926 33.0357 14.5705 35.1905 17.8559L37.2698 21.346L39.3527 17.8559C41.5074 14.5705 44.7395 12.926 49.0095 12.926C52.7013 12.926 55.6784 14.2258 57.9553 16.7572C60.1531 19.2922 61.2508 22.7152 61.2484 27.0263Z" fill="#928374" />
<defs>
<linearGradient id="paint0_linear_549_34" x1="37.0692" y1="0" x2="37.0692" y2="79" gradientUnits="userSpaceOnUse">
<stop stop-color="#6364FF"/>
<stop offset="1" stop-color="#563ACC"/>
</linearGradient>
</defs>
</svg>
</a> </li>
<li> <a href="https://bsky.app/profile/pgaultier.bsky.social">
<svg fill="currentColor" viewBox="0 0 64 57" width="32" style="width: 32px; height: 28.5px;"><path d="M13.873 3.805C21.21 9.332 29.103 20.537 32 26.55v15.882c0-.338-.13.044-.41.867-1.512 4.456-7.418 21.847-20.923 7.944-7.111-7.32-3.819-14.64 9.125-16.85-7.405 1.264-15.73-.825-18.014-9.015C1.12 23.022 0 8.51 0 6.55 0-3.268 8.579-.182 13.873 3.805ZM50.127 3.805C42.79 9.332 34.897 20.537 32 26.55v15.882c0-.338.13.044.41.867 1.512 4.456 7.418 21.847 20.923 7.944 7.111-7.32 3.819-14.64-9.125-16.85 7.405 1.264 15.73-.825 18.014-9.015C62.88 23.022 64 8.51 64 6.55c0-9.818-8.578-6.732-13.873-2.745Z"/></svg>
</a> </li>
</ul>
</div>
<div id="search-matches" hidden>
</div>
<div id="pseudo-body">
<div class="article-prelude">
<p><a href="/blog"> ⏴ Back to all articles</a></p>
<p class="publication-date">Published on 2023-06-03. Last modified on 2026-03-04.</p>
</div>
<div class="article-title">
<h1>Cycle detection in graphs does not have to be hard: A lesser known, simple way with Kahn's algorithm</h1>
<div class="tags"> <a href="/blog/articles-by-tag.html#graph" class="tag">Graph</a> <a href="/blog/articles-by-tag.html#algorithm" class="tag">Algorithm</a> <a href="/blog/articles-by-tag.html#javascript" class="tag">JavaScript</a> <a href="/blog/articles-by-tag.html#sql" class="tag">SQL</a> </div>
</div>
<details class="toc"><summary>Table of contents</summary>
<ul>
<li>
<a href="#introduction">Introduction</a>
</li>
<li>
<a href="#the-database">The database</a>
</li>
<li>
<a href="#topological-sort">Topological sort</a>
</li>
<li>
<a href="#how-to-store-the-graph-in-memory">How to store the graph in memory</a>
</li>
<li>
<a href="#kahn-s-algorithm">Kahn's algorithm</a>
</li>
<li>
<a href="#implementation">Implementation</a>
<ul>
<li>
<a href="#helpers">Helpers</a>
</li>
<li>
<a href="#the-algorithm">The algorithm</a>
</li>
<li>
<a href="#inserting-entries-in-the-database">Inserting entries in the database</a>
</li>
<li>
<a href="#detecting-cycles">Detecting cycles</a>
</li>
<li>
<a href="#detecting-multiple-roots">Detecting multiple roots</a>
</li>
</ul>
</li>
<li>
<a href="#playing-with-the-database">Playing with the database</a>
</li>
<li>
<a href="#closing-thoughts">Closing thoughts</a>
</li>
<li>
<a href="#addendum-the-full-code">Addendum: the full code</a>
</li>
</ul>
</details>
<h2 id="introduction">
<a class="title" href="#introduction">Introduction</a>
<a class="hash-anchor" href="#introduction" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>Graphs are everywhere in Software Engineering, or so we are told by Computer Science teachers and interviewers. But sometimes, they do show up in real problems.</p>
<p>Not too long ago, I was tasked to create a Web API to create and update a company's hierarchy of employee, and display that on a web page. Basically, who reports to whom.</p>
<p>In the simple case, it's a tree, when an employee reports to exactly one manager.</p>
<p><img src="kahns_algorithm_1.svg" alt="Employee hierarchy" /></p>
<p>Here's the tree of employees in an organization. An employee reports to a manager, and this forms a tree. The root is the CEO since they report to no one and so they have no outgoing edge.</p>
<p>An arrow (or 'edge') between two nodes means <code><source> reports to <destination></code>, for example: <code>Jane the CFO reports to Ellen the CEO</code>.</p>
<p>But here is the twist: our API receives a list of <code>employee -> manager</code> links, in any order:</p>
<pre>
<div class="code-header">
<span>Plaintext</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-plaintext"><span class="line-number"></span><span class="code-hl">Jane -> Ellen</span>
<span class="line-number"></span><span class="code-hl">Angela -> Ellen</span>
<span class="line-number"></span><span class="code-hl">Zoe -> Jane</span>
<span class="line-number"></span><span class="code-hl">Zoe -> Angela</span>
<span class="line-number"></span><span class="code-hl">Bella -> Angela</span>
<span class="line-number"></span><span class="code-hl">Miranda -> Angela</span>
</code></pre>
<p>It opens the door to various invalid inputs: links that form a graph (an employee has multiple managers), multiple roots (e.g. multiple CEOs) or cycles.</p>
<p>We have to detect those and reject them, such as this one:</p>
<p><img src="kahns_algorithm_1_invalid.svg" alt="Invalid employee hierarchy" /></p>
<h2 id="the-database">
<a class="title" href="#the-database">The database</a>
<a class="hash-anchor" href="#the-database" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>So how do we store all of those people in the database?</p>
<pre>
<div class="code-header">
<span>Sql</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-sql"><span class="line-number"></span><span class="code-hl">CREATE TABLE IF NOT EXISTS people(name TEXT NOT NULL UNIQUE, manager BIGINT REFERENCES people)</span>
</code></pre>
<p>Each employee has an optional reference to a manager.</p>
<blockquote>
<p>This is not a novel idea, actually this is one of the examples in the official <a href="https://www.sqlite.org/lang_with.html">SQLite documentation</a>.</p>
</blockquote>
<p>For example, to save <code>Ellen, CEO</code> inside the database, we do:</p>
<pre>
<div class="code-header">
<span>Sql</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-sql"><span class="line-number"></span><span class="code-hl">INSERT INTO people VALUES('Ellen, CEO', NULL)</span>
</code></pre>
<p>And to save <code>Jane, CFO</code> in the database:</p>
<pre>
<div class="code-header">
<span>Sql</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-sql"><span class="line-number"></span><span class="code-hl">INSERT INTO people VALUES('Jane, CFO', 1)</span>
</code></pre>
<p>Where <code>Ellen, CEO</code>, Jane's boss, which we just inserted before, has the id <code>1</code>.</p>
<p>Immediately, we notice that to insert an employee, their manager needs to already by in the database, by virtue of the self-referential foreign key <code>manager BIGINT REFERENCES people</code>.</p>
<p>So we need a way to sort the big list of <code>employee -> manager</code> links (or 'edges' in graph parlance), to insert them in the right order. First we insert the CEO, who reports to no one. Then we insert the employees directly reporting to the CEO. Then the employees reporting to those. Etc.</p>
<p>And that's called a topological sort.</p>
<p>A big benefit is that we hit three birds with one stone:</p>
<ul>
<li>We detect cycles</li>
<li>We have the nodes in a convenient order to insert them in the database</li>
<li>Since the algorithm for the topological sort takes as input an adjacency matrix (more on this later), we can easily detect the invalid case of a node having more than one outgoing edge (i.e. more than one manager, i.e. multiple roots).</li>
</ul>
<p>From now one, I will use the graph of employees (where <code>Zoe</code> has two managers) as example since that's a possible input to our API and we need to detect this case.</p>
<h2 id="topological-sort">
<a class="title" href="#topological-sort">Topological sort</a>
<a class="hash-anchor" href="#topological-sort" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>From Wikipedia:</p>
<blockquote>
<p>A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks</p>
</blockquote>
<p>That's a mouthful but it's not too hard.</p>
<p>A useful command line utility that's already on your (Unix) machine is <code>tsort</code>, which takes a list of edges as input, and outputs a topological sort. Here is the input in a text file (<code>people.txt</code>):</p>
<pre>
<div class="code-header">
<span>Plaintext</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-plaintext"><span class="line-number"></span><span class="code-hl">Jane Ellen</span>
<span class="line-number"></span><span class="code-hl">Angela Ellen</span>
<span class="line-number"></span><span class="code-hl">Zoe Jane</span>
<span class="line-number"></span><span class="code-hl">Zoe Angela</span>
<span class="line-number"></span><span class="code-hl">Bella Angela</span>
<span class="line-number"></span><span class="code-hl">Miranda Angela</span>
</code></pre>
<blockquote>
<p><code>tsort</code> uses a simple way of defining each edge <code>A -> B</code> on its own line with the syntax: <code>A B</code>. The order of the lines does not matter.</p>
</blockquote>
<p>And here's the <code>tsort</code> output:</p>
<pre>
<div class="code-header">
<span>Shell</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-shell"><span class="line-number"></span><span class="code-hl">$ tsort < people.txt</span>
<span class="line-number"></span><span class="code-hl">Bella</span>
<span class="line-number"></span><span class="code-hl">Miranda</span>
<span class="line-number"></span><span class="code-hl">Zoe</span>
<span class="line-number"></span><span class="code-hl">Angela</span>
<span class="line-number"></span><span class="code-hl">Jane</span>
<span class="line-number"></span><span class="code-hl">Ellen</span>
</code></pre>
<p>The first 3 elements are the ones with no incoming edge, the Software Engineers, since no one reports to them. Then come their respective managers, Angela and Jane. Finally comes their manager, <code>Ellen</code>.</p>
<p>So to insert all those people in our <code>people</code> SQL table, we go through that list in reverse order: We can first insert <code>Ellen</code>, then <code>Jane</code>, etc, until we finally insert <code>Bella</code>.</p>
<p>Also, <code>tsort</code> detects cycles, for example if we add the line: <code>Ellen Zoe</code> at the end of <code>people.txt</code>, we get:</p>
<pre>
<div class="code-header">
<span>Shell</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-shell"><span class="line-number"></span><span class="code-hl">$ tsort < people.txt</span>
<span class="line-number"></span><span class="code-hl">Bella</span>
<span class="line-number"></span><span class="code-hl">Miranda</span>
<span class="line-number"></span><span class="code-hl">tsort: -: input contains a loop:</span>
<span class="line-number"></span><span class="code-hl">tsort: Jane</span>
<span class="line-number"></span><span class="code-hl">tsort: Ellen</span>
<span class="line-number"></span><span class="code-hl">tsort: Zoe</span>
<span class="line-number"></span><span class="code-hl">Jane</span>
<span class="line-number"></span><span class="code-hl">tsort: -: input contains a loop:</span>
<span class="line-number"></span><span class="code-hl">tsort: Angela</span>
<span class="line-number"></span><span class="code-hl">tsort: Ellen</span>
<span class="line-number"></span><span class="code-hl">tsort: Zoe</span>
<span class="line-number"></span><span class="code-hl">Angela</span>
<span class="line-number"></span><span class="code-hl">Ellen</span>
<span class="line-number"></span><span class="code-hl">Zoe</span>
</code></pre>
<p>So, how can we implement something like <code>tsort</code> for our problem at hand? That's where <a href="https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm">Kahn's algorithm</a> comes in to do exactly that: find cycles in the graph and output a topological sort.</p>
<p><em>Note that that's not the only solution and there are ways to detect cycles without creating a topological sort, but this algorithm seems relatively unknown and does not come up often on the Internet, so let's discover how it works and implement it. I promise, it's not complex.</em></p>
<h2 id="how-to-store-the-graph-in-memory">
<a class="title" href="#how-to-store-the-graph-in-memory">How to store the graph in memory</a>
<a class="hash-anchor" href="#how-to-store-the-graph-in-memory" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>There are many ways to do so, and Kahn's algorithm does not dictate which one to use.</p>
<p>We'll use an <a href="https://en.wikipedia.org/wiki/Adjacency_matrix">adjacency matrix</a>, because it's simple conceptually, maps well to Kahn's algorithm, and can be optimized if needed.</p>
<p>It's just a 2D square table of size <code>n x n</code> (where <code>n</code> is the number of nodes), where the cell at row <code>i</code> and column <code>j</code> is 1 if there is an edge from the node <code>i</code> to the node <code>j</code>, and otherwise, <code>0</code>.</p>
<p>The order of the nodes is arbitrary, I'll use the alphabetical order because again, it's simple to do:</p>
<pre>
<div class="code-header">
<span>Plaintext</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-plaintext"><span class="line-number"></span><span class="code-hl">Angela</span>
<span class="line-number"></span><span class="code-hl">Bella</span>
<span class="line-number"></span><span class="code-hl">Ellen</span>
<span class="line-number"></span><span class="code-hl">Jane</span>
<span class="line-number"></span><span class="code-hl">Miranda</span>
<span class="line-number"></span><span class="code-hl">Zoe</span>
</code></pre>
<p>Here, <code>Angela</code> is the node <code>0</code> and <code>Zoe</code> is the node <code>5</code>.</p>
<p>Since there is an edge from <code>Zoe</code> to <code>Angela</code>, i.e. from the node <code>5</code> to the node <code>0</code>, the cell at the position <code>(5, 0)</code> is set to <code>1</code>.</p>
<p>The full adjacency matrix for the employee graph in the example above looks like:</p>
<table>
<tbody>
<tr> <th></th> <th>Angela</th> <th>Bella</th> <th>Ellen</th> <th>Jane</th> <th>Miranda</th> <th>Zoe</th> </tr>
<tr> <td>Angela</td> <td>0</td> <td>0</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> </tr>
<tr> <td>Bella</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr>
<tr> <td>Ellen</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr>
<tr> <td>Jane</td> <td>0</td> <td>0</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> </tr>
<tr> <td>Miranda</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr>
<tr> <td>Zoe</td> <td>1</td> <td>0</td> <td>0</td> <td>1</td> <td>0</td> <td>0</td> </tr>
</tbody>
</table>
<p>The way to read this table is:</p>
<ul>
<li>For a given row, all the <code>1</code>'s indicate outgoing edges</li>
<li>For a given column, all the <code>1</code>'s indicate incoming edges</li>
<li>If there is a <code>1</code> on the diagonal, it means there is an edge going out of a node and going to the same node.</li>
</ul>
<p>There are a lot of zeroes in this table. Some may think this is horribly inefficient, which it is, but it really depends on number of nodes, i.e. the number of employees in the organization.
But note that this adjacency matrix is a concept, it shows what information is present, but not how it is stored.</p>
<p>For this article, we will store it the naive way, in a 2D array. Here are two optimization ideas I considered but have not had time to experiment with:</p>
<ul>
<li>Make this a bitarray. We are already only storing zeroes and ones, so it maps perfectly to this format.</li>
<li>Since there are a ton of zeroes (in the valid case, a regular employee's row only has one <code>1</code> and the CEO's row is only zeroes), it is very compressible. An easy way would be to use run-length encoding, meaning, instead of <code>0 0 0 0</code>, we just store the number of times the number occurs: <code>4 0</code>. Easy to implement, easy to understand. A row compresses to just a few bytes. And this size would be constant, whatever the size of the organization (i.e. number of employees) is.</li>
</ul>
<p>Wikipedia lists others if you are interested, it's a well-known problem.</p>
<p>Alright, now that we know how our graph is represented, on to the algorithm.</p>
<h2 id="kahn-s-algorithm">
<a class="title" href="#kahn-s-algorithm">Kahn's algorithm</a>
<a class="hash-anchor" href="#kahn-s-algorithm" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p><a href="https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm">Kahn's algorithm</a> keeps track of nodes with no incoming edge, and mutates the graph (in our case the adjacency matrix), by removing one edge at a time, until there are no more edges, and builds a list of nodes in the right order, which is the output.</p>
<p>Here's the pseudo-code:</p>
<pre>
<div class="code-header">
<span>Plaintext</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-plaintext"><span class="line-number"></span><span class="code-hl">L ← Empty list that will contain the sorted elements</span>
<span class="line-number"></span><span class="code-hl">S ← Set of all nodes with no incoming edge</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">while S is not empty do</span>
<span class="line-number"></span><span class="code-hl"> remove a node n from S</span>
<span class="line-number"></span><span class="code-hl"> add n to L</span>
<span class="line-number"></span><span class="code-hl"> for each node m with an edge e from n to m do</span>
<span class="line-number"></span><span class="code-hl"> remove edge e from the graph</span>
<span class="line-number"></span><span class="code-hl"> if m has no other incoming edges then</span>
<span class="line-number"></span><span class="code-hl"> insert m into S</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">if graph has edges then</span>
<span class="line-number"></span><span class="code-hl"> return error (graph has at least one cycle)</span>
<span class="line-number"></span><span class="code-hl">else </span>
<span class="line-number"></span><span class="code-hl"> return L (a topologically sorted order)</span>
</code></pre>
<p>And in plain English:</p>
<ul>
<li>Line 1: The result of this algorithm is the list of nodes in the desired order (topological). It starts empty, and we add nodes one-by one during the algorithm. We can simply use an array in our implementation.</li>
<li>Line 2: We first collect all nodes with no incoming edge. In terms of adjacency matrix, it means picking columns with only zeroes. The algorithm calls it a set, but we are free in our implementation to use whatever data structure we see fit. It just means a given node appears at most once in it. In our example, this set is: <code>[Zoe, Bella, Miranda]</code>. During the algorithm course, we will add further nodes to this set. Note that this is a working set, not the final result. Also, the order does not matter.</li>
<li>Line 4: Self-explanatory, we continue until the working set is empty and there is no more work to do.</li>
<li>Line 5: We first pick a node with no incoming edge (it does not matter which one). For example, <code>Zoe</code>, and remove it from <code>S</code>. <code>S</code> is now: <code>[Bella, Miranda]</code>.</li>
<li>Line 6: We add this node to the list of topologically sorted nodes, <code>L</code>. It now is: <code>[Zoe]</code>.</li>
<li>Line 7: We then inspect each node that <code>Zoe</code> has an edge to. That means <code>Jane</code> and <code>Angela</code>. In terms of adjacency matrix, we simply read <code>Zoe's</code> row, and inspect cells with a <code>1</code> in it.</li>
<li>Line 8: We remove such an edge, for example, <code>Zoe -> Jane</code>. In terms of adjacency matrix, it means setting the cell on the row <code>Zoe</code> and column <code>Jane</code> to <code>0</code>. At this point, the graph looks like this: <img src="kahns_algorithm_2.svg" alt="Employee hierarchy, step 1" /></li>
<li>Line 9: If <code>Jane</code> does not have another incoming edge, we add it to the set of all nodes with no incoming edge. That's the case here, so <code>S</code> now looks like: <code>[Bella, Miranda, Jane]</code>. We now loop to line 7 and handle the node <code>Angela</code> since <code>Jane</code> is taken care of.</li>
<li>Line 7-10: We are now handling the node <code>Angela</code>. We remove the edge <code>Zoe -> Angela</code>. We check whether the node <code>Angela</code> has incoming edges. It does, so we do <strong>not</strong> add it to <code>S</code>. The graph is now: <img src="kahns_algorithm_2_1.svg" alt="Employee hierarchy, step 2" /></li>
<li>We are now done with the line 7 for loop, so go back to line 5 and pick this time <code>Bella</code>. And so on. The graph would now, to the algorithm, look like: <img src="kahns_algorithm_2_2.svg" alt="Employee hierarchy, step 3" /></li>
</ul>
<hr />
<p>And here are the next steps in images:</p>
<ol>
<li><img src="kahns_algorithm_2_3.svg" alt="Employee hierarchy, step 4" /></li>
<li><img src="kahns_algorithm_2_4.svg" alt="Employee hierarchy, step 5" /></li>
<li><img src="kahns_algorithm_2_5.svg" alt="Employee hierarchy, step 6" /></li>
<li><img src="kahns_algorithm_2_6.svg" alt="Employee hierarchy, step 7" /></li>
<li><img src="kahns_algorithm_2_7.svg" alt="Employee hierarchy, step 8" /></li>
<li><img src="kahns_algorithm_2_8.svg" alt="Employee hierarchy, step 9" /></li>
<li><img src="kahns_algorithm_2_9.svg" alt="Employee hierarchy, step 10" /></li>
</ol>
<hr />
<ul>
<li>Line 12-15: Once the loop at line 4 is finished, we inspect our graph. If there are no more edges, we are done. If there is still an edge, it means there was a cycle in the graph, and we return an error.
Note that this algorithm is not capable by itself to point out which cycle there was exactly, only that there was one. That's because we mutated the graph by removing edges. If this information was important, we could keep track of which edges we removed in order, and re-add them back, or perhaps apply the algorithm to a copy of the graph (the adjacency matrix is trivial to clone).</li>
</ul>
<p>This algorithm is loose concerning the order of some operations, for example, picking a node with no incoming edge, or in which order the nodes in <code>S</code> are stored. That gives room for an implementation to use certain data structures or orders that are faster, but in some cases we want the order to be always the same to solve ties in the stable way and to be reproducible. In order to do that, we simply use the alphabetical order. So in our example above, at line 5, we picked <code>Zoe</code> out of <code>[Zoe, Bella, Miranda]</code>. Using this method, we would keep the working set <code>S</code> sorted alphabetically and pick <code>Bella</code> out of <code>[Bella, Miranda, Zoe]</code>.</p>
<h2 id="implementation">
<a class="title" href="#implementation">Implementation</a>
<a class="hash-anchor" href="#implementation" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>I implemented this at the time in Go, but I will use for this article the lingua franca of the 2010s, JavaScript.</p>
<p><em>I don't write JavaScript these days, I stopped many years ago, so apologies in advance if I am not using all the bells and whistles of 'Modern JavaScript', or if the code is not quite idiomatic.</em></p>
<p>First, we define our adjacency matrix and the list of nodes. This is the naive format. We would get the nodes and edges in some format, for example JSON, in the API, and build the adjacency matrix, which is trivial. Let's take the very first example, the (valid) tree of employees:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">const adjacencyMatrix = [</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 1, 0, 0],</span>
<span class="line-number"></span><span class="code-hl">];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">const nodes = ["Angela", "Bella", "Ellen", "Jane", "Miranda", "Zoe"];</span>
</code></pre>
<h3 id="helpers">
<a class="title" href="#helpers">Helpers</a>
<a class="hash-anchor" href="#helpers" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>We need a helper function to check if a node has no incoming edge (line 9 in the algorithm):</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">function hasNodeNoIncomingEdge(adjacencyMatrix, nodeIndex) {</span>
<span class="line-number"></span><span class="code-hl"> const column = nodeIndex;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> for (let row = 0; row < adjacencyMatrix.length; row += 1) {</span>
<span class="line-number"></span><span class="code-hl"> const cell = adjacencyMatrix[row][column];</span>
<span class="line-number"></span><span class="code-hl"> if (cell != 0) {</span>
<span class="line-number"></span><span class="code-hl"> return false;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return true;</span>
<span class="line-number"></span><span class="code-hl">}</span>
</code></pre>
<p>Then, using this helper, we can define a second helper to initially collect all the nodes with no incoming edge (line 2 in the algorithm):</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">function getNodesWithNoIncomingEdge(adjacencyMatrix, nodes) {</span>
<span class="line-number"></span><span class="code-hl"> return nodes.filter((_, i) => hasNodeNoIncomingEdge(adjacencyMatrix, i));</span>
<span class="line-number"></span><span class="code-hl">}</span>
</code></pre>
<p>We can try it:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">console.log(getNodesWithNoIncomingEdge(adjacencyMatrix, nodes));</span>
</code></pre>
<p>And it outputs:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">[ 'Bella', 'Miranda', 'Zoe' ]</span>
</code></pre>
<p>We need one final helper, to determine if the graph has edges (line 12), which is straightforward:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">function graphHasEdges(adjacencyMatrix) {</span>
<span class="line-number"></span><span class="code-hl"> for (let row = 0; row < adjacencyMatrix.length; row += 1) {</span>
<span class="line-number"></span><span class="code-hl"> for (let column = 0; column < adjacencyMatrix.length; column += 1) {</span>
<span class="line-number"></span><span class="code-hl"> if (adjacencyMatrix[row][column] == 1) return true;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return false;</span>
<span class="line-number"></span><span class="code-hl">}</span>
</code></pre>
<h3 id="the-algorithm">
<a class="title" href="#the-algorithm">The algorithm</a>
<a class="hash-anchor" href="#the-algorithm" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>We are finally ready to implement the algorithm. It's a straightforward, line by line, translation of the pseudo-code:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">function topologicalSort(adjacencyMatrix) {</span>
<span class="line-number"></span><span class="code-hl"> const L = [];</span>
<span class="line-number"></span><span class="code-hl"> const S = getNodesWithNoIncomingEdge(adjacencyMatrix, nodes);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> while (S.length > 0) {</span>
<span class="line-number"></span><span class="code-hl"> const node = S.pop();</span>
<span class="line-number"></span><span class="code-hl"> L.push(node);</span>
<span class="line-number"></span><span class="code-hl"> const nodeIndex = nodes.indexOf(node);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> for (let mIndex = 0; mIndex < nodes.length; mIndex += 1) {</span>
<span class="line-number"></span><span class="code-hl"> const hasEdgeFromNtoM = adjacencyMatrix[nodeIndex][mIndex];</span>
<span class="line-number"></span><span class="code-hl"> if (!hasEdgeFromNtoM) continue;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> adjacencyMatrix[nodeIndex][mIndex] = 0;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> if (hasNodeNoIncomingEdge(adjacencyMatrix, mIndex)) {</span>
<span class="line-number"></span><span class="code-hl"> const m = nodes[mIndex];</span>
<span class="line-number"></span><span class="code-hl"> S.push(m);</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> if (graphHasEdges(adjacencyMatrix)) {</span>
<span class="line-number"></span><span class="code-hl"> throw new Error("Graph has at least one cycle");</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return L;</span>
<span class="line-number"></span><span class="code-hl">}</span>
</code></pre>
<p>Let's try it:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">console.log(topologicalSort(adjacencyMatrix, nodes));</span>
</code></pre>
<p>We get:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">[ 'Zoe', 'Jane', 'Miranda', 'Bella', 'Angela', 'Ellen' ]</span>
</code></pre>
<p>Interestingly, it is not the same order as <code>tsort</code>, but it is indeed a valid topological ordering. That's because there are ties between some nodes and we do not resolve those ties the exact same way <code>tsort</code> does.</p>
<p>But in our specific case, we just want a valid insertion order in the database, and so this is enough.</p>
<h3 id="inserting-entries-in-the-database">
<a class="title" href="#inserting-entries-in-the-database">Inserting entries in the database</a>
<a class="hash-anchor" href="#inserting-entries-in-the-database" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>Now, we can produce the SQL code to insert our entries. We operate on a clone of the adjacency matrix for convenience because we later need to know what is the outgoing edge for a given node.</p>
<p>We handle the special case of the root first, which is the last element, and then we go through the topologically sorted list of employees in reverse order, and insert each one. We use a one liner to get the manager id by name when inserting to avoid many round trips to the database:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">const employeesTopologicallySorted = topologicalSort(structuredClone(adjacencyMatrix), nodes)</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">const root = employeesTopologicallySorted[employeesTopologicallySorted.length - 1];</span>
<span class="line-number"></span><span class="code-hl">console.log(`INSERT INTO people VALUES("${root}", NULL)`);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">for (let i = employeesTopologicallySorted.length - 2; i >= 0; i -= 1) {</span>
<span class="line-number"></span><span class="code-hl"> const employee = employeesTopologicallySorted[i];</span>
<span class="line-number"></span><span class="code-hl"> const employeeIndex = nodes.indexOf(employee);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> const managerIndex = adjacencyMatrix[employeeIndex].indexOf(1);</span>
<span class="line-number"></span><span class="code-hl"> const manager = nodes[managerIndex];</span>
<span class="line-number"></span><span class="code-hl"> console.log(</span>
<span class="line-number"></span><span class="code-hl"> `INSERT INTO people SELECT "${employee}", rowid FROM people WHERE name = "${manager}" LIMIT 1;`,</span>
<span class="line-number"></span><span class="code-hl"> );</span>
<span class="line-number"></span><span class="code-hl">}</span>
</code></pre>
<p>Which outputs:</p>
<pre>
<div class="code-header">
<span>Sql</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-sql"><span class="line-number"></span><span class="code-hl">INSERT INTO people VALUES("Ellen", NULL);</span>
<span class="line-number"></span><span class="code-hl">INSERT INTO people SELECT "Angela", rowid FROM people WHERE name = "Ellen" LIMIT 1;</span>
<span class="line-number"></span><span class="code-hl">INSERT INTO people SELECT "Bella", rowid FROM people WHERE name = "Angela" LIMIT 1;</span>
<span class="line-number"></span><span class="code-hl">INSERT INTO people SELECT "Miranda", rowid FROM people WHERE name = "Angela" LIMIT 1;</span>
<span class="line-number"></span><span class="code-hl">INSERT INTO people SELECT "Jane", rowid FROM people WHERE name = "Ellen" LIMIT 1;</span>
<span class="line-number"></span><span class="code-hl">INSERT INTO people SELECT "Zoe", rowid FROM people WHERE name = "Jane" LIMIT 1;</span>
</code></pre>
<h3 id="detecting-cycles">
<a class="title" href="#detecting-cycles">Detecting cycles</a>
<a class="hash-anchor" href="#detecting-cycles" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>As we said earlier, we get that for free, so let's check our implementation against this invalid example:</p>
<p><img src="kahns_algorithm_4.svg" alt="Employee hierarchy with cycle" /></p>
<p>We add the edge <code>Ellen -> Zoe</code> to create a cycle:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">const adjacencyMatrix = [</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 0, 0, 1], // => We change the last element of this row (Ellen's row, Zoe's column) from 0 to 1.</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 1, 0, 0],</span>
<span class="line-number"></span><span class="code-hl">];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">const nodes = ["Angela", "Bella", "Ellen", "Jane", "Miranda", "Zoe"];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">const employeesTopologicallySorted = topologicalSort(structuredClone(adjacencyMatrix), nodes);</span>
</code></pre>
<p>And we get an error as expected:</p>
<pre>
<div class="code-header">
<span>Shell</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-shell"><span class="line-number"></span><span class="code-hl">/home/pg/my-code/blog/kahns_algorithm.js:63</span>
<span class="line-number"></span><span class="code-hl"> throw new Error("Graph has at least one cycle");</span>
<span class="line-number"></span><span class="code-hl"> ^</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">Error: Graph has at least one cycle</span>
</code></pre>
<h3 id="detecting-multiple-roots">
<a class="title" href="#detecting-multiple-roots">Detecting multiple roots</a>
<a class="hash-anchor" href="#detecting-multiple-roots" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>One thing that topological sorting does not do for us is to detect the case of multiple roots in the graph, for example:</p>
<p><img src="kahns_algorithm_3.svg" alt="Employee hierarchy with multiple roots" /></p>
<p>To do this, we simply scan the adjacency matrix and verify that there is only one row with only zeroes, that is, only one node that has no outgoing edges:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">function hasMultipleRoots(adjacencyMatrix) {</span>
<span class="line-number"></span><span class="code-hl"> let countOfRowsWithOnlyZeroes = 0;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> for (let row = 0; row < adjacencyMatrix.length; row += 1) {</span>
<span class="line-number"></span><span class="code-hl"> let rowHasOnlyZeroes = true;</span>
<span class="line-number"></span><span class="code-hl"> for (let column = 0; column < adjacencyMatrix.length; column += 1) {</span>
<span class="line-number"></span><span class="code-hl"> if (adjacencyMatrix[row][column] != 0) {</span>
<span class="line-number"></span><span class="code-hl"> rowHasOnlyZeroes = false;</span>
<span class="line-number"></span><span class="code-hl"> break;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> if (rowHasOnlyZeroes) countOfRowsWithOnlyZeroes += 1;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return countOfRowsWithOnlyZeroes > 1;</span>
<span class="line-number"></span><span class="code-hl">}</span>
</code></pre>
<p>Let's try it with our invalid example from above:</p>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">const adjacencyMatrix = [</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 1, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl">];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">const nodes = ["Angela", "Bella", "Ellen", "Jane", "Miranda", "Zoe", "Kelly"];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">console.log(hasMultipleRoots(adjacencyMatrix));</span>
</code></pre>
<p>And we get: <code>true</code>. With our previous (valid) example, we get: <code>false</code>.</p>
<h2 id="playing-with-the-database">
<a class="title" href="#playing-with-the-database">Playing with the database</a>
<a class="hash-anchor" href="#playing-with-the-database" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>We can query each employee along with their manager name so:</p>
<pre>
<div class="code-header">
<span>Sql</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-sql"><span class="line-number"></span><span class="code-hl">SELECT a.name as employee_name, COALESCE(b.name, '') as manager_name FROM people a LEFT JOIN people b ON a.manager = b.rowid;</span>
</code></pre>
<p>To query the manager (N+1) and the manager's manager (N+2) of an employee:</p>
<pre>
<div class="code-header">
<span>Sql</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-sql"><span class="line-number"></span><span class="code-hl">SELECT COALESCE(n_plus_1.name, ''), COALESCE(n_plus_2.name, '')</span>
<span class="line-number"></span><span class="code-hl">FROM people employee</span>
<span class="line-number"></span><span class="code-hl">LEFT JOIN people n_plus_1 ON employee.manager = n_plus_1.rowid</span>
<span class="line-number"></span><span class="code-hl">LEFT JOIN people n_plus_2 ON n_plus_1.manager = n_plus_2.rowid</span>
<span class="line-number"></span><span class="code-hl">WHERE employee.name = ?</span>
</code></pre>
<p>We can also do this with hairy recursive Common Table Expression (CTE) but I'll leave that to the reader.</p>
<h2 id="closing-thoughts">
<a class="title" href="#closing-thoughts">Closing thoughts</a>
<a class="hash-anchor" href="#closing-thoughts" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>Graphs and algorithms operating on them do not have to be complicated. Using an adjacency matrix and Kahn's algorithm, we can achieve a lot with little and it remains simple.</p>
<p>There are many ways to optimize the code in this article; the point was not to write the most efficient code, but to showcase in the clearest, simplest way possible to detect cycles and store a graph/tree in memory and in a database.</p>
<p>If you want to play with the code here and try to make it faster, go at it!</p>
<h2 id="addendum-the-full-code">
<a class="title" href="#addendum-the-full-code">Addendum: the full code</a>
<a class="hash-anchor" href="#addendum-the-full-code" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<details>
<summary>The full code</summary>
<pre>
<div class="code-header">
<span>Javascript</span>
<button class="copy-code" type="button"><svg aria-hidden="true" focusable="false" class="octicon octicon-copy" viewBox="0 0 16 16" width="16" height="16" fill="currentColor" display="inline-block" overflow="visible" style="vertical-align: text-bottom;"><path d="M0 6.75C0 5.784.784 5 1.75 5h1.5a.75.75 0 0 1 0 1.5h-1.5a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-1.5a.75.75 0 0 1 1.5 0v1.5A1.75 1.75 0 0 1 9.25 16h-7.5A1.75 1.75 0 0 1 0 14.25Z"></path><path d="M5 1.75C5 .784 5.784 0 6.75 0h7.5C15.216 0 16 .784 16 1.75v7.5A1.75 1.75 0 0 1 14.25 11h-7.5A1.75 1.75 0 0 1 5 9.25Zm1.75-.25a.25.25 0 0 0-.25.25v7.5c0 .138.112.25.25.25h7.5a.25.25 0 0 0 .25-.25v-7.5a.25.25 0 0 0-.25-.25Z"></path></svg></button>
</div>
<code class="language-javascript"><span class="line-number"></span><span class="code-hl">const adjacencyMatrix = [</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 1, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [1, 0, 0, 0, 0, 0],</span>
<span class="line-number"></span><span class="code-hl"> [0, 0, 0, 1, 0, 0],</span>
<span class="line-number"></span><span class="code-hl">];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">const nodes = ["Angela", "Bella", "Ellen", "Jane", "Miranda", "Zoe"];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">function hasNodeNoIncomingEdge(adjacencyMatrix, nodeIndex) {</span>
<span class="line-number"></span><span class="code-hl"> const column = nodeIndex;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> for (let row = 0; row < adjacencyMatrix.length; row += 1) {</span>
<span class="line-number"></span><span class="code-hl"> const cell = adjacencyMatrix[row][column];</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> if (cell != 0) {</span>
<span class="line-number"></span><span class="code-hl"> return false;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return true;</span>
<span class="line-number"></span><span class="code-hl">}</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">function getNodesWithNoIncomingEdge(adjacencyMatrix, nodes) {</span>
<span class="line-number"></span><span class="code-hl"> return nodes.filter((_, i) => hasNodeNoIncomingEdge(adjacencyMatrix, i));</span>
<span class="line-number"></span><span class="code-hl">}</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">function graphHasEdges(adjacencyMatrix) {</span>
<span class="line-number"></span><span class="code-hl"> for (let row = 0; row < adjacencyMatrix.length; row += 1) {</span>
<span class="line-number"></span><span class="code-hl"> for (let column = 0; column < adjacencyMatrix.length; column += 1) {</span>
<span class="line-number"></span><span class="code-hl"> if (adjacencyMatrix[row][column] == 1) return true;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return false;</span>
<span class="line-number"></span><span class="code-hl">}</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">function topologicalSort(adjacencyMatrix) {</span>
<span class="line-number"></span><span class="code-hl"> const L = [];</span>
<span class="line-number"></span><span class="code-hl"> const S = getNodesWithNoIncomingEdge(adjacencyMatrix, nodes);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> while (S.length > 0) {</span>
<span class="line-number"></span><span class="code-hl"> const node = S.pop();</span>
<span class="line-number"></span><span class="code-hl"> L.push(node);</span>
<span class="line-number"></span><span class="code-hl"> const nodeIndex = nodes.indexOf(node);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> for (let mIndex = 0; mIndex < nodes.length; mIndex += 1) {</span>
<span class="line-number"></span><span class="code-hl"> const hasEdgeFromNtoM = adjacencyMatrix[nodeIndex][mIndex];</span>
<span class="line-number"></span><span class="code-hl"> if (!hasEdgeFromNtoM) continue;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> adjacencyMatrix[nodeIndex][mIndex] = 0;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> if (hasNodeNoIncomingEdge(adjacencyMatrix, mIndex)) {</span>
<span class="line-number"></span><span class="code-hl"> const m = nodes[mIndex];</span>
<span class="line-number"></span><span class="code-hl"> S.push(m);</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> if (graphHasEdges(adjacencyMatrix)) {</span>
<span class="line-number"></span><span class="code-hl"> throw new Error("Graph has at least one cycle");</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return L;</span>
<span class="line-number"></span><span class="code-hl">}</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">function hasMultipleRoots(adjacencyMatrix) {</span>
<span class="line-number"></span><span class="code-hl"> let countOfRowsWithOnlyZeroes = 0;</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> for (let row = 0; row < adjacencyMatrix.length; row += 1) {</span>
<span class="line-number"></span><span class="code-hl"> let rowHasOnlyZeroes = true;</span>
<span class="line-number"></span><span class="code-hl"> for (let column = 0; column < adjacencyMatrix.length; column += 1) {</span>
<span class="line-number"></span><span class="code-hl"> if (adjacencyMatrix[row][column] != 0) {</span>
<span class="line-number"></span><span class="code-hl"> rowHasOnlyZeroes = false;</span>
<span class="line-number"></span><span class="code-hl"> break;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"> if (rowHasOnlyZeroes) countOfRowsWithOnlyZeroes += 1;</span>
<span class="line-number"></span><span class="code-hl"> }</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> return countOfRowsWithOnlyZeroes > 1;</span>
<span class="line-number"></span><span class="code-hl">}</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">console.log(hasMultipleRoots(adjacencyMatrix));</span>
<span class="line-number"></span><span class="code-hl">const employeesTopologicallySorted = topologicalSort(structuredClone(adjacencyMatrix), nodes);</span>
<span class="line-number"></span><span class="code-hl">console.log(employeesTopologicallySorted);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">const root = employeesTopologicallySorted[employeesTopologicallySorted.length - 1];</span>
<span class="line-number"></span><span class="code-hl">console.log(`INSERT INTO people VALUES("${root}", NULL)`);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl">for (let i = employeesTopologicallySorted.length - 2; i >= 0; i -= 1) {</span>
<span class="line-number"></span><span class="code-hl"> const employee = employeesTopologicallySorted[i];</span>
<span class="line-number"></span><span class="code-hl"> const employeeIndex = nodes.indexOf(employee);</span>
<span class="line-number"></span><span class="code-hl"></span>
<span class="line-number"></span><span class="code-hl"> const managerIndex = adjacencyMatrix[employeeIndex].indexOf(1);</span>
<span class="line-number"></span><span class="code-hl"> const manager = nodes[managerIndex];</span>
<span class="line-number"></span><span class="code-hl"> console.log(</span>
<span class="line-number"></span><span class="code-hl"> `INSERT INTO people SELECT "${employee}", rowid FROM people WHERE name = "${manager}" LIMIT 1;`,</span>
<span class="line-number"></span><span class="code-hl"> );</span>
<span class="line-number"></span><span class="code-hl">}</span>
</code></pre>
</details>
<p><a href="/blog"> ⏴ Back to all articles</a></p>
<div id="donate">
<em>
<p>If you enjoy what you're reading, you want to support me, and can afford it: <a href="https://paypal.me/philigaultier?country.x=DE&locale.x=en_US">Support me</a>. That allows me to write more cool articles!</p>
<p>
This blog is <a href="https://github.com/gaultier/blog">open-source</a>!
If you find a problem, please open a Github issue.
The content of this blog as well as the code snippets are under the <a href="https://en.wikipedia.org/wiki/BSD_licenses#3-clause_license_(%22BSD_License_2.0%22,_%22Revised_BSD_License%22,_%22New_BSD_License%22,_or_%22Modified_BSD_License%22)">BSD-3 License</a> which I also usually use for all my personal projects. It's basically free for every use but you have to mention me as the original author.
</p>
</em>
</div>
</div>
</body>
</html>