§ Immediate dominator in a DAG

def idom(dag : Dict[int, int], sink : int) -> int:  node2parents, time2node = toposort(dat)  frontier = set([sink])  seen = set (frontier)  time = n-1  while len(frontier) != 1:    w = time2node[time]    # Node is not in the frontier.    if w not in frontier: continue    # Node is in the frontier, expand it.    del frontier[w]    # add the nodes that we have not seen.    # but do we even care?    wps = [p for p not in seen for p in node2parents[w]]    seen.add(wps)    frontier.add(wps)  assert len(frontier) == 1  return list(frontier)[0]  # Unreachable, since at the end, we will reach a state where we have