"""Wasserman (2004), Chapter 17: Directed Graphs and Conditional Independence.

Companion code for Chapter 17 of L. Wasserman, All of Statistics: A Concise Course in Statistical
Inference (Springer, 2004), pp. 263-279, written from scratch with numpy, scipy and matplotlib. The
functions are short and meant to be read next to the lecture notes (../ch17-directed-graphs.html).
A DAG is a dict that maps each node to the list of its parents, in a fixed node order.

* Section 17.2, conditional independence: joint tables of discrete variables, marginals and the exact
  conditional mutual information (cond_mi), which is zero exactly when a conditional independence holds.
* Section 17.3, DAG vocabulary: children, ancestors, descendants, a topological order, acyclicity,
  skeletons and unshielded colliders (v_structures).
* Section 17.4, probability and DAGs: the joint table of a distribution Markov to a DAG from its
  conditional probability tables (joint_from_cpts), random tables (random_cpts) and the local Markov
  statements of Theorem 17.6 (local_markov).
* Section 17.5, d-separation: by the reachability ("Bayes ball") search (d_separated, which also
  returns the order in which states are visited) and, as a cross-check, by listing every undirected
  path and testing the book's definition literally (d_separated_paths); the set I(G) of all
  d-separation statements (independence_statements); Markov equivalence (equivalence_key,
  all_dags, equivalence_classes, essential_graph), covered edges and Chickering's sequence of
  covered-edge reversals between two equivalent DAGs (covered_reversal_path); Robinson's count of DAGs.
* Section 17.6, estimation: maximum likelihood for a discrete DAG is counting (fit_discrete_dag),
  log-likelihood, AIC and BIC of every DAG on a few nodes from one table of counts (family_scores,
  dag_scores), and the bootstrap of Exercise 17.6.
* Section 17.8 (appendix), interventions: the truncated factorisation f*(v) = f(v) / f(x | pi_x)
  for "set X = x" (intervene), conditioning against intervening in the binary model of Exercise 17.8
  (binary_scm_exact, binary_scm_sim), the Gaussian structural equations of Exercise 17.9
  (gauss_scm_moments) and the correspondence with counterfactuals.
* JSRandom and js_uniforms: the seeded generator of the browser demonstrations (DK.rng in
  courses/demo-kit.js), so that the simulations of the three demos are reproduced here number for number
  (demo_intervention, demo_equivalence, demo_reachability).

Figures. All twelve figures of the chapter are graph diagrams. They are redrawn here (draw_dag), and
where the book draws a graph to make a point about independence the point is computed and printed on
the figure: the Markov statements of Figures 17.3 to 17.5 are produced by local_markov, the verdicts on
Figures 17.6 to 17.8 and 17.12 by d_separated, the probabilities on Figure 17.9 by exact summation, and
Figures 17.10 and 17.11 show the graphs before and after an intervention. Nothing is skipped.
Six supplementary figures illustrate the gaps filled in the notes:
  17.S1 conditioning against intervening by simulation (Exercise 17.8);
  17.S2 the Gaussian structural equation model and the correlation fallacy (Exercise 17.9);
  17.S3 maximum likelihood and bootstrap intervals for a discrete DAG (Exercise 17.6);
  17.S4 a distribution that is Markov but not faithful to its DAG (path cancellation);
  17.S5 structure learning: equivalent DAGs tie, and the right class needs data (Section 17.6);
  17.S6 the number of DAGs and of Markov equivalence classes (Section 17.6).
Run `python3 ch17_directed_graphs.py --list`, `python3 ch17_directed_graphs.py` (all eighteen
figures, under a minute on one CPU thread) or `python3 ch17_directed_graphs.py --fig 17.8`.
Files go to ../img/ch17/. The demonstrations compute everything in the browser and need no data files.
"""
import itertools
import math
import os
from collections import deque

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyArrowPatch, FancyBboxPatch

import common
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, savefig

CH = 17
M32 = 0xFFFFFFFF
CACHE_DIR = os.path.join(os.path.dirname(os.path.abspath(__file__)), "cache")


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js): u() is
    mulberry32 and norm() the Box-Muller transform that returns r cos(t) and keeps r sin(t) for the
    next call, exactly as in JavaScript."""

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        x = 0.0
        while x == 0.0:
            x = self.u()
        r = math.sqrt(-2.0 * math.log(x))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)


def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed), vectorised (mulberry32 adds a constant
    to its state at each call, so the j-th output is a hash of seed + j * 0x6D2B79F5 mod 2^32)."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    m = np.uint64(M32)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & m
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


# =========================================================================== Section 17.3: DAG vocabulary
def nodes_of(parents):
    return list(parents)


def children_of(parents):
    """Children of each node, listed in node order (the demos build them the same way)."""
    ch = {n: [] for n in parents}
    for n in parents:
        for p in parents[n]:
            ch[p].append(n)
    return ch


def ancestors(parents, S):
    """S together with all ancestors of nodes of S (the book counts a node as its own ancestor)."""
    out, stack = set(S), list(S)
    while stack:
        v = stack.pop()
        for p in parents[v]:
            if p not in out:
                out.add(p)
                stack.append(p)
    return out


def descendants(parents, S):
    """S together with all descendants of nodes of S."""
    ch = children_of(parents)
    out, stack = set(S), list(S)
    while stack:
        v = stack.pop()
        for c in ch[v]:
            if c not in out:
                out.add(c)
                stack.append(c)
    return out


def topological_order(parents):
    """A topological order: repeatedly take the first node (in node order) whose parents are all placed.
    Returns None when the graph has a directed cycle."""
    placed, order, left = set(), [], list(parents)
    while left:
        for v in left:
            if all(p in placed for p in parents[v]):
                order.append(v)
                placed.add(v)
                left.remove(v)
                break
        else:
            return None
    return order


def is_acyclic(parents):
    return topological_order(parents) is not None


def skeleton(parents):
    return frozenset(frozenset((p, n)) for n in parents for p in parents[n])


def v_structures(parents):
    """Unshielded colliders a -> c <- b with a and b not adjacent, as (frozenset({a, b}), c)."""
    sk = skeleton(parents)
    out = set()
    for c in parents:
        for a, b in itertools.combinations(parents[c], 2):
            if frozenset((a, b)) not in sk:
                out.add((frozenset((a, b)), c))
    return frozenset(out)


def equivalence_key(parents):
    """Theorem 17.13: skeleton and unshielded colliders together determine the Markov equivalence class."""
    return (skeleton(parents), v_structures(parents))


def edges_of(parents):
    return [(p, n) for n in parents for p in parents[n]]


def factorisation_string(parents):
    """'f(x)f(y|x)...' for a DAG, as in (17.3)."""
    out = []
    for n in parents:
        out.append("f(%s|%s)" % (n, ",".join(parents[n])) if parents[n] else "f(%s)" % n)
    return "".join(out)


# =========================================================================== Section 17.5: d-separation
def d_separated(parents, A, B, C, trace=False):
    """True if C d-separates A from B, by the reachability ('Bayes ball') search.

    A state is (node, direction): 'up' means the node was entered from one of its children (moving
    against an arrow), 'down' that it was entered from a parent. From a node outside C entered 'up' the
    search continues to its parents ('up') and its children ('down'); from a node outside C entered
    'down' only to its children (a chain); from a node entered 'down' that is in C or has a descendant
    in C (an unblocked collider) it turns back up to its parents. A and B are d-separated by C exactly
    when no node of B is reached. With trace=True also returns the list of visited states in order and
    the set of reached nodes (the demonstration shows the same sequence).
    """
    A, B, C = list(A), set(B), set(C)
    ch = children_of(parents)
    anc = ancestors(parents, C)          # C and its ancestors: exactly the colliders that are unblocked
    seen, reach, order = set(), [], []
    queue = deque((a, "up") for a in A)
    while queue:
        node, d = queue.popleft()
        if (node, d) in seen:
            continue
        seen.add((node, d))
        order.append((node, d))
        if node not in C and node not in reach:
            reach.append(node)
        if d == "up" and node not in C:
            queue.extend((p, "up") for p in parents[node])
            queue.extend((c, "down") for c in ch[node])
        elif d == "down":
            if node not in C:
                queue.extend((c, "down") for c in ch[node])
            if node in anc:
                queue.extend((p, "up") for p in parents[node])
    sep = not (set(reach) & B)
    if trace:
        return sep, order, reach
    return sep


def undirected_paths(parents, a, b):
    """Every simple path between a and b in the skeleton."""
    ch = children_of(parents)
    nbr = {n: list(parents[n]) + ch[n] for n in parents}
    out = []

    def go(path):
        v = path[-1]
        if v == b:
            out.append(list(path))
            return
        for w in nbr[v]:
            if w not in path:
                path.append(w)
                go(path)
                path.pop()
    go([a])
    return out


def is_collider(parents, path, i):
    return path[i - 1] in parents[path[i]] and path[i + 1] in parents[path[i]]


def path_active(parents, path, W):
    """The book's definition (p. 270): every collider on the path has a descendant in W (itself
    included) and no other vertex of the path is in W."""
    W = set(W)
    for i in range(1, len(path) - 1):
        v = path[i]
        if is_collider(parents, path, i):
            if not (descendants(parents, [v]) & W):
                return False
        elif v in W:
            return False
    return True


def d_separated_paths(parents, A, B, W):
    """d-separation by listing every undirected path (exponential; used only to check d_separated)."""
    for a in A:
        for b in B:
            for p in undirected_paths(parents, a, b):
                if path_active(parents, p, W):
                    return False
    return True


def local_markov(parents):
    """The statements of the Markov condition (17.4): for each W, W indep (non-descendants minus parents)
    given its parents; statements with an empty right-hand side are omitted. Returns (W, set, parents)."""
    out = []
    for w in parents:
        nd = [v for v in parents if v not in descendants(parents, [w]) and v not in parents[w]]
        if nd:
            out.append((w, nd, list(parents[w])))
    return out


def independence_statements(parents):
    """I(G): all (x, y, W) with x before y in node order, W a subset of the other nodes, and x, y
    d-separated by W. By definition a statement between sets is a conjunction of such pairs."""
    nodes = list(parents)
    out = set()
    for i, j in itertools.combinations(range(len(nodes)), 2):
        rest = [v for k, v in enumerate(nodes) if k not in (i, j)]
        for r in range(len(rest) + 1):
            for W in itertools.combinations(rest, r):
                if d_separated(parents, [nodes[i]], [nodes[j]], W):
                    out.add((nodes[i], nodes[j], frozenset(W)))
    return frozenset(out)


# =========================================================================== Markov equivalence
PAIR_STATES = (0, 1, 2)   # 0 no edge, 1 i -> j, 2 j -> i (i before j in node order)


def all_dags(nodes):
    """Every DAG on the given nodes, by trying the three states of each pair (pairs in lexicographic
    order, the first pair varying fastest), keeping the acyclic ones."""
    pairs = list(itertools.combinations(range(len(nodes)), 2))
    out = []
    for code in range(3 ** len(pairs)):
        par = {v: [] for v in nodes}
        c = code
        for (i, j) in pairs:
            s, c = c % 3, c // 3
            if s == 1:
                par[nodes[j]].append(nodes[i])
            elif s == 2:
                par[nodes[i]].append(nodes[j])
        if is_acyclic(par):
            out.append(par)
    return out


def equivalence_classes(dags):
    """Group DAGs by (skeleton, unshielded colliders)."""
    cl = {}
    for g in dags:
        cl.setdefault(equivalence_key(g), []).append(g)
    return cl


def essential_graph(members):
    """Edges directed the same way in every member of a class (the others are reversible).
    Returns (directed, undirected) as sets of pairs."""
    sets = [set(edges_of(g)) for g in members]
    directed = set.intersection(*sets)
    und = set()
    for (a, b) in sets[0]:
        if (a, b) not in directed:
            und.add(frozenset((a, b)))
    return directed, und


def robinson_count(n):
    """Robinson's (1973) recursion for the number of labelled DAGs on n nodes."""
    a = [1]
    for m in range(1, n + 1):
        a.append(sum((-1) ** (k + 1) * math.comb(m, k) * 2 ** (k * (m - k)) * a[m - k] for k in range(1, m + 1)))
    return a[n]


