Sha256: 83efa360fd7f528c33837163fc4f4aaabea90001efd5289a086ac1b488e42248
Contents?: true
Size: 1.16 KB
Versions: 26
Compression:
Stored size: 1.16 KB
Contents
const PERMANENT_MARKER = 2
const TEMPORARY_MARKER = 1
function createError(node, graph) {
const er = new Error("Nondeterministic import's order")
const related = graph[node]
const relatedNode = related.find(
relatedNode => 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
const children = graph[node]
const length = children.length
for (let i = 0; i < length; ++i) {
const 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) {
const result = []
const state = {}
const nodes = Object.keys(graph)
const length = nodes.length
for (let i = 0; i < length; ++i) {
const er = walkGraph(nodes[i], graph, state, result, strict)
if (er instanceof Error) return er
}
return result
}
module.exports = topologicalSort
Version data entries
26 entries across 25 versions & 8 rubygems