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
57
58
59
60
61
62
63
64
65
66
67
68
69
|
/**
* Topological sorting function
*
* @param {Array} edges
* @returns {Array}
*/
module.exports = function(edges){
return toposort(uniqueNodes(edges), edges)
}
module.exports.array = toposort
function toposort(nodes, edges) {
var cursor = nodes.length
, sorted = new Array(cursor)
, visited = {}
, i = cursor
while (i--) {
if (!visited[i]) visit(nodes[i], i, [])
}
return sorted
function visit(node, i, predecessors) {
if(predecessors.indexOf(node) >= 0) {
var nodeRep
try {
nodeRep = ", node was:" + JSON.stringify(node)
} catch(e) {
nodeRep = ""
}
throw new Error('Cyclic dependency' + nodeRep)
}
if (!~nodes.indexOf(node)) {
throw new Error('Found unknown node. Make sure to provided all involved nodes. Unknown node: '+JSON.stringify(node))
}
if (visited[i]) return;
visited[i] = true
// outgoing edges
var outgoing = edges.filter(function(edge){
return edge[0] === node
})
if (i = outgoing.length) {
var preds = predecessors.concat(node)
do {
var child = outgoing[--i][1]
visit(child, nodes.indexOf(child), preds)
} while (i)
}
sorted[--cursor] = node
}
}
function uniqueNodes(arr){
var res = []
for (var i = 0, len = arr.length; i < len; i++) {
var edge = arr[i]
if (res.indexOf(edge[0]) < 0) res.push(edge[0])
if (res.indexOf(edge[1]) < 0) res.push(edge[1])
}
return res
}
|