def covered(parents, x, y):
    """The edge x -> y is covered when pa(y) = pa(x) + {x} (Chickering, 1995)."""
    return x in parents[y] and set(parents[y]) == set(parents[x]) | {x}


def reverse_edge(parents, x, y):
    g = {v: list(ps) for v, ps in parents.items()}
    g[y].remove(x)
    g[x].append(y)
    return g


def covered_reversal_path(G, H):
    """A sequence of covered-edge reversals turning G into the equivalent DAG H (the constructive proof
    of the 'if' half of Theorem 17.13). At each step: among edges of G oriented against H, take the one
    whose head y comes first in a topological order of G and, for that y, whose tail x comes last; that
    edge is covered. Returns the list of reversed edges."""
    G = {v: list(ps) for v, ps in G.items()}
    steps = []
    while True:
        hE = set(edges_of(H))
        diff = [(a, b) for (a, b) in edges_of(G) if (a, b) not in hE]
        if not diff:
            return steps
        order = topological_order(G)
        pos = {v: i for i, v in enumerate(order)}
        y = min((b for (a, b) in diff), key=lambda v: pos[v])
        x = max((a for (a, b) in diff if b == y), key=lambda v: pos[v])
        if not covered(G, x, y):
            raise RuntimeError("the chosen edge is not covered: the DAGs are not equivalent")
        G = reverse_edge(G, x, y)
        steps.append((x, y))


# =========================================================================== discrete distributions
def cards_of(parents, cards=None):
    return [2 if cards is None else cards[v] for v in parents]


def joint_from_cpts(parents, cpts, cards=None):
    """The joint table f(v) = prod_i f(x_i | pi_i) of (17.3). cpts[v] is an array of shape
    (card(parents...), card(v)) indexed by the parents' values in the order of parents[v]."""
    nodes = list(parents)
    K = cards_of(parents, cards)
    J = np.ones(K)
    for idx in itertools.product(*[range(k) for k in K]):
        val = dict(zip(nodes, idx))
        p = 1.0
        for v in nodes:
            p *= cpts[v][tuple(val[q] for q in parents[v]) + (val[v],)]
        J[idx] = p
    return J


def random_cpts(parents, rng, lo=0.1, hi=0.9):
    """Random binary conditional probability tables, P(v = 1 | parents) uniform on [lo, hi]."""
    out = {}
    for v in parents:
        k = len(parents[v])
        p1 = lo + (hi - lo) * rng.random((2,) * k)
        out[v] = np.stack([1 - p1, p1], axis=-1)
    return out


def marginal(J, nodes, keep):
    axes = tuple(i for i, v in enumerate(nodes) if v not in keep)
    M = J.sum(axis=axes)
    kept = [v for v in nodes if v in keep]
    return M, kept


def cond_mi(J, nodes, A, B, C):
    """Exact conditional mutual information I(A; B | C) (nats) of a joint table; zero iff A indep B | C."""
    A, B, C = list(A), list(B), list(C)
    keep = A + B + C
    M, kept = marginal(J, nodes, set(keep))
    # reorder axes to A, B, C
    perm = [kept.index(v) for v in keep]
    M = np.transpose(M, perm)
    sa, sb = M.shape[:len(A)], M.shape[len(A):len(A) + len(B)]
    na, nb = int(np.prod(sa)), int(np.prod(sb))
    M = M.reshape(na, nb, -1)
    pc = M.sum((0, 1))
    pac = M.sum(1)
    pbc = M.sum(0)
    out = 0.0
    for i in range(na):
        for j in range(nb):
            for k in range(M.shape[2]):
                p = M[i, j, k]
                if p > 0:
                    out += p * math.log(p * pc[k] / (pac[i, k] * pbc[j, k]))
    return max(out, 0.0)


def conditional_table(J, nodes, v, given):
    """f(v | given) from a joint table, shape (card(given)..., card(v)), with given in the listed order."""
    M, kept = marginal(J, nodes, set(given) | {v})
    perm = [kept.index(u) for u in list(given) + [v]]
    M = np.transpose(M, perm)
    with np.errstate(invalid="ignore", divide="ignore"):
        return M / M.sum(axis=-1, keepdims=True)


# =========================================================================== Section 17.6: estimation
def fit_discrete_dag(parents, data, cards):
    """Maximum likelihood for a discrete DAG: each f(x_j | pi_j) is the table of empirical conditional
    frequencies. data is an (n, k) integer array with columns in node order."""
    nodes = list(parents)
    col = {v: i for i, v in enumerate(nodes)}
    cpts = {}
    for v in nodes:
        shape = tuple(cards[p] for p in parents[v]) + (cards[v],)
        N = np.zeros(shape)
        idx = tuple(data[:, col[p]] for p in parents[v]) + (data[:, col[v]],)
        np.add.at(N, idx, 1)
        with np.errstate(invalid="ignore"):
            cpts[v] = N / N.sum(axis=-1, keepdims=True)
    return cpts


