D-Separation Check

Problem

Check whether nodes x and y are d-separated given the set of observed nodes. Build the ancestral graph of x, y and given, moralize it, remove the observed nodes, and test whether x can still reach y along an undirected path. Return True when they are d-separated and False otherwise, including when a node index is invalid.

Hint

Moralization plus ancestral graph reduction turns d-separation into ordinary graph reachability.

Test cases

case 1

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

expected: false

case 2

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

expected: true

case 3

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

expected: true

case 4

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

expected: false

case 5

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

expected: false

Starter codePython

def d_separation_check(num_nodes, edges, x, y, given):
    # Your code here
    pass

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