Topological sorting

toposort.ts

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)
  }
}