[6a3a178] | 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;
|
---|