AI: Independence from the graph

Decide independence without a single number, just by reading the graph.

What to build

A program that decides whether two variables are d-separated by a set of observed variables.

Requirements

  • The network is given by its arrows. A path between X and Y is active if every node on it is either a non-collider that is not observed, or a collider (both arrows point into it) that is observed or has an observed descendant. X and Y are independent given the evidence exactly when no path is active.
  • Print independent or dependent.

Input

Line 1: e. Then e arrows A B (A → B). Last line: X Y or X Y | Z….

Output

One line.

Constraints

At most 30 nodes; the graph has no cycles; X and Y are not observed.

Example

Input:

4
C S
C R
S W
R W
S R

Output:

dependent

Why it works

Information flows along a path through causes and effects unless an observed middle node blocks it, while a common effect connects its causes only once it, or something it causes, is observed.

Examples

Example 1 · Input
4
C S
C R
S W
R W
S R
Expected output
dependent
Example 2 · Input
4
C S
C R
S W
R W
S R | C
Expected output
independent

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Search over (node, direction) pairs: arriving from a child (going up) or from a parent (going down), as in the Bayes-ball algorithm.

Hint 2

A collider passes the search only if it or one of its descendants is observed; any other node passes only if it is not observed.

Solution

Show one correct solution (try it yourself first)
from collections import deque

parents, children = {}, {}
for _ in range(int(input())):
    a, b = input().split()
    children.setdefault(a, []).append(b)
    parents.setdefault(b, []).append(a)
    children.setdefault(b, [])
    parents.setdefault(a, [])
pair, _, rest = input().partition("|")
x, y = pair.split()
observed = set(rest.split())

# nodes that are observed or have an observed descendant
opens_collider = set()
todo = list(observed)
while todo:
    node = todo.pop()
    if node not in opens_collider:
        opens_collider.add(node)
        todo.extend(parents.get(node, []))

seen = set()
queue = deque([(x, "up")])
reached = set()
while queue:
    node, direction = queue.popleft()
    if (node, direction) in seen:
        continue
    seen.add((node, direction))
    if node not in observed:
        reached.add(node)
    if direction == "up" and node not in observed:
        queue.extend((p, "up") for p in parents.get(node, []))
        queue.extend((c, "down") for c in children.get(node, []))
    elif direction == "down":
        if node not in observed:
            queue.extend((c, "down") for c in children.get(node, []))
        if node in opens_collider:
            queue.extend((p, "up") for p in parents.get(node, []))
print("dependent" if y in reached else "independent")

Lesson: Bayesian networks →