def family_scores(counts, nnodes):
    """Log-likelihood and parameter count of every (node, parent set) family for binary data.

    counts is the table of the 2^k cells, cell index sum_i x_i 2^i (node i in node order). Returns a dict
    {(i, mask): (loglik, nparams)} where mask is the parent set as a bit mask."""
    k = nnodes
    out = {}
    cells = np.arange(2 ** k)
    bits = (cells[:, None] >> np.arange(k)[None, :]) & 1
    for i in range(k):
        for mask in range(2 ** k):
            if mask >> i & 1:
                continue
            pa = [j for j in range(k) if mask >> j & 1]
            cfg = np.zeros(2 ** k, dtype=int)
            for t, j in enumerate(pa):
                cfg += bits[:, j] << t
            N = np.zeros((2 ** len(pa), 2))
            np.add.at(N, (cfg, bits[:, i]), counts)
            tot = N.sum(1, keepdims=True)
            with np.errstate(divide="ignore", invalid="ignore"):
                ll = np.where(N > 0, N * np.log(N / tot), 0.0).sum()
            out[(i, mask)] = (float(ll), 2 ** len(pa))
    return out


def dag_mask_parents(parents, nodes):
    pos = {v: i for i, v in enumerate(nodes)}
    return [sum(1 << pos[p] for p in parents[v]) for v in nodes]


def dag_scores(dags, nodes, counts, n):
    """Maximised log-likelihood, parameter count, AIC = l - k and BIC = l - (k/2) log n of each DAG
    (the book's sign convention, Section 13.6: larger is better)."""
    fam = family_scores(counts, len(nodes))
    out = []
    for g in dags:
        masks = dag_mask_parents(g, nodes)
        ll = sum(fam[(i, m)][0] for i, m in enumerate(masks))
        k = sum(fam[(i, m)][1] for i, m in enumerate(masks))
        out.append((ll, k, ll - k, ll - 0.5 * k * math.log(n)))
    return out


def counts_from_data(data):
    k = data.shape[1]
    idx = (data * (1 << np.arange(k))).sum(1)
    return np.bincount(idx, minlength=2 ** k).astype(float)


def sample_dag(parents, cpts, n, rng, cards=None):
    """Ancestral sampling (the pseudocode of p. 273): each variable drawn given its sampled parents."""
    nodes = list(parents)
    col = {v: i for i, v in enumerate(nodes)}
    K = cards_of(parents, cards)
    X = np.zeros((n, len(nodes)), dtype=int)
    for v in topological_order(parents):
        P = cpts[v][tuple(X[:, col[p]] for p in parents[v])]      # (n, card), or (card,) for a root
        P = np.broadcast_to(P, (n, P.shape[-1]))
        u = rng.random(n)
        X[:, col[v]] = (u[:, None] > np.cumsum(P, axis=1)[:, :-1]).sum(1)
    return X


# =========================================================================== Section 17.8: interventions
def intervene(J, nodes, parents, x, value):
    """The truncated factorisation for 'set x = value': f*(v) = f(v) / f(x | pi_x) on {x = value}, zero
    elsewhere. Returns the post-intervention joint table (a distribution Markov to the mutilated DAG)."""
    i = nodes.index(x)
    cond = conditional_table(J, nodes, x, parents[x])        # f(x | pi_x)
    out = np.zeros_like(J)
    for idx in itertools.product(*[range(s) for s in J.shape]):
        if idx[i] != value:
            continue
        pv = tuple(idx[nodes.index(p)] for p in parents[x])
        c = cond[pv + (value,)]
        out[idx] = J[idx] / c if c > 0 else 0.0
    return out


def expit(t):
    return 1.0 / (1.0 + math.exp(-t))


EX17_8 = dict(px=0.5, a0=-2.0, a1=4.0, b0=-2.0, bx=2.0, by=2.0, rand=False)


def binary_scm_probs(prm):
    """Conditional probabilities of the binary model X -> Y -> Z, X -> Z of Exercise 17.8 (generalised):
    P(X=1) = px, P(Y=1|x) = expit(a0 + a1 x) (or 1/2 if Y is randomised), P(Z=1|x,y) = expit(b0 + bx x + by y)."""
    pX = prm["px"]
    pY = [0.5, 0.5] if prm.get("rand") else [expit(prm["a0"]), expit(prm["a0"] + prm["a1"])]
    pZ = [[expit(prm["b0"] + prm["bx"] * x + prm["by"] * y) for y in (0, 1)] for x in (0, 1)]
    return pX, pY, pZ


def binary_scm_exact(prm):
    """Exact P(Z=1 | Y=y) (conditioning, p. 273) and P(Z=1 | Y:=y) (intervening, p. 274) for y = 0, 1,
    with the weights f(x | y) and f(x) of the two formulas."""
    pX, pY, pZ = binary_scm_probs(prm)
    px = [1 - pX, pX]
    out = {"cond": [], "do": [], "wcond": [], "wdo": [px[1], px[1]]}
    for y in (0, 1):
        py_x = [pY[x] if y == 1 else 1 - pY[x] for x in (0, 1)]
        py = sum(px[x] * py_x[x] for x in (0, 1))
        w = [px[x] * py_x[x] / py for x in (0, 1)]                # f(x | y)
        out["cond"].append(sum(pZ[x][y] * w[x] for x in (0, 1)))
        out["do"].append(sum(pZ[x][y] * px[x] for x in (0, 1)))
        out["wcond"].append(w[1])
    out["pY1"] = sum(px[x] * pY[x] for x in (0, 1))
    return out


def binary_scm_sim(prm, N, seed):
    """The two computer programs of p. 273 run N times with the demo's generator.

    Observational run (DK.rng(seed)): per unit three uniforms, x, y, z in turn. Interventional run
    (DK.rng(seed + 1)): per unit two uniforms, x and a common uniform for z, so that the same unit is
    seen under 'set Y = 0' and 'set Y = 1' (its two counterfactual outcomes). Returns running estimates
    of P(Z=1 | Y=1), P(Z=1 | Y=0), P(Z=1 | Y:=1) and P(Z=1 | Y:=0) after each unit."""
    pX, pY, pZ = binary_scm_probs(prm)
    pZ = np.array(pZ)
    u = js_uniforms(seed, 3 * N).reshape(N, 3)
    x = (u[:, 0] < pX).astype(int)
    y = (u[:, 1] < np.where(x == 1, pY[1], pY[0])).astype(int)
    z = (u[:, 2] < pZ[x, y]).astype(int)
    v = js_uniforms(seed + 1, 2 * N).reshape(N, 2)
    xi = (v[:, 0] < pX).astype(int)
    z1 = (v[:, 1] < pZ[xi, 1]).astype(int)
    z0 = (v[:, 1] < pZ[xi, 0]).astype(int)
    n1 = np.cumsum(y)
    n0 = np.cumsum(1 - y)
    with np.errstate(invalid="ignore", divide="ignore"):
        c1 = np.cumsum(z * y) / n1
        c0 = np.cumsum(z * (1 - y)) / n0
    k = np.arange(1, N + 1)
    return {"cond1": c1, "cond0": c0, "do1": np.cumsum(z1) / k, "do0": np.cumsum(z0) / k,
            "x": x, "y": y, "z": z}


def gauss_scm_moments(alpha, beta, gamma, randomised=False):
    """Exercise 17.9: X ~ N(0,1), Y = alpha X + e1 (or Y = alpha + e1 when Y is randomised), Z = beta Y +
    gamma X + e2. Returns the slope and residual variance of E(Z | Y = y), the causal slope of
    E(Z | Y := y), and corr(Y, Z)."""
    if randomised:
        vy, cxy = 1.0, 0.0
    else:
        vy, cxy = alpha ** 2 + 1.0, alpha
    cyz = beta * vy + gamma * cxy
    vz = beta ** 2 * vy + gamma ** 2 + 2 * beta * gamma * cxy + 1.0
    slope = cyz / vy
    resid = vz - cyz ** 2 / vy
    return {"slope": slope, "resvar": resid, "causal": beta, "rho": cyz / math.sqrt(vy * vz), "vy": vy,
            "vz": vz, "cyz": cyz}


