1 | // Copyright (c) Jupyter Development Team.
|
2 | // Distributed under the terms of the Modified BSD License.
|
3 | /*-----------------------------------------------------------------------------
|
4 | | Copyright (c) 2014-2017, PhosphorJS Contributors
|
5 | |
|
6 | | Distributed under the terms of the BSD 3-Clause License.
|
7 | |
|
8 | | The full license is in the file LICENSE, distributed with this software.
|
9 | |----------------------------------------------------------------------------*/
|
10 |
|
11 | /**
|
12 | * Topologically sort an iterable of edges.
|
13 | *
|
14 | * @param edges - The iterable object of edges to sort.
|
15 | * An edge is represented as a 2-tuple of `[fromNode, toNode]`.
|
16 | *
|
17 | * @returns The topologically sorted array of nodes.
|
18 | *
|
19 | * #### Notes
|
20 | * If a cycle is present in the graph, the cycle will be ignored and
|
21 | * the return value will be only approximately sorted.
|
22 | *
|
23 | * #### Example
|
24 | * ```typescript
|
25 | * import { topologicSort } from '@lumino/algorithm';
|
26 | *
|
27 | * let data = [
|
28 | * ['d', 'e'],
|
29 | * ['c', 'd'],
|
30 | * ['a', 'b'],
|
31 | * ['b', 'c']
|
32 | * ];
|
33 | *
|
34 | * topologicSort(data); // ['a', 'b', 'c', 'd', 'e']
|
35 | * ```
|
36 | */
|
37 | export function topologicSort<T>(edges: Iterable<[T, T]>): T[] {
|
38 | // Setup the shared sorting state.
|
39 | let sorted: T[] = [];
|
40 | let visited = new Set<T>();
|
41 | let graph = new Map<T, T[]>();
|
42 |
|
43 | // Add the edges to the graph.
|
44 | for (const edge of edges) {
|
45 | addEdge(edge);
|
46 | }
|
47 |
|
48 | // Visit each node in the graph.
|
49 | for (const [k] of graph) {
|
50 | visit(k);
|
51 | }
|
52 |
|
53 | // Return the sorted results.
|
54 | return sorted;
|
55 |
|
56 | // Add an edge to the graph.
|
57 | function addEdge(edge: [T, T]): void {
|
58 | let [fromNode, toNode] = edge;
|
59 | let children = graph.get(toNode);
|
60 | if (children) {
|
61 | children.push(fromNode);
|
62 | } else {
|
63 | graph.set(toNode, [fromNode]);
|
64 | }
|
65 | }
|
66 |
|
67 | // Recursively visit the node.
|
68 | function visit(node: T): void {
|
69 | if (visited.has(node)) {
|
70 | return;
|
71 | }
|
72 | visited.add(node);
|
73 | let children = graph.get(node);
|
74 | if (children) {
|
75 | for (const child of children) {
|
76 | visit(child);
|
77 | }
|
78 | }
|
79 | sorted.push(node);
|
80 | }
|
81 | }
|