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 | import { each, IterableOrArrayLike } from './iter';
|
11 |
|
12 | /**
|
13 | * Topologically sort an iterable of edges.
|
14 | *
|
15 | * @param edges - The iterable or array-like object of edges to sort.
|
16 | * An edge is represented as a 2-tuple of `[fromNode, toNode]`.
|
17 | *
|
18 | * @returns The topologically sorted array of nodes.
|
19 | *
|
20 | * #### Notes
|
21 | * If a cycle is present in the graph, the cycle will be ignored and
|
22 | * the return value will be only approximately sorted.
|
23 | *
|
24 | * #### Example
|
25 | * ```typescript
|
26 | * import { topologicSort } from '@lumino/algorithm';
|
27 | *
|
28 | * let data = [
|
29 | * ['d', 'e'],
|
30 | * ['c', 'd'],
|
31 | * ['a', 'b'],
|
32 | * ['b', 'c']
|
33 | * ];
|
34 | *
|
35 | * topologicSort(data); // ['a', 'b', 'c', 'd', 'e']
|
36 | * ```
|
37 | */
|
38 | export function topologicSort<T>(edges: IterableOrArrayLike<[T, T]>): T[] {
|
39 | // Setup the shared sorting state.
|
40 | let sorted: T[] = [];
|
41 | let visited = new Set<T>();
|
42 | let graph = new Map<T, T[]>();
|
43 |
|
44 | // Add the edges to the graph.
|
45 | each(edges, addEdge);
|
46 |
|
47 | // Visit each node in the graph.
|
48 | graph.forEach((v, k) => {
|
49 | visit(k);
|
50 | });
|
51 |
|
52 | // Return the sorted results.
|
53 | return sorted;
|
54 |
|
55 | // Add an edge to the graph.
|
56 | function addEdge(edge: [T, T]): void {
|
57 | let [fromNode, toNode] = edge;
|
58 | let children = graph.get(toNode);
|
59 | if (children) {
|
60 | children.push(fromNode);
|
61 | } else {
|
62 | graph.set(toNode, [fromNode]);
|
63 | }
|
64 | }
|
65 |
|
66 | // Recursively visit the node.
|
67 | function visit(node: T): void {
|
68 | if (visited.has(node)) {
|
69 | return;
|
70 | }
|
71 | visited.add(node);
|
72 | let children = graph.get(node);
|
73 | if (children) {
|
74 | children.forEach(visit);
|
75 | }
|
76 | sorted.push(node);
|
77 | }
|
78 | }
|