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
|
"use strict";
var PERMANENT_MARKER = 2;
var TEMPORARY_MARKER = 1;
function createError(node, graph) {
var er = new Error("Nondeterministic import's order");
var related = graph[node];
var relatedNode = related.find(function (relatedNode) {
return graph[relatedNode].indexOf(node) > -1;
});
er.nodes = [node, relatedNode];
return er;
}
function walkGraph(node, graph, state, result, strict) {
if (state[node] === PERMANENT_MARKER) return;
if (state[node] === TEMPORARY_MARKER) {
if (strict) return createError(node, graph);
return;
}
state[node] = TEMPORARY_MARKER;
var children = graph[node];
var length = children.length;
for (var i = 0; i < length; ++i) {
var er = walkGraph(children[i], graph, state, result, strict);
if (er instanceof Error) return er;
}
state[node] = PERMANENT_MARKER;
result.push(node);
}
function topologicalSort(graph, strict) {
var result = [];
var state = {};
var nodes = Object.keys(graph);
var length = nodes.length;
for (var i = 0; i < length; ++i) {
var er = walkGraph(nodes[i], graph, state, result, strict);
if (er instanceof Error) return er;
}
return result;
}
module.exports = topologicalSort;
|