# =========================================================================== the three demos
INT_PRESETS = [
    dict(px=0.5, a0=-2.0, a1=4.0, b0=-2.0, bx=2.0, by=2.0, rand=False, N=2000, seed=1),
    dict(px=0.5, a0=-2.0, a1=4.0, b0=-1.0, bx=2.5, by=0.0, rand=False, N=2000, seed=2),
    dict(px=0.5, a0=-2.0, a1=4.0, b0=1.0, bx=-4.0, by=1.0, rand=False, N=2000, seed=3),
    dict(px=0.5, a0=-2.0, a1=4.0, b0=-2.0, bx=2.0, by=2.0, rand=True, N=2000, seed=4),
    dict(px=0.3, a0=-1.0, a1=3.0, b0=-1.5, bx=0.0, by=2.0, rand=False, N=2000, seed=5),
]


def demo_intervention(prm):
    """What the intervention demo shows for one setting: exact values and the final simulated estimates."""
    ex = binary_scm_exact(prm)
    sim = binary_scm_sim(prm, prm["N"], prm["seed"])
    return {"cond": ex["cond"], "do": ex["do"], "wcond": ex["wcond"],
            "sim": [float(sim["cond0"][-1]), float(sim["cond1"][-1]), float(sim["do0"][-1]), float(sim["do1"][-1])]}


# Markov equivalence demo: graphs on up to five binary nodes
EQ_GRAPHS = {
    "chain": (["X", "Y", "Z"], {"X": [], "Y": ["X"], "Z": ["Y"]}),
    "collider": (["X", "Y", "Z"], {"X": [], "Y": ["X", "Z"], "Z": []}),
    "rain": (["R", "W"], {"R": [], "W": ["R"]}),
    "fig17_3": (["X", "Y", "Z", "W"], {"X": [], "Y": [], "Z": ["X", "Y"], "W": ["Z"]}),
    "fig17_4": (["A", "B", "C", "D", "E"], {"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"], "E": ["D"]}),
    "fig17_5": (["X1", "X2", "X3", "X4", "X5"], {"X1": [], "X2": [], "X3": ["X1", "X2"], "X4": ["X1"], "X5": ["X3", "X4"]}),
}
EQ_PRESETS = [
    dict(g="chain", n=500, seed=3), dict(g="collider", n=500, seed=2), dict(g="rain", n=200, seed=3),
    dict(g="fig17_3", n=1000, seed=4), dict(g="fig17_4", n=2000, seed=5),
]


def demo_cpts_and_data(parents, nodes, n, seed, lo=0.05, hi=0.95):
    """The equivalence demo's data: one generator DK.rng(seed); first the tables (nodes in node order,
    parent configurations 0, 1, ... with the first parent as the lowest bit, P(v=1|.) = lo + (hi-lo) u),
    then n rows drawn ancestrally (nodes in topological order, one uniform each, v = 1 if u < P)."""
    g = JSRandom(seed)
    p1 = {}
    for v in nodes:
        p1[v] = [lo + (hi - lo) * g.u() for _ in range(2 ** len(parents[v]))]
    order = topological_order({v: parents[v] for v in nodes})
    X = np.zeros((n, len(nodes)), dtype=int)
    col = {v: i for i, v in enumerate(nodes)}
    for r in range(n):
        for v in order:
            cfg = sum(X[r, col[p]] << t for t, p in enumerate(parents[v]))
            X[r, col[v]] = 1 if g.u() < p1[v][cfg] else 0
    return p1, X


def demo_equivalence(g, n, seed, crit="bic"):
    nodes, parents = EQ_GRAPHS[g]
    parents = {v: parents[v] for v in nodes}
    p1, X = demo_cpts_and_data(parents, nodes, n, seed)
    counts = counts_from_data(X)
    dags = all_dags(nodes)
    sc = dag_scores(dags, nodes, counts, n)
    key = equivalence_key(parents)
    cls = equivalence_classes(dags)
    j = 3 if crit == "bic" else 2
    best = max(range(len(dags)), key=lambda i: sc[i][j])
    in_true = [equivalence_key(d) == key for d in dags]
    true_ll = [sc[i][0] for i in range(len(dags)) if in_true[i]]
    # one score per class (all members tie, Section 17.6); rank of the true class, 1 = best
    cls_score = {}
    spread = 0.0
    for d, s_ in zip(dags, sc):
        k_ = equivalence_key(d)
        if k_ in cls_score:
            spread = max(spread, abs(cls_score[k_] - s_[j]))
        else:
            cls_score[k_] = s_[j]
    rank = 1 + sum(1 for k_, v in cls_score.items() if v > cls_score[key])
    return {"ndags": len(dags), "nclasses": len(cls), "classsize": len(cls[key]),
            "bestscore": sc[best][j], "best_in_true": bool(in_true[best]), "rank": rank,
            "truell": true_ll[0], "truescore": cls_score[key], "spread": spread,
            "nstatements": len(independence_statements(parents)), "counts": counts}


# reachability demo
REACH_GRAPHS = {
    "fig17_8": {"X": [], "U": ["X", "V"], "V": [], "W": ["V", "Y"], "Y": [], "S1": ["U"], "S2": ["W"]},
    "fig17_5": {"X1": [], "X2": [], "X3": ["X1", "X2"], "X4": ["X1"], "X5": ["X3", "X4"]},
    "fig17_7": {"X": [], "Y": ["X", "Z"], "Z": [], "W": ["Y"]},
    "fig17_4": {"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"], "E": ["D"]},
    "fig17_12": {"X": [], "Y1": ["X", "Z1"], "Z1": [], "Y2": ["X", "Z2"], "Z2": [], "Y3": ["X", "Z3"], "Z3": [],
                 "Y4": ["X", "Z4"], "Z4": []},
}
REACH_PRESETS = [
    dict(g="fig17_8", src="X", W=[], seed=1), dict(g="fig17_8", src="X", W=["S1", "S2"], seed=1),
    dict(g="fig17_8", src="X", W=["S1", "S2", "V"], seed=1), dict(g="fig17_5", src="X2", W=["X1", "X3"], seed=2),
    dict(g="fig17_7", src="X", W=["W"], seed=3),
]


def demo_random_cpts(parents, seed):
    """The reachability demo's random binary tables: DK.rng(seed), nodes in node order, configurations
    0, 1, ... (first parent = lowest bit), P(v = 1 | .) = 0.1 + 0.8 u."""
    g = JSRandom(seed)
    cpts = {}
    for v in parents:
        k = len(parents[v])
        p1 = np.zeros((2,) * k)
        for cfg in range(2 ** k):
            idx = tuple((cfg >> t) & 1 for t in range(k))
            p1[idx] = 0.1 + 0.8 * g.u()
        cpts[v] = np.stack([1 - p1, p1], axis=-1)
    return cpts


def demo_reachability(g, src, W, seed):
    parents = REACH_GRAPHS[g]
    nodes = list(parents)
    sep, order, reach = d_separated(parents, [src], [], W, trace=True)
    J = joint_from_cpts(parents, demo_random_cpts(parents, seed))
    cmi = {}
    for v in nodes:
        if v == src or v in W:
            continue
        cmi[v] = cond_mi(J, nodes, [src], [v], W)
    return {"order": order, "reach": reach, "cmi": cmi}


# =========================================================================== book examples
G17_1 = {"Y": [], "X": ["Y"], "Z": ["Y"]}
G17_2 = {"overweight": [], "smoking": [], "heart disease": ["overweight", "smoking"], "cough": ["smoking"]}
G17_3 = {"X": [], "Y": [], "Z": ["X", "Y"], "W": ["Z"]}
G17_4 = {"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"], "E": ["D"]}
G17_5 = {"X1": [], "X2": [], "X3": ["X1", "X2"], "X4": ["X1"], "X5": ["X3", "X4"]}
G17_6 = [{"X": [], "Y": ["X"], "Z": ["Y"]}, {"Z": [], "Y": ["Z"], "X": ["Y"]},
         {"Y": [], "X": ["Y"], "Z": ["Y"]}, {"X": [], "Z": [], "Y": ["X", "Z"]}]
G17_7 = {"X": [], "Z": [], "Y": ["X", "Z"], "W": ["Y"]}
G17_8 = REACH_GRAPHS["fig17_8"]
G17_9 = {"aliens": [], "forgot watch": [], "late": ["aliens", "forgot watch"]}
G17_10 = {"X": [], "Y": ["X"], "Z": ["X", "Y"]}
G17_12 = REACH_GRAPHS["fig17_12"]

# Example 17.11 with numbers (the book gives none): rare abductions, an occasional forgotten watch.
ALIENS = dict(pa=0.01, pw=0.10, late={(0, 0): 0.05, (1, 0): 0.95, (0, 1): 0.90, (1, 1): 0.99})


def aliens_probs(prm=ALIENS):
    """P(aliens), P(aliens | late), P(aliens | late, watch not set), P(aliens | late, watch set)."""
    J = np.zeros((2, 2, 2))
    for a in (0, 1):
        for w in (0, 1):
            pl = prm["late"][(a, w)]
            pa = prm["pa"] if a else 1 - prm["pa"]
            pw = prm["pw"] if w else 1 - prm["pw"]
            J[a, w, 1] = pa * pw * pl
            J[a, w, 0] = pa * pw * (1 - pl)
    p_a = J[1].sum()
    p_a_l = J[1, :, 1].sum() / J[:, :, 1].sum()
    p_a_lw = J[1, 1, 1] / J[:, 1, 1].sum()
    p_a_lnw = J[1, 0, 1] / J[:, 0, 1].sum()
    return {"prior": p_a, "late": p_a_l, "late_forgot": p_a_lw, "late_set": p_a_lnw, "J": J}


# Exercise 17.3
EX3 = np.array([[[0.405, 0.125], [0.045, 0.125]], [[0.045, 0.125], [0.005, 0.125]]])   # [x, y, z]

# Exercise 17.6: a distribution Markov to X -> Y -> Z with X, Y binary and Z in {0, 1, 2}
EX6 = {"X": np.array([0.4, 0.6]), "Y": np.array([[0.7, 0.3], [0.2, 0.8]]),
       "Z": np.array([[0.6, 0.3, 0.1], [0.2, 0.3, 0.5]])}
EX6_G = {"X": [], "Y": ["X"], "Z": ["Y"]}
EX6_CARDS = {"X": 2, "Y": 2, "Z": 3}


def ex6_theta(cpts):
    """theta_rst = P(X=r, Y=s, Z=t) = f(r) f(s|r) f(t|s), a (2, 2, 3) array."""
    return cpts["X"][:, None, None] * cpts["Y"][:, :, None] * cpts["Z"][None, :, :]


def ex6_bootstrap(n=1000, B=2000, seed=17):
    """Exercise 17.6: simulate n vectors, the DAG-constrained MLE, and the nonparametric bootstrap
    (standard errors and 95% percentile intervals) for the twelve cell probabilities."""
    rng = np.random.default_rng(seed)
    X = sample_dag(EX6_G, EX6, n, rng, EX6_CARDS)
    th_hat = ex6_theta(fit_discrete_dag(EX6_G, X, EX6_CARDS))
    boot = np.empty((B, 2, 2, 3))
    for b in range(B):
        Xb = X[rng.integers(0, n, n)]
        boot[b] = ex6_theta(fit_discrete_dag(EX6_G, Xb, EX6_CARDS))
    se = boot.std(axis=0, ddof=1)
    lo, hi = np.percentile(boot, [2.5, 97.5], axis=0)
    emp = np.zeros((2, 2, 3))
    np.add.at(emp, (X[:, 0], X[:, 1], X[:, 2]), 1)
    return {"data": X, "theta": ex6_theta(EX6), "mle": th_hat, "se": se, "lo": lo, "hi": hi,
            "saturated": emp / n, "boot": boot}


def ex6_delta_se(cpts, n):
    """Asymptotic standard errors of the DAG MLE of theta_rst: theta = a b c with independent multinomial
    pieces, so Var(log theta) ~ Var(log a) + Var(log b) + Var(log c) (delta method)."""
    a, Bm, Cm = cpts["X"], cpts["Y"], cpts["Z"]
    th = ex6_theta(cpts)
    out = np.zeros_like(th)
    for r in range(2):
        for s in range(2):
            for t in range(3):
                va = (1 - a[r]) / (n * a[r])
                ny = n * a[r]
                vb = (1 - Bm[r, s]) / (ny * Bm[r, s])
                nz = n * (a * Bm[:, s]).sum()
                vc = (1 - Cm[s, t]) / (nz * Cm[s, t])
                out[r, s, t] = th[r, s, t] * math.sqrt(va + vb + vc)
    return out


# =========================================================================== drawing graphs
NODE_FC = "white"
OBS_FC = "#c9c9c9"


def draw_dag(ax, pos, parents, observed=(), labels=None, latent=(), r=0.27, box=False, fs=12,
             colour="#222222", edge_colours=None, curved=None, node_colours=None, lw=1.4):
    """Draw a DAG: circles (or rounded boxes for long names), shaded when conditioned on, dashed when
    unobserved; arrows clipped at the node outlines."""
    labels = labels or {}
    edge_colours = edge_colours or {}
    curved = curved or {}
    node_colours = node_colours or {}
    patches = {}
    for v, (x, y) in pos.items():
        fc = node_colours.get(v, OBS_FC if v in observed else NODE_FC)
        ls = "--" if v in latent else "-"
        if box:
            txt = labels.get(v, v)
            w = 0.115 * len(txt) * fs / 10 + 0.3
            p = FancyBboxPatch((x - w / 2, y - 0.17), w, 0.34, boxstyle="round,pad=0.02,rounding_size=0.12",
                               fc=fc, ec=colour, lw=lw, ls=ls, zorder=2)
        else:
            p = Circle((x, y), r, fc=fc, ec=colour, lw=lw, ls=ls, zorder=2)
        ax.add_patch(p)
        patches[v] = p
        ax.text(x, y, labels.get(v, v), ha="center", va="center", fontsize=fs, zorder=3)
    for v in parents:
        for p in parents[v]:
            if p not in pos or v not in pos:
                continue
            rad = curved.get((p, v), 0.0)
            arr = FancyArrowPatch(pos[p], pos[v], patchA=patches[p], patchB=patches[v], arrowstyle="-|>",
                                  mutation_scale=14, lw=lw, color=edge_colours.get((p, v), colour),
                                  connectionstyle="arc3,rad=%g" % rad, shrinkA=1, shrinkB=1, zorder=1)
            ax.add_patch(arr)
    ax.set_aspect("equal")
    ax.axis("off")


def _limits(ax, pos, padx=0.5, pady=None):
    pady = padx if pady is None else pady
    xs, ys = [p[0] for p in pos.values()], [p[1] for p in pos.values()]
    ax.set_xlim(min(xs) - padx, max(xs) + padx)
    ax.set_ylim(min(ys) - pady, max(ys) + pady)


def _tex(n):
    import re
    m = re.match(r"([A-Za-z]+)(\d+)$", n)
    return "$%s_{%s}$" % m.groups() if m else "$%s$" % n


IND = r"\perp\!\!\!\perp"
NIND = r"\not\perp\!\!\!\perp"


def _set_tex(S):
    S = list(S)
    if not S:
        return r"\emptyset"
    inner = ",".join(_tex(v).strip("$") for v in S)
    return inner if len(S) == 1 else r"\{%s\}" % inner


def _stmt(a, b, W, sep):
    rel = IND if sep else NIND
    tail = "" if not W else r" \mid " + _set_tex(W)
    return "$%s %s %s%s$" % (_set_tex(a), rel, _set_tex(b), tail)


# =========================================================================== figures: the book's graphs
def fig_17_1(out_dir=None):
    """Figure 17.1: a directed graph with edges Y -> X and Y -> Z."""
    pos = {"Y": (1, 0.8), "X": (0, 0), "Z": (2, 0)}
    fig, ax = plt.subplots(figsize=(2.9, 2.0))
    draw_dag(ax, pos, G17_1)
    _limits(ax, pos, 0.4)
    ax.set_ylim(-0.75, 1.15)
    ax.text(1, -0.6, r"$f(x,y,z)=f(y)\,f(x\mid y)\,f(z\mid y)$", ha="center", fontsize=10)
    savefig(fig, CH, "fig17-1", out_dir)


def fig_17_2(out_dir=None):
    """Figure 17.2: the DAG of Example 17.4, with the dependence of Example 17.12 computed."""
    pos = {"overweight": (0, 1), "smoking": (2.4, 1), "heart disease": (1.2, 0), "cough": (3.4, 0)}
    fig, ax = plt.subplots(figsize=(4.6, 2.4))
    draw_dag(ax, pos, G17_2, box=True, fs=10)
    _limits(ax, pos, 0.75, 0.45)
    ax.set_ylim(-0.95, 1.3)
    s1 = d_separated(G17_2, ["overweight"], ["smoking"], [])
    s2 = d_separated(G17_2, ["overweight"], ["smoking"], ["heart disease"])
    ax.text(1.7, -0.55, "overweight %s smoking;   given heart disease: %s" % ("independent" if s1 else "dependent",
            "independent" if s2 else "dependent"), ha="center", fontsize=9, color=GREEN if s1 and not s2 else RED)
    savefig(fig, CH, "fig17-2", out_dir)


def _markov_text(parents, names=None):
    """The Markov statements, dropping a statement that only mirrors an earlier one (Y indep X after
    X indep Y), as the book does."""
    lines, seen = [], set()
    for w, nd, pa in local_markov(parents):
        key = (frozenset([w]), frozenset(nd), frozenset(pa))
        mirror = (frozenset(nd), frozenset([w]), frozenset(pa))
        if mirror in seen:
            continue
        seen.add(key)
        lines.append(_stmt([w], nd, pa, True))
    return lines


def fig_17_3(out_dir=None):
    """Figure 17.3, with the Markov statements of Example 17.7 produced by local_markov."""
    pos = {"X": (0, 1.0), "Y": (0, -0.2), "Z": (1.2, 0.4), "W": (2.4, 0.4)}
    fig, ax = plt.subplots(figsize=(4.2, 2.1))
    draw_dag(ax, pos, G17_3)
    _limits(ax, pos, 0.4)
    ax.set_xlim(-0.4, 4.9)
    for i, s in enumerate(_markov_text(G17_3)):
        ax.text(3.0, 0.95 - 0.38 * i, s, fontsize=10.5, va="center")
    ax.text(3.0, 1.35, "Markov condition:", fontsize=9.5, color=GREY, va="center")
    savefig(fig, CH, "fig17-3", out_dir)


def fig_17_4(out_dir=None):
    """Figure 17.4, with the Markov statements of Example 17.8 produced by local_markov."""
    pos = {"A": (0, 1.0), "B": (-0.7, 0.2), "C": (0.7, 0.2), "D": (0, -0.6), "E": (0, -1.4)}
    fig, ax = plt.subplots(figsize=(4.6, 2.7))
    draw_dag(ax, pos, G17_4)
    _limits(ax, pos, 0.4)
    ax.set_xlim(-1.1, 4.4)
    st = _markov_text(G17_4)
    ax.text(1.35, 1.0, "Markov condition:", fontsize=9.5, color=GREY, va="center")
    for i, s in enumerate(st):
        ax.text(1.35, 0.55 - 0.42 * i, s, fontsize=10.5, va="center")
    savefig(fig, CH, "fig17-4", out_dir)


def fig_17_5(out_dir=None):
    """Figure 17.5, its five Markov statements, and the extra relation found by d-separation."""
    pos = {"X2": (0, 2.0), "X3": (0.9, 1.2), "X1": (0, 0.4), "X5": (1.8, 0.4), "X4": (0.9, -0.4)}
    fig, ax = plt.subplots(figsize=(5.6, 2.9))
    draw_dag(ax, {k: pos[k] for k in ["X1", "X2", "X3", "X4", "X5"]}, G17_5, labels={v: _tex(v) for v in pos})
    _limits(ax, pos, 0.4)
    ax.set_xlim(-0.4, 6.3)
    ax.text(2.6, 2.05, "Markov condition:", fontsize=9.5, color=GREY, va="center")
    st = _markov_text(G17_5)
    for i, s in enumerate(st):
        ax.text(2.6, 1.65 - 0.36 * i, s, fontsize=10.5, va="center")
    sep = d_separated(G17_5, ["X4", "X5"], ["X2"], ["X1", "X3"])
    ax.text(2.6, 1.65 - 0.36 * len(st) - 0.12, "and, by d-separation:", fontsize=9.5, color=GREY, va="center")
    ax.text(2.6, 1.65 - 0.36 * (len(st) + 1) - 0.12, _stmt(["X4", "X5"], ["X2"], ["X1", "X3"], sep), fontsize=10.5,
            va="center", color=GREEN)
    savefig(fig, CH, "fig17-5", out_dir)


def fig_17_6(out_dir=None):
    """Figure 17.6: the three non-collider DAGs and the collider, with d-separation verdicts."""
    fig, axes = plt.subplots(2, 2, figsize=(6.4, 3.2))
    pos = {"X": (0, 0), "Y": (1, 0), "Z": (2, 0)}
    names = ["chain", "reversed chain", "fork", "collider"]
    for k, g in enumerate(G17_6):
        ax = axes[k // 2, k % 2]
        draw_dag(ax, pos, g)
        _limits(ax, pos, 0.4)
        ax.set_ylim(-1.05, 0.45)
        a = d_separated(g, ["X"], ["Z"], [])
        b = d_separated(g, ["X"], ["Z"], ["Y"])
        ax.text(0.45, -0.7, _stmt(["X"], ["Z"], [], a), ha="center", fontsize=10.5, color=GREEN if a else RED)
        ax.text(1.55, -0.7, _stmt(["X"], ["Z"], ["Y"], b), ha="center", fontsize=10.5, color=GREEN if b else RED)
        ax.set_title(names[k], fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig17-6", out_dir)


def fig_17_7(out_dir=None):
    """Figure 17.7: a collider with a descendant, with the verdicts of rule 3."""
    pos = {"X": (0, 0.6), "Y": (1, 0.6), "Z": (2, 0.6), "W": (1, -0.4)}
    fig, ax = plt.subplots(figsize=(5.0, 2.2))
    draw_dag(ax, pos, G17_7)
    _limits(ax, pos, 0.4)
    ax.set_xlim(-0.4, 5.0)
    for i, W in enumerate([[], ["Y"], ["W"]]):
        s = d_separated(G17_7, ["X"], ["Z"], W)
        ax.text(2.8, 0.85 - 0.45 * i, _stmt(["X"], ["Z"], W, s), fontsize=10.5, va="center", color=GREEN if s else RED)
    savefig(fig, CH, "fig17-7", out_dir)


def fig_17_8(out_dir=None):
    """Figure 17.8 with the three statements of Example 17.9 computed by d_separated."""
    pos = {"X": (0, 1), "U": (1, 1), "V": (2, 1), "W": (3, 1), "Y": (4, 1), "S1": (1, 0), "S2": (3, 0)}
    fig, ax = plt.subplots(figsize=(5.4, 2.9))
    draw_dag(ax, pos, G17_8, labels={v: _tex(v) for v in pos})
    _limits(ax, pos, 0.4)
    ax.set_ylim(-1.75, 1.4)
    for i, W in enumerate([[], ["S1", "S2"], ["S1", "S2", "V"]]):
        s = d_separated(G17_8, ["X"], ["Y"], W)
        ax.text(2.0, -0.6 - 0.42 * i, ("d-separated: " if s else "d-connected:  ") + _stmt(["X"], ["Y"], W, s),
                ha="center", fontsize=10.5, va="center", color=GREEN if s else RED)
    savefig(fig, CH, "fig17-8", out_dir)


def fig_17_9(out_dir=None):
    """Figure 17.9 (Example 17.11) with illustrative numbers: explaining away."""
    pr = aliens_probs()
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 2.7), gridspec_kw=dict(width_ratios=[1, 1.35]))
    pos = {"aliens": (0, 1), "forgot watch": (2.2, 1), "late": (1.1, 0)}
    draw_dag(axes[0], pos, G17_9, box=True, fs=10, observed=["late"])
    _limits(axes[0], pos, 0.85, 0.45)
    ax = axes[1]
    labs = ["P(aliens)", "P(aliens | late)", "P(aliens | late,\nforgot watch)", "P(aliens | late,\nwatch was set)"]
    vals = [pr["prior"], pr["late"], pr["late_forgot"], pr["late_set"]]
    y = np.arange(4)[::-1]
    ax.barh(y, vals, color=[GREY, RED, BLUE, PURPLE], height=0.6)
    for yi, v in zip(y, vals):
        ax.text(v + 0.004, yi, "%.4f" % v, va="center", fontsize=9)
    ax.set_yticks(y)
    ax.set_yticklabels(labs, fontsize=8.5)
    ax.set_xlim(0, max(vals) * 1.35)
    ax.set_xlabel("probability")
    ax.set_title("explaining away (illustrative numbers)", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig17-9", out_dir)


def fig_17_10(out_dir=None):
    """Figure 17.10, and the graph after the intervention 'set Y = y' (arrows into Y removed)."""
    fig, axes = plt.subplots(1, 2, figsize=(6.4, 2.0))
    pos = {"X": (0, 0), "Y": (1, 0), "Z": (2, 0)}
    draw_dag(axes[0], pos, G17_10, curved={("X", "Z"): -0.45})
    axes[0].set_title(r"$f(x)\,f(y\mid x)\,f(z\mid x,y)$", fontsize=10)
    mut = {"X": [], "Y": [], "Z": ["X", "Y"]}
    draw_dag(axes[1], pos, mut, curved={("X", "Z"): -0.45}, labels={"Y": "$y$"}, node_colours={"Y": "#ffe2b3"})
    axes[1].set_title(r"set $Y=y$:  $f(x)\,f(z\mid x,y)$", fontsize=10)
    for ax in axes:
        _limits(ax, pos, 0.4)
        ax.set_ylim(-0.45, 0.85)
    savefig(fig, CH, "fig17-10", out_dir)


def fig_17_11(out_dir=None):
    """Figure 17.11: randomised study; observational study with measured or unmeasured confounders."""
    fig, axes = plt.subplots(1, 3, figsize=(7.2, 2.2))
    pos = {"Z": (1, 0.9), "X": (0, 0), "Y": (2, 0)}
    designs = [({"Z": [], "X": [], "Y": ["X", "Z"]}, ["Z"], "randomised study"),
               ({"Z": [], "X": ["Z"], "Y": ["X", "Z"]}, [], "observational,\nconfounder measured"),
               ({"Z": [], "X": ["Z"], "Y": ["X", "Z"]}, ["Z"], "observational,\nconfounder unmeasured")]
    for ax, (g, lat, t) in zip(axes, designs):
        draw_dag(ax, pos, g, latent=lat)
        _limits(ax, pos, 0.4)
        ax.set_ylim(-0.45, 1.35)
        ax.set_title(t, fontsize=9.5)
    savefig(fig, CH, "fig17-11", out_dir)


def fig_17_12(out_dir=None):
    """Figure 17.12 (Exercise 17.7): X -> Y_j <- Z_j, with the verdict X indep Z_j."""
    pos = {"X": (0, 0), "Y1": (1, 0), "Z1": (2, 0), "Y2": (0, -1), "Z2": (0, -2), "Y3": (-1, 0), "Z3": (-2, 0),
           "Y4": (0, 1), "Z4": (0, 2)}
    fig, ax = plt.subplots(figsize=(3.6, 3.9))
    draw_dag(ax, pos, G17_12, labels={v: _tex(v) for v in pos})
    _limits(ax, pos, 0.4)
    ok = all(d_separated(G17_12, ["X"], ["Z%d" % j], []) for j in range(1, 5))
    ax.set_ylim(-2.95, 2.4)
    ax.text(0, -2.75, r"$X %s Z_j,\ j=1,\dots,4$" % (IND if ok else NIND), fontsize=10.5, ha="center",
            color=GREEN if ok else RED)
    savefig(fig, CH, "fig17-12", out_dir)


# =========================================================================== supplementary figures
def fig_17_s1(out_dir=None):
    """Exercise 17.8: conditioning against intervening, by simulation, as the number of runs grows."""
    ex = binary_scm_exact(EX17_8)
    N = 100000
    rng = np.random.default_rng(178)
    pX, pY, pZ = binary_scm_probs(EX17_8)
    pZ = np.array(pZ)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.0))
    for rep, col in zip(range(3), [RED, BLUE, GREEN]):
        x = (rng.random(N) < pX).astype(int)
        y = (rng.random(N) < np.where(x == 1, pY[1], pY[0])).astype(int)
        z = (rng.random(N) < pZ[x, y]).astype(int)
        with np.errstate(invalid="ignore", divide="ignore"):
            c1 = np.cumsum(z * y) / np.cumsum(y)
        xi = (rng.random(N) < pX).astype(int)
        z1 = (rng.random(N) < pZ[xi, 1]).astype(int)
        d1 = np.cumsum(z1) / np.arange(1, N + 1)
        k = np.unique(np.round(np.logspace(0, 5, 300)).astype(int)) - 1
        axes[0].plot(k + 1, c1[k], color=col, lw=1.0)
        axes[1].plot(k + 1, d1[k], color=col, lw=1.0)
    for ax, v, t in [(axes[0], ex["cond"][1], r"(a) observe: $\widehat P(Z=1\mid Y=1)$"),
                     (axes[1], ex["do"][1], r"(b) intervene: $\widehat P(Z=1\mid \mathrm{set}\ Y=1)$")]:
        ax.axhline(v, color="k", ls="--", lw=1)
        ax.axhline(ex["do"][1] if ax is axes[0] else ex["cond"][1], color=GREY, ls=":", lw=1)
        ax.set_xscale("log")
        ax.set_ylim(0.4, 1.0)
        ax.set_xlabel("number of simulated runs N")
        ax.set_title(t, fontsize=10)
        ax.text(1.3, v + 0.02, "%.4f" % v, fontsize=9)
    axes[0].set_ylabel("running estimate")
    savefig(fig, CH, "fig17-S1", out_dir)


def fig_17_s2(out_dir=None):
    """Exercise 17.9: regression of Z on Y against the causal line, and the correlation as beta varies."""
    a, b, g = 1.0, 0.5, -1.5
    rng = np.random.default_rng(179)
    n = 400
    x = rng.standard_normal(n)
    y = a * x + rng.standard_normal(n)
    z = b * y + g * x + rng.standard_normal(n)
    m = gauss_scm_moments(a, b, g)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2))
    ax = axes[0]
    ax.scatter(y, z, s=6, color=GREY, alpha=0.6)
    t = np.linspace(-4, 4, 50)
    ax.plot(t, m["slope"] * t, color=RED, label=r"$E(Z\mid Y=y)$, slope %.2f" % m["slope"])
    ax.plot(t, b * t, color=BLUE, label=r"$E(Z\mid Y:=y)$, slope %.2f" % b)
    ax.set_xlabel("y")
    ax.set_ylabel("z")
    ax.legend(fontsize=8.5, loc="upper left")
    ax.set_title(r"(a) $\alpha=%g,\ \beta=%g,\ \gamma=%g$" % (a, b, g), fontsize=10)
    ax = axes[1]
    bs = np.linspace(-2, 2, 401)
    ax.plot(bs, [gauss_scm_moments(a, bb, g)["rho"] for bb in bs], color=RED, label="observational")
    ax.plot(bs, [gauss_scm_moments(a, bb, g, True)["rho"] for bb in bs], color=BLUE, label="Y randomised")
    ax.axhline(0, color="k", lw=0.6)
    ax.axvline(0, color="k", lw=0.6, ls=":")
    b0 = -g * a / (a * a + 1)
    ax.axvline(b0, color=RED, lw=0.8, ls="--")
    ax.text(b0 + 0.05, -0.85, r"$\rho=0$ at $\beta=%.2f$" % b0, color=RED, fontsize=8.5)
    ax.set_xlabel(r"causal effect $\beta$ of Y on Z")
    ax.set_ylabel(r"corr$(Y,Z)$")
    ax.legend(fontsize=8.5, loc="lower right")
    ax.set_title(r"(b) $\alpha=%g,\ \gamma=%g$" % (a, g), fontsize=10)
    savefig(fig, CH, "fig17-S2", out_dir)


def fig_17_s3(out_dir=None):
    """Exercise 17.6: true cell probabilities, the DAG MLE and 95% bootstrap intervals."""
    r = ex6_bootstrap()
    th, mle, lo, hi = (r[k].ravel() for k in ("theta", "mle", "lo", "hi"))
    sat = r["saturated"].ravel()
    labels = ["%d%d%d" % c for c in itertools.product(range(2), range(2), range(3))]
    fig, ax = plt.subplots(figsize=(8.2, 3.0))
    xs = np.arange(12)
    ax.vlines(xs, lo, hi, color=BLUE, lw=2.5, alpha=0.5, label="95% bootstrap interval")
    ax.plot(xs, mle, "o", color=BLUE, ms=5, label="MLE under the DAG")
    ax.plot(xs + 0.18, sat, "s", color=ORANGE, ms=4, label="cell frequency (no DAG)")
    ax.plot(xs, th, "_", color=RED, ms=16, mew=2, label="true value")
    ax.set_xticks(xs)
    ax.set_xticklabels([r"$\theta_{%s}$" % s for s in labels])
    ax.set_ylabel("probability")
    ax.legend(fontsize=8.5, ncol=2, loc="upper left")
    ax.set_ylim(0, max(hi) * 1.35)
    savefig(fig, CH, "fig17-S3", out_dir)


def fig_17_s4(out_dir=None):
    """Unfaithfulness: in X -> Y -> Z, X -> Z the marginal correlation of X and Z vanishes when the two
    paths cancel, gamma = -alpha beta, although the graph has an edge X -> Z."""
    a, b = 0.8, 0.9
    gs = np.linspace(-2, 1.5, 401)

    def rho(g):
        vy = a * a + 1
        cxz = g + a * b
        vz = b * b * vy + g * g + 2 * a * b * g + 1
        return cxz / math.sqrt(vz)

    def prho(g):
        # partial correlation of X and Z given Y
        S = np.array([[1, a, g + a * b], [a, a * a + 1, b * (a * a + 1) + g * a],
                      [g + a * b, b * (a * a + 1) + g * a, b * b * (a * a + 1) + g * g + 2 * a * b * g + 1]])
        P = np.linalg.inv(S)
        return -P[0, 2] / math.sqrt(P[0, 0] * P[2, 2])
    fig, ax = plt.subplots(figsize=(5.6, 3.0))
    ax.plot(gs, [rho(g) for g in gs], color=RED, label=r"corr$(X,Z)$")
    ax.plot(gs, [prho(g) for g in gs], color=BLUE, label=r"partial corr$(X,Z\mid Y)$")
    ax.axhline(0, color="k", lw=0.6)
    ax.axvline(-a * b, color=RED, ls="--", lw=0.8)
    ax.axvline(0, color=BLUE, ls=":", lw=0.8)
    ax.text(-a * b - 0.05, 0.62, r"$\gamma=-\alpha\beta$", color=RED, fontsize=9, ha="right")
    ax.set_xlabel(r"direct effect $\gamma$ of X on Z")
    ax.set_title(r"$Y=\alpha X+\epsilon_1,\ Z=\beta Y+\gamma X+\epsilon_2$, $\alpha=%g,\ \beta=%g$" % (a, b), fontsize=10)
    ax.legend(fontsize=8.5, loc="lower right")
    savefig(fig, CH, "fig17-S4", out_dir)


def structure_selection_rate(truth, nodes, cpt_p1, ns, reps, seed, crit=3):
    """Fraction of simulated data sets for which the best-scoring DAG (BIC by default) lies in the true
    Markov equivalence class; cpt_p1[v] is a list of P(v=1 | configuration)."""
    rng = np.random.default_rng(seed)
    cpts = {}
    for v in nodes:
        k = len(truth[v])
        p1 = np.zeros((2,) * k)
        for cfg in range(2 ** k):
            p1[tuple((cfg >> t) & 1 for t in range(k))] = cpt_p1[v][cfg]
        cpts[v] = np.stack([1 - p1, p1], axis=-1)
    dags = all_dags(nodes)
    key = equivalence_key(truth)
    intrue = np.array([equivalence_key(d) == key for d in dags])
    rates = []
    for n in ns:
        hit = 0
        for _ in range(reps):
            X = sample_dag(truth, cpts, n, rng)
            sc = dag_scores(dags, nodes, counts_from_data(X), n)
            best = max(range(len(dags)), key=lambda i: sc[i][crit])
            hit += intrue[best]
        rates.append(hit / reps)
    return np.array(rates)


S5_TRUTHS = {
    "collider X -> Z <- Y": ({"X": [], "Y": [], "Z": ["X", "Y"]}, {"X": [0.5], "Y": [0.5], "Z": [0.2, 0.5, 0.5, 0.8]}),
    "chain X -> Z -> Y": ({"X": [], "Y": ["Z"], "Z": ["X"]}, {"X": [0.5], "Y": [0.35, 0.65], "Z": [0.35, 0.65]}),
}
S5_NS = [25, 50, 100, 200, 400, 800, 1600, 3200]


def fig_17_s5(out_dir=None):
    """Section 17.6: (a) the maximised log-likelihood and BIC of all 25 DAGs on three nodes for one data
    set, grouped by equivalence class; (b) how often BIC picks the true class as n grows."""
    nodes = ["X", "Y", "Z"]
    truth, p1 = S5_TRUTHS["collider X -> Z <- Y"]
    dags = all_dags(nodes)
    cls = equivalence_classes(dags)
    keys = sorted(cls, key=lambda k: (len(k[0]), len(k[1]), sorted(map(sorted, k[0]))))
    rng = np.random.default_rng(1705)
    cpts = {}
    for v in nodes:
        k = len(truth[v])
        q = np.zeros((2,) * k)
        for cfg in range(2 ** k):
            q[tuple((cfg >> t) & 1 for t in range(k))] = p1[v][cfg]
        cpts[v] = np.stack([1 - q, q], axis=-1)
    n = 2000
    X = sample_dag(truth, cpts, n, rng)
    sc = dag_scores(dags, nodes, counts_from_data(X), n)
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 3.3), gridspec_kw=dict(width_ratios=[1.35, 1]))
    ax = axes[0]
    tk = equivalence_key(truth)
    for ci, k in enumerate(keys):
        for d in cls[k]:
            i = dags.index(d)
            col = RED if k == tk else BLUE
            ax.plot(ci, sc[i][3], "o", color=col, ms=5, alpha=0.8)
            ax.plot(ci, sc[i][0], "_", color=GREY, ms=9)
    ax.set_xticks(range(len(keys)))
    ax.set_xticklabels([str(len(cls[k])) for k in keys], fontsize=8)
    ax.set_xlabel("equivalence class (label: number of DAGs in it)")
    ax.set_ylabel("log-likelihood (grey), BIC (dots)")
    ax.set_title("(a) all 25 DAGs, n = %d, truth X -> Z <- Y (red)" % n, fontsize=9.5)
    ax = axes[1]
    for (name, (g, p)), col in zip(S5_TRUTHS.items(), [RED, BLUE]):
        rates = structure_selection_rate(g, nodes, p, S5_NS, 200, 99)
        ax.plot(S5_NS, rates, "o-", color=col, label="truth: " + name)
    ax.set_xscale("log")
    ax.set_ylim(0, 1.03)
    ax.set_xlabel("sample size n")
    ax.set_ylabel("P(BIC picks the true class)")
    ax.legend(fontsize=8, loc="lower right")
    ax.set_title("(b) 200 data sets per n", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig17-S5", out_dir)


def mec_counts(kmax=5):
    """Numbers of DAGs and of Markov equivalence classes on k = 1..kmax labelled nodes, by enumeration."""
    out = []
    for k in range(1, kmax + 1):
        nodes = [str(i) for i in range(k)]
        dags = all_dags(nodes)
        out.append((k, len(dags), len(equivalence_classes(dags))))
    return out


def fig_17_s6(out_dir=None):
    """Section 17.6: the number of DAGs grows super-exponentially; equivalence classes about 3.7 times fewer."""
    path = os.path.join(CACHE_DIR, "ch17_mec_counts.npy")
    if os.path.exists(path):
        mc = [tuple(r) for r in np.load(path).tolist()]
    else:
        mc = mec_counts(5)
        os.makedirs(CACHE_DIR, exist_ok=True)
        np.save(path, np.array(mc))
    ks = np.arange(1, 11)
    nd = [robinson_count(k) for k in ks]
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.0))
    ax = axes[0]
    ax.semilogy(ks, nd, "o-", color=RED, label="DAGs (Robinson's recursion)")
    ax.semilogy(ks, [2.0 ** (k * (k - 1) / 2) for k in ks], "s--", color=GREY, ms=4, label=r"$2^{k(k-1)/2}$ undirected graphs")
    ax.semilogy([r[0] for r in mc], [r[2] for r in mc], "^-", color=BLUE, label="equivalence classes (enumerated)")
    ax.set_xlabel("number of nodes k")
    ax.set_ylabel("count")
    ax.legend(fontsize=8)
    ax.set_title("(a) how many DAGs?", fontsize=10)
    ax = axes[1]
    ax.plot([r[0] for r in mc], [r[1] / r[2] for r in mc], "o-", color=PURPLE)
    for r in mc:
        ax.text(r[0], r[1] / r[2] + 0.08, "%d/%d" % (r[1], r[2]), ha="center", fontsize=8)
    ax.set_xlabel("number of nodes k")
    ax.set_ylabel("DAGs per equivalence class")
    ax.set_ylim(0.8, 4.0)
    ax.set_title("(b) average class size", fontsize=10)
    fig.tight_layout()
    savefig(fig, CH, "fig17-S6", out_dir)


FIGURES = {"17.1": fig_17_1, "17.2": fig_17_2, "17.3": fig_17_3, "17.4": fig_17_4, "17.5": fig_17_5,
           "17.6": fig_17_6, "17.7": fig_17_7, "17.8": fig_17_8, "17.9": fig_17_9, "17.10": fig_17_10,
           "17.11": fig_17_11, "17.12": fig_17_12, "17.S1": fig_17_s1, "17.S2": fig_17_s2, "17.S3": fig_17_s3,
           "17.S4": fig_17_s4, "17.S5": fig_17_s5, "17.S6": fig_17_s6}

if __name__ == "__main__":
    common.run(FIGURES, CH)
