1 | const PERMANENT_MARKER = 2;
|
---|
2 | const TEMPORARY_MARKER = 1;
|
---|
3 |
|
---|
4 | function createError(node, graph) {
|
---|
5 | const er = new Error("Nondeterministic import's order");
|
---|
6 |
|
---|
7 | const related = graph[node];
|
---|
8 | const relatedNode = related.find(
|
---|
9 | (relatedNode) => graph[relatedNode].indexOf(node) > -1
|
---|
10 | );
|
---|
11 |
|
---|
12 | er.nodes = [node, relatedNode];
|
---|
13 |
|
---|
14 | return er;
|
---|
15 | }
|
---|
16 |
|
---|
17 | function walkGraph(node, graph, state, result, strict) {
|
---|
18 | if (state[node] === PERMANENT_MARKER) {
|
---|
19 | return;
|
---|
20 | }
|
---|
21 |
|
---|
22 | if (state[node] === TEMPORARY_MARKER) {
|
---|
23 | if (strict) {
|
---|
24 | return createError(node, graph);
|
---|
25 | }
|
---|
26 |
|
---|
27 | return;
|
---|
28 | }
|
---|
29 |
|
---|
30 | state[node] = TEMPORARY_MARKER;
|
---|
31 |
|
---|
32 | const children = graph[node];
|
---|
33 | const length = children.length;
|
---|
34 |
|
---|
35 | for (let i = 0; i < length; ++i) {
|
---|
36 | const error = walkGraph(children[i], graph, state, result, strict);
|
---|
37 |
|
---|
38 | if (error instanceof Error) {
|
---|
39 | return error;
|
---|
40 | }
|
---|
41 | }
|
---|
42 |
|
---|
43 | state[node] = PERMANENT_MARKER;
|
---|
44 |
|
---|
45 | result.push(node);
|
---|
46 | }
|
---|
47 |
|
---|
48 | function topologicalSort(graph, strict) {
|
---|
49 | const result = [];
|
---|
50 | const state = {};
|
---|
51 |
|
---|
52 | const nodes = Object.keys(graph);
|
---|
53 | const length = nodes.length;
|
---|
54 |
|
---|
55 | for (let i = 0; i < length; ++i) {
|
---|
56 | const er = walkGraph(nodes[i], graph, state, result, strict);
|
---|
57 |
|
---|
58 | if (er instanceof Error) {
|
---|
59 | return er;
|
---|
60 | }
|
---|
61 | }
|
---|
62 |
|
---|
63 | return result;
|
---|
64 | }
|
---|
65 |
|
---|
66 | module.exports = topologicalSort;
|
---|