Dominator Tree Immediate Dominator

Problem

Compute immediate dominators for a small directed graph.

n is the node count, edges is a list of [from, to], and start is the entry node. The immediate dominator of a node is the last node through which every path from start must pass. Use the iterative Cooper algorithm with preorder numbers.

Return the idom array, where the start maps to itself and unreachable nodes map to -1.

Hint

Intersect dominator candidates by walking the one with the larger preorder number upward.

Test cases

case 1

in: [4,[[0,1],[1,2],[0,2],[2,3]],0]

expected: [0,0,0,2]

case 2

in: [3,[[0,1],[1,2]],0]

expected: [0,0,1]

case 3

in: [4,[[0,1],[2,3]],0]

expected: [0,0,-1,-1]

case 4

in: [1,[],0]

expected: [0]

Starter codePython

def immediate_dominators(n, edges, start):
    # Your code here
    pass

4 test cases · run your code against them in the editor