Skip to content

Instantly share code, notes, and snippets.

@zerobias
Created March 21, 2021 14:14
Show Gist options
  • Save zerobias/6d04ae36c56b0100aac58556ada4174a to your computer and use it in GitHub Desktop.
Save zerobias/6d04ae36c56b0100aac58556ada4174a to your computer and use it in GitHub Desktop.
Topological sorting
export function toposort(
rawGraph: Record<string, string[]>,
ignore?: Set<string>
) {
const graph = {} as Record<string, string[]>
for (const id in rawGraph) {
graph[id] = [...new Set(rawGraph[id])]
}
const result = [] as string[]
const visited = {} as Record<string, boolean>
const temp = {} as Record<string, boolean>
for (const node in graph) {
if (!visited[node] && !temp[node]) {
topologicalSortHelper(node)
}
}
result.reverse()
if (ignore && ignore.size > 0) {
const processed = [] as string[]
const ignored = [...ignore]
let item: string | void
while ((item = ignored.shift())) {
processed.push(item)
graph[item].forEach(child => {
if (processed.includes(child) || ignored.includes(child)) return
ignored.push(child)
})
}
processed.forEach(item => {
const pos = result.indexOf(item)
if (pos !== -1) {
result.splice(pos, 1)
}
})
}
return result
function topologicalSortHelper(node: string) {
temp[node] = true
const neighbors = graph[node]
for (let i = 0; i < neighbors.length; i++) {
const n = neighbors[i]
if (temp[n]) {
// continue
throw Error('found cycle in DAG')
}
if (!visited[n]) {
topologicalSortHelper(n)
}
}
temp[node] = false
visited[node] = true
result.push(node)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment