blob: c9897e7187974afd19c6485a1f60da37059876b6 [file] [log] [blame]
/**
* 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
}