"""Murphy (2023), Chapter 30: Graph learning (book pp. 1043-1045 and Supplement Chapter 30, pp. 227-266).

Companion code for Chapter 30 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft). Written from scratch with numpy, scipy, scikit-learn (only for
the l1-penalised logistic regressions of Figure S30.21 and as a cross-check), networkx (only for the
cross-check of graph routines) and matplotlib, to be read next to the lecture notes
(../ch30-graph-learning.html). Every algorithm of the chapter is implemented by hand and confirmed
against a library routine where one exists.

Methods
* Latent variable models for graphs (S30.1): the stochastic block model with collapsed Gibbs sampling
  (sample_sbm, sbm_log_marginal, sbm_gibbs), the mixed membership model with a collapsed Gibbs sampler
  over the pairwise role indicators (mmsb_gibbs), block patterns of Figure S30.3.
* Trees (S30.2): the Chow-Liu algorithm (mutual_info_matrix, kruskal, chow_liu), maximum weight forests,
  the matrix-tree theorem (matrix_tree_sum, tree_edge_marginals).
* DAGs (S30.3): d-separation, Markov equivalence and the CPDAG (d_separated, markov_equivalent, cpdag),
  Robinson's recurrence (count_dags), the BDeu score and exact posterior over all DAGs on five
  nodes (bdeu_local, dag_posterior), greedy hill climbing (hill_climb), the PC algorithm with an oracle
  or Fisher-z tests (pc), the NOTEARS acyclicity constraint (notears_h, notears), latent-variable scores:
  BIC, Cheeseman-Stutz and variational Bayes against the exact marginal likelihood (latent_class_*).
* Undirected graphs (S30.4): the Gaussian MLE for a given graph and the graphical lasso (ggm_mle,
  glasso), a dependency network (dependency_network) and a sparse binary Markov network by pseudo-likelihood
  (ising_pl_lasso).
* Causal DAGs (S30.5): additive noise models with an HSIC test (anm_direction), information-geometric causal
  inference (igci_slope, igci_entropy), interventional data (bdeu_two_node).

Figures reproduced: 30.1 (graphical lasso on the flow cytometry data), S30.2, S30.3, S30.5, S30.8, S30.10 and
S30.11, S30.12, S30.13, S30.15, S30.21, S30.22, S30.23, S30.24. Own figures: x30.1 (faithfulness), x30.2
(marginal likelihood approximations), x30.3 (NOTEARS), x30.4 (interventions).

Skipped figures, with reasons: Figure S30.1 (a hand-drawn directed graph; its content is the adjacency matrix
of S30.2), S30.4 (graphical models of the SBM and the mixed membership SBM, diagrams), S30.6 and S30.7
(the infinite relational model on the Unified Medical Language System and on the 1965 political data: the data
are not available; the model is described in the notes), S30.9 (a three-node diagram; its content is the
covariance computed for x30.1), S30.14 (the three Meek orientation rules, a diagram; the rules are
implemented in cpdag and used for S30.15), S30.16 (the fitted network with a hidden variable of the college
plans data, whose data are not available: its content is reproduced on simulated data in S30.12 and the
scores of x30.2), S30.17 to S30.20 (latent tree models of the newsgroups data and Google's Rephil: diagrams of
very large learned networks).

Data. The covariance matrix of the flow cytometry data of Sachs et al. (2005; 7466 cells, 11 proteins)
is read from ../data/ch30-sachs.json. The 20 newsgroups binary bag-of-words matrix (4 families, 100 words) is the
one built in the Chapter 5 module (stand-in for the book's 16 242 x 100 matrix); the Sampson monks, the college
plans data and the political and medical relational data sets are not available and are replaced by simulations
from the models of the text (stated in each caption).
"""
import itertools
import json
import os
import sys
import time

import numpy as np
from scipy import special, stats

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig, panel_grid, panel_label  # noqa: E402

CH = 30
CACHE_DIR = os.path.join(HERE, "cache", "ch30")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)


# =========================================================================== graph utilities (S30.3.1 to S30.3.2)
def is_dag(A):
    """True if the 0/1 matrix A (A[i, j] = 1 for i -> j) has no directed cycle."""
    A = np.array(A, dtype=bool)
    n = len(A)
    indeg = A.sum(0).astype(int)
    stack = [i for i in range(n) if indeg[i] == 0]
    seen = 0
    indeg = indeg.copy()
    while stack:
        i = stack.pop()
        seen += 1
        for j in np.nonzero(A[i])[0]:
            indeg[j] -= 1
            if indeg[j] == 0:
                stack.append(j)
    return seen == n


def parents(A, t):
    return tuple(int(i) for i in np.nonzero(np.asarray(A)[:, t])[0])


def ancestors(A, nodes):
    """The set of nodes in `nodes` together with all their ancestors."""
    A = np.asarray(A)
    out = set(nodes)
    stack = list(nodes)
    while stack:
        v = stack.pop()
        for u in np.nonzero(A[:, v])[0]:
            if int(u) not in out:
                out.add(int(u))
                stack.append(int(u))
    return out


def d_separated(A, x, y, Z=()):
    """d-separation of x and y given the set Z in the DAG A, by the moral ancestral graph criterion:
    keep the ancestors of {x, y} and Z, marry the parents of every node, drop the directions, delete Z and
    ask whether x and y are still connected."""
    A = np.asarray(A)
    Z = set(Z)
    keep = sorted(ancestors(A, {x, y} | Z))
    M = np.zeros((len(A), len(A)), dtype=bool)
    for v in keep:
        pa = [u for u in np.nonzero(A[:, v])[0]]
        for u in pa:
            M[u, v] = M[v, u] = True
        for u, w in itertools.combinations(pa, 2):
            M[u, w] = M[w, u] = True
    seen = {x}
    stack = [x]
    while stack:
        v = stack.pop()
        for u in np.nonzero(M[v])[0]:
            u = int(u)
            if u in Z or u in seen or u not in keep:
                continue
            seen.add(u)
            stack.append(u)
    return y not in seen


def skeleton(A):
    A = np.asarray(A, dtype=bool)
    return A | A.T


def v_structures(A):
    """The set of v-structures (a, c, b), a < b, a -> c <- b with a and b not adjacent."""
    A = np.asarray(A, dtype=bool)
    S = A | A.T
    out = set()
    for c in range(len(A)):
        pa = np.nonzero(A[:, c])[0]
        for a, b in itertools.combinations(pa, 2):
            if not S[a, b]:
                out.add((int(a), c, int(b)))
    return out


def markov_equivalent(A, B):
    """Theorem S30.3.1 (Verma and Pearl 1990): same skeleton and same v-structures."""
    return bool((skeleton(A) == skeleton(B)).all()) and v_structures(A) == v_structures(B)


def meek_closure(P):
    """Apply Meek's rules R1 to R3 until nothing changes. P[i, j] = 1 and P[j, i] = 0 is i -> j;
    P[i, j] = P[j, i] = 1 is an undirected edge."""
    P = np.array(P, dtype=int)
    n = len(P)
    changed = True
    while changed:
        changed = False
        adj = (P | P.T) > 0
        for b in range(n):
            for c in range(n):
                if b == c or not (P[b, c] and P[c, b]):
                    continue
                # R1: a -> b - c with a, c not adjacent  =>  b -> c
                for a in range(n):
                    if a != c and P[a, b] and not P[b, a] and not adj[a, c]:
                        P[c, b] = 0
                        changed = True
                        break
                if not P[c, b]:
                    continue
                # R2: b -> a -> c with b - c  =>  b -> c
                for a in range(n):
                    if P[b, a] and not P[a, b] and P[a, c] and not P[c, a]:
                        P[c, b] = 0
                        changed = True
                        break
                if not P[c, b]:
                    continue
                # R3: b - a1 -> c, b - a2 -> c, a1, a2 not adjacent, b - c  =>  b -> c
                nb = [a for a in range(n) if P[b, a] and P[a, b] and P[a, c] and not P[c, a]]
                done = False
                for a1, a2 in itertools.combinations(nb, 2):
                    if not adj[a1, a2]:
                        P[c, b] = 0
                        changed = True
                        done = True
                        break
                if done:
                    continue
    return P


def orient_vstructures(P0, sepset):
    """Orient a - c - b as a -> c <- b when a, b are not adjacent and c is not in sepset[(a, b)]."""
    P = np.array(P0, dtype=int)
    n = len(P)
    adj = (P0 | np.asarray(P0).T) > 0
    for c in range(n):
        nb = np.nonzero(adj[c])[0]
        for a, b in itertools.combinations(nb, 2):
            if not adj[a, b] and c not in sepset.get((int(a), int(b)), sepset.get((int(b), int(a)), ())):
                # a -> c: keep P[a, c], remove P[c, a] unless that edge is already oriented the other way
                for u in (a, b):
                    if P[u, c] and P[c, u]:
                        P[c, u] = 0
    return P


def cpdag(A):
    """The essential graph of the Markov equivalence class of the DAG A: the skeleton, with the edges of the
    v-structures oriented and Meek's rules closed."""
    A = np.asarray(A, dtype=int)
    S = (skeleton(A)).astype(int)
    P = S.copy()
    for (a, c, b) in v_structures(A):
        P[c, a] = 0
        P[c, b] = 0
    return meek_closure(P)


def count_dags(n):
    """Number of labelled DAGs on n nodes, Robinson's recurrence (30.31)."""
    f = [1]
    for m in range(1, n + 1):
        f.append(sum((-1) ** (i + 1) * special.comb(m, i, exact=True) * 2 ** (i * (m - i)) * f[m - i] for i in range(1, m + 1)))
    return f[n]


def all_dags(n):
    """All labelled DAGs on n nodes (as a list of 0/1 matrices): every topological order and every subset of
    the forward edges, with duplicates removed."""
    seen = set()
    out = []
    pairs = [(i, j) for i in range(n) for j in range(i + 1, n)]
    for perm in itertools.permutations(range(n)):
        for mask in range(1 << len(pairs)):
            A = np.zeros((n, n), dtype=np.uint8)
            for k, (i, j) in enumerate(pairs):
                if mask >> k & 1:
                    A[perm[i], perm[j]] = 1
            key = A.tobytes()
            if key not in seen:
                seen.add(key)
                out.append(A)
    return out


def equivalence_classes(dags):
    """Group DAGs by (skeleton, v-structures); returns a dict key -> list of indices."""
    cls = {}
    for k, A in enumerate(dags):
        key = (skeleton(A).tobytes(), tuple(sorted(v_structures(A))))
        cls.setdefault(key, []).append(k)
    return cls


# =========================================================================== PC algorithm (S30.3.5)
def pc(n, ci, max_level=None):
    """The (stable) PC algorithm. ci(a, b, S) returns True if a and b are judged independent given S.
    Returns (P, sepset, trace): P the CPDAG-like partially directed graph, sepset[(a, b)] the separating
    set found for each removed edge, trace the list of (level, removed_edge, S) in order."""
    adj = np.ones((n, n), dtype=bool)
    np.fill_diagonal(adj, False)
    sepset = {}
    trace = []
    level = 0
    while True:
        snap = adj.copy()
        if max(snap.sum(1)) - 1 < level:
            break
        for a in range(n):
            for b in range(a + 1, n):
                if not adj[a, b]:
                    continue
                found = False
                for x, y in ((a, b), (b, a)):
                    cand = [int(v) for v in np.nonzero(snap[x])[0] if v != y]
                    if len(cand) < level:
                        continue
                    for S in itertools.combinations(cand, level):
                        if ci(a, b, S):
                            adj[a, b] = adj[b, a] = False
                            sepset[(a, b)] = S
                            trace.append((level, (a, b), S))
                            found = True
                            break
                    if found:
                        break
        level += 1
        if max_level is not None and level > max_level:
            break
    P = orient_vstructures(adj.astype(int), sepset)
    return meek_closure(P), sepset, trace


def oracle_ci(A):
    return lambda a, b, S: d_separated(A, a, b, S)


def fisherz_ci(R, N, alpha=0.01):
    """Conditional independence test from the correlation matrix R of N Gaussian cases (Fisher z)."""
    def ci(a, b, S):
        idx = [a, b] + list(S)
        P = np.linalg.pinv(R[np.ix_(idx, idx)])
        r = -P[0, 1] / np.sqrt(P[0, 0] * P[1, 1])
        r = np.clip(r, -0.999999, 0.999999)
        z = 0.5 * np.log((1 + r) / (1 - r)) * np.sqrt(max(N - len(S) - 3, 1))
        return 2 * (1 - stats.norm.cdf(abs(z))) > alpha
    return ci


def sem_sample(W, N, rng, noise="gauss"):
    """Linear SEM x = W^T x + e with W[i, j] the weight of i -> j (a DAG): returns N x D samples."""
    D = len(W)
    E = rng.standard_normal((N, D)) if noise == "gauss" else rng.uniform(-np.sqrt(3), np.sqrt(3), (N, D))
    return E @ np.linalg.inv(np.eye(D) - W)


def shd_pdag(P, Q):
    """Structural Hamming distance between two partially directed graphs."""
    P = np.asarray(P)
    Q = np.asarray(Q)
    d = 0
    for i in range(len(P)):
        for j in range(i + 1, len(P)):
            if (P[i, j], P[j, i]) != (Q[i, j], Q[j, i]):
                d += 1
    return d


# =========================================================================== Bayesian scores for DAGs (S30.3.3, S30.3.4)
def counts_family(X, K, t, pa):
    """Counts N[c, k] of node t in state k with the parents `pa` in joint state c (X is N x D integers)."""
    Kt = K[t]
    if len(pa) == 0:
        return np.bincount(X[:, t], minlength=Kt).astype(float)[None, :]
    idx = np.zeros(len(X), dtype=np.int64)
    C = 1
    for p in pa:
        idx = idx * K[p] + X[:, p]
        C *= K[p]
    return np.bincount(idx * Kt + X[:, t], minlength=C * Kt).reshape(C, Kt).astype(float)


def bdeu_from_counts(Ntk, alpha):
    """Log BDeu local score (30.28) from a C x K count table: each cell has pseudo count alpha / (K C)."""
    C, Kt = Ntk.shape
    a_ck = alpha / (Kt * C)
    a_c = alpha / C
    Nc = Ntk.sum(1)
    return float((special.gammaln(a_c) - special.gammaln(a_c + Nc)).sum() + (special.gammaln(a_ck + Ntk) - special.gammaln(a_ck)).sum())


def bdeu_local(X, K, t, pa, alpha=5.0):
    return bdeu_from_counts(counts_family(X, K, t, tuple(sorted(pa))), alpha)


def bdeu_dag(X, K, A, alpha=5.0):
    return sum(bdeu_local(X, K, t, parents(A, t), alpha) for t in range(len(A)))


def bic_local(X, K, t, pa):
    """Log-likelihood minus (log N / 2) times the number of free parameters, for the family (t, pa)."""
    Nt = counts_family(X, K, t, tuple(sorted(pa)))
    Nc = Nt.sum(1, keepdims=True)
    with np.errstate(divide="ignore", invalid="ignore"):
        ll = np.where(Nt > 0, Nt * np.log(Nt / np.maximum(Nc, 1)), 0).sum()
    return float(ll - 0.5 * np.log(len(X)) * Nt.shape[0] * (K[t] - 1))


def dag_posterior(X, K, dags, alpha=5.0, allowed=None, local_cache=None):
    """Exact posterior over a list of DAGs under a uniform prior on the allowed ones (BDeu scores).
    allowed(A) -> bool gives the structural constraints. Returns (log scores, posterior)."""
    cache = {} if local_cache is None else local_cache
    n = len(K)
    out = np.full(len(dags), -np.inf)
    for k, A in enumerate(dags):
        if allowed is not None and not allowed(A):
            continue
        s = 0.0
        for t in range(n):
            pa = parents(A, t)
            key = (t, pa)
            if key not in cache:
                cache[key] = bdeu_local(X, K, t, pa, alpha)
            s += cache[key]
        out[k] = s
    post = np.exp(out - special.logsumexp(out))
    return out, post


def reach_matrix(A):
    R = np.array(A, dtype=bool)
    n = len(R)
    for k in range(n):
        R = R | (R[:, [k]] & R[[k], :])
    return R


def hill_climb(X, K, alpha=5.0, init=None, max_parents=4, max_iter=1000, verbose=False):
    """Greedy hill climbing over DAGs with the moves add, delete and reverse an edge, scored by BDeu.
    Because the score decomposes only the families of the (at most two) nodes touched by a move are rescored.
    Returns (A, score, number of moves)."""
    n = len(K)
    A = np.zeros((n, n), dtype=np.uint8) if init is None else np.array(init, dtype=np.uint8)
    cache = {}

    def loc(t, pa):
        key = (t, tuple(sorted(pa)))
        if key not in cache:
            cache[key] = bdeu_local(X, K, t, key[1], alpha)
        return cache[key]

    moves = 0
    while moves < max_iter:
        R = reach_matrix(A)
        cands = []
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if A[i, j]:
                    pa = set(parents(A, j))
                    cands.append((loc(j, pa - {i}) - loc(j, pa), "del", i, j))
                    pa_i = set(parents(A, i))
                    if len(pa_i) < max_parents:
                        d = loc(j, pa - {i}) - loc(j, pa) + loc(i, pa_i | {j}) - loc(i, pa_i)
                        cands.append((d, "rev", i, j))
                elif not A[j, i] and not R[j, i]:
                    pa = set(parents(A, j))
                    if len(pa) < max_parents:
                        cands.append((loc(j, pa | {i}) - loc(j, pa), "add", i, j))
        cands.sort(key=lambda c: -c[0])
        done = False
        for d, kind, i, j in cands:
            if d <= 1e-9:
                break
            B = A.copy()
            if kind == "add":
                B[i, j] = 1
            elif kind == "del":
                B[i, j] = 0
            else:
                B[i, j] = 0
                B[j, i] = 1
            if kind == "rev" and not is_dag(B):
                continue
            A = B
            done = True
            moves += 1
            break
        if not done:
            break
    score = sum(loc(t, parents(A, t)) for t in range(n))
    return A, score, moves


# =========================================================================== trees (S30.2)
def mutual_info_matrix(X):
    """Empirical pairwise mutual information (nats) between the columns of a 0/1 matrix."""
    X = X.astype(float)
    n, d = X.shape
    n11 = X.T @ X
    c1 = X.sum(0)
    n10 = c1[:, None] - n11
    n01 = c1[None, :] - n11
    n00 = n - n11 - n10 - n01
    M = np.zeros((d, d))
    for cnt, a, b in ((n11, c1[:, None], c1[None, :]), (n10, c1[:, None], n - c1[None, :]), (n01, n - c1[:, None], c1[None, :]), (n00, n - c1[:, None], n - c1[None, :])):
        with np.errstate(divide="ignore", invalid="ignore"):
            term = np.where(cnt > 0, cnt / n * np.log(cnt * n / (a * b)), 0)
        M += term
    np.fill_diagonal(M, 0)
    return M


def kruskal(W, positive_only=False):
    """Maximum weight spanning tree (forest when positive_only: edges with weight <= 0 are never used)
    of the complete graph with symmetric weights W, by Kruskal's algorithm with union-find.
    Returns the list of edges (i, j) in the order added."""
    n = len(W)
    parent = list(range(n))

    def find(a):
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a

    edges = sorted(((W[i, j], i, j) for i in range(n) for j in range(i + 1, n)), reverse=True)
    out = []
    for w, i, j in edges:
        if positive_only and w <= 0:
            break
        ri, rj = find(i), find(j)
        if ri != rj:
            parent[ri] = rj
            out.append((i, j))
            if len(out) == n - 1:
                break
    return out


def tree_loglik_per_case(X, edges):
    """Maximised log likelihood per case of the tree with the given edges (all marginals empirical):
    sum of node entropies (negated) plus the sum of edge mutual informations (30.12)-(30.13)."""
    p1 = X.mean(0)
    with np.errstate(divide="ignore", invalid="ignore"):
        negH = np.where(p1 > 0, p1 * np.log(p1), 0) + np.where(p1 < 1, (1 - p1) * np.log(1 - p1), 0)
    M = mutual_info_matrix(X)
    return float(negH.sum() + sum(M[i, j] for i, j in edges))


def tree_loglik_direct(X, edges, root=0):
    """The same log likelihood computed directly from p(x_root) prod p(x_t | x_parent), empirical conditionals."""
    n, d = X.shape
    adj = {i: [] for i in range(d)}
    for i, j in edges:
        adj[i].append(j)
        adj[j].append(i)
    seen = {root}
    order = [root]
    par = {root: None}
    for v in order:
        for u in adj[v]:
            if u not in seen:
                seen.add(u)
                par[u] = v
                order.append(u)
    ll = 0.0
    for v in order:
        if par[v] is None:
            p = X[:, v].mean()
            ll += np.where(X[:, v] == 1, np.log(p), np.log(1 - p)).sum()
        else:
            for a in (0, 1):
                sel = X[:, par[v]] == a
                if sel.sum() == 0:
                    continue
                p = X[sel, v].mean()
                for b, pb in ((1, p), (0, 1 - p)):
                    m = (X[sel, v] == b).sum()
                    if m:
                        ll += m * np.log(pb)
    return ll / n


def matrix_tree_sum(W):
    """Sum over all spanning trees of the product of the edge weights (symmetric W with zero diagonal):
    the determinant of the Laplacian with one row and column removed (Kirchhoff)."""
    L = np.diag(W.sum(1)) - W
    return float(np.linalg.det(L[1:, 1:]))


def tree_edge_marginals(W):
    """P((i, j) in T) under p(T) proportional to the product of the edge weights, from the inverse of the
    reduced Laplacian: W_ij * (effective resistance between i and j)."""
    n = len(W)
    L = np.diag(W.sum(1)) - W
    Linv = np.zeros((n, n))
    Linv[1:, 1:] = np.linalg.inv(L[1:, 1:])
    d = np.diag(Linv)
    R = d[:, None] + d[None, :] - 2 * Linv
    return W * R


def all_labelled_trees(n):
    """All n^(n-2) labelled trees on n nodes via Pruefer sequences, as lists of edges."""
    out = []
    for seq in itertools.product(range(n), repeat=n - 2):
        deg = [1] * n
        for v in seq:
            deg[v] += 1
        edges = []
        s = list(seq)
        for v in s:
            leaf = min(i for i in range(n) if deg[i] == 1)
            edges.append((min(leaf, v), max(leaf, v)))
            deg[leaf] -= 1
            deg[v] -= 1
        u, w = [i for i in range(n) if deg[i] == 1]
        edges.append((u, w))
        out.append(edges)
    return out


# =========================================================================== latent variables: scores (S30.3.8)
def lc_complete_logml(Nk, N1, alpha=1.0, a=1.0, b=1.0):
    """Exact log marginal likelihood of complete data of the latent class model (class k with weight pi_k,
    D conditionally independent binary features with Bernoulli parameter theta_dk), under Dirichlet(alpha)
    on pi and Beta(a, b) on every theta. Nk: class counts (K,), N1: counts of x_d = 1 in class k (D x K).
    Counts may be fractional (expected counts, Cheeseman-Stutz)."""
    K = len(Nk)
    N0 = Nk[None, :] - N1
    out = special.gammaln(K * alpha) - special.gammaln(K * alpha + Nk.sum()) + (special.gammaln(alpha + Nk) - special.gammaln(alpha)).sum()
    out += (special.betaln(a + N1, b + N0) - special.betaln(a, b)).sum()
    return float(out)


def lc_exact_logml(X, K=2, alpha=1.0):
    """log p(X) by summing the complete-data marginal likelihood over all K^N assignments of the latent classes."""
    N, D = X.shape
    assign = np.array(list(itertools.product(range(K), repeat=N)), dtype=np.int8)
    vals = np.empty(len(assign))
    Xf = X.astype(float)
    Hs = [(assign == k).astype(float) for k in range(K)]
    Nk = np.stack([h.sum(1) for h in Hs], 1)                         # (M, K)
    N1 = np.stack([h @ Xf for h in Hs], 2)                            # (M, D, K)
    Kk = K
    lg = special.gammaln(Kk * alpha) - special.gammaln(Kk * alpha + N)
    lg = lg + (special.gammaln(alpha + Nk) - special.gammaln(alpha)).sum(1)
    N0 = Nk[:, None, :] - N1
    lg = lg + (special.betaln(1 + N1, 1 + N0)).sum((1, 2))
    return float(special.logsumexp(lg))


def lc_em(X, K=2, iters=300, restarts=5, rng=None):
    """EM for the latent class model (maximum likelihood; the Dir(1) and Beta(1, 1) priors have MAP = MLE).
    Returns (pi, theta (D x K), responsibilities, log likelihood) of the best restart."""
    rng = np.random.default_rng(0) if rng is None else rng
    N, D = X.shape
    best = None
    for _ in range(restarts):
        r = rng.dirichlet(np.ones(K), size=N)
        for _ in range(iters):
            Nk = r.sum(0) + 1e-12
            pi = Nk / N
            th = np.clip((X.T @ r) / Nk, 1e-6, 1 - 1e-6)
            lp = np.log(pi)[None, :] + X @ np.log(th) + (1 - X) @ np.log(1 - th)
            r = np.exp(lp - special.logsumexp(lp, 1, keepdims=True))
        ll = float(special.logsumexp(lp, 1).sum())
        if best is None or ll > best[3]:
            best = (pi, th, r, ll)
    return best


def lc_bic(X, K=2, **kw):
    N, D = X.shape
    pi, th, r, ll = lc_em(X, K, **kw)
    return ll - 0.5 * np.log(N) * ((K - 1) + K * D)


def lc_cs(X, K=2, **kw):
    """Cheeseman-Stutz (30.41): log p(Dbar) + log p(D | theta) - log p(Dbar | theta), with Dbar the data filled in
    with expected counts at the EM estimate."""
    pi, th, r, ll = lc_em(X, K, **kw)
    Nk = r.sum(0)
    N1 = X.T @ r
    lbar = lc_complete_logml(Nk, N1)
    llbar = float((Nk * np.log(pi)).sum() + (N1 * np.log(th) + (Nk[None, :] - N1) * np.log(1 - th)).sum())
    return lbar + ll - llbar


def _kl_dir(a, b):
    return float(special.gammaln(a.sum()) - special.gammaln(a).sum() - special.gammaln(b.sum()) + special.gammaln(b).sum() + ((a - b) * (special.digamma(a) - special.digamma(a.sum()))).sum())


def lc_vb(X, K=2, iters=200, restarts=5, rng=None):
    """Variational Bayes EM (S30.3.8.4): q(pi) Dirichlet, q(theta_dk) Beta, q(z_n) discrete. Returns the best
    evidence lower bound over restarts (a lower bound on log p(X))."""
    rng = np.random.default_rng(1) if rng is None else rng
    N, D = X.shape
    best = -np.inf
    for s in range(restarts):
        if s == 0:
            r = lc_em(X, K, restarts=2, rng=np.random.default_rng(5))[2]
        else:
            r = rng.dirichlet(np.ones(K), size=N)
        prev = -np.inf
        for _ in range(iters):
            Nk = r.sum(0)
            N1 = X.T @ r
            a_pi = 1.0 + Nk
            b1 = 1.0 + N1
            b0 = 1.0 + Nk[None, :] - N1
            elogpi = special.digamma(a_pi) - special.digamma(a_pi.sum())
            e1 = special.digamma(b1) - special.digamma(b1 + b0)
            e0 = special.digamma(b0) - special.digamma(b1 + b0)
            lp = elogpi[None, :] + X @ e1 + (1 - X) @ e0
            lse = special.logsumexp(lp, 1)
            r = np.exp(lp - lse[:, None])
            kl = _kl_dir(a_pi, np.ones(K)) + sum(_kl_dir(np.array([b1[d, k], b0[d, k]]), np.ones(2)) for d in range(D) for k in range(K))
            elbo = float(lse.sum() - kl)
            if abs(elbo - prev) < 1e-9:
                break
            prev = elbo
        best = max(best, elbo)
    return best


# =========================================================================== undirected Gaussian graphs (S30.4)
def ggm_mle(S, A, tol=1e-12, maxit=2000):
    """Maximum likelihood covariance W of a Gaussian graphical model with adjacency matrix A (symmetric 0/1),
    by the modified regression algorithm: W_ij = S_ij on the edges and the diagonal, (W^-1)_ij = 0 elsewhere."""
    p = len(S)
    W = np.array(S, dtype=float)
    for _ in range(maxit):
        W_old = W.copy()
        for j in range(p):
            idx = [k for k in range(p) if k != j]
            nb = [k for k in range(p) if k != j and A[j, k]]
            beta = np.zeros(p - 1)
            if nb:
                W11 = W[np.ix_(idx, idx)]
                pos = [idx.index(k) for k in nb]
                beta[pos] = np.linalg.solve(W11[np.ix_(pos, pos)], S[nb, j])
            w12 = W[np.ix_(idx, idx)] @ beta
            W[idx, j] = w12
            W[j, idx] = w12
        if np.abs(W - W_old).max() < tol:
            break
    return W, np.linalg.inv(W)


def ggm_loglik(Omega, S):
    sign, ld = np.linalg.slogdet(Omega)
    return ld - float(np.trace(S @ Omega))


def _soft(x, t):
    return np.sign(x) * np.maximum(np.abs(x) - t, 0.0)


def glasso(S, lam, penalize_diag=True, tol=1e-10, maxit=500, W0=None):
    """The graphical lasso (30.50) by block coordinate descent on the covariance W (Friedman, Hastie and
    Tibshirani 2008): for each node a lasso regression of the node on the others with the current W as Gram
    matrix. J(Omega) = -log det Omega + tr(S Omega) + lam ||Omega||_1 (the diagonal is penalised when
    penalize_diag, as in the book). Returns dict(W, Theta, beta, sweeps)."""
    S = np.asarray(S, dtype=float)
    p = len(S)
    W = (S + lam * np.eye(p)) if (penalize_diag and W0 is None) else (S.copy() if W0 is None else W0.copy())
    if not penalize_diag and W0 is None:
        W = S.copy()
    B = np.zeros((p, p))                                   # B[j, k]: coefficient of node k in the regression of node j
    scale = np.abs(S - np.diag(np.diag(S))).mean() + 1e-12
    sweeps = 0
    for sweeps in range(1, maxit + 1):
        W_old = W.copy()
        for j in range(p):
            idx = np.array([k for k in range(p) if k != j])
            W11 = W[np.ix_(idx, idx)]
            s12 = S[idx, j]
            beta = B[j, idx].copy()
            for _ in range(200):
                b_old = beta.copy()
                for k in range(p - 1):
                    r = s12[k] - W11[k] @ beta + W11[k, k] * beta[k]
                    beta[k] = _soft(r, lam) / W11[k, k]
                if np.abs(beta - b_old).max() < 1e-13:
                    break
            B[j, idx] = beta
            w12 = W11 @ beta
            W[idx, j] = w12
            W[j, idx] = w12
        if np.abs(W - W_old).mean() < tol * scale:
            break
    Theta = np.zeros((p, p))
    for j in range(p):
        idx = np.array([k for k in range(p) if k != j])
        th = 1.0 / (W[j, j] - W[idx, j] @ B[j, idx])
        Theta[j, j] = th
        Theta[idx, j] = -B[j, idx] * th
    Theta = 0.5 * (Theta + Theta.T)
    return dict(W=W, Theta=Theta, beta=B, sweeps=sweeps)


def glasso_objective(Theta, S, lam, penalize_diag=True):
    sign, ld = np.linalg.slogdet(Theta)
    pen = np.abs(Theta).sum() if penalize_diag else np.abs(Theta - np.diag(np.diag(Theta))).sum()
    return -ld + float(np.trace(S @ Theta)) + lam * pen


def edges_of(Theta, tol=1e-8):
    p = len(Theta)
    return [(i, j) for i in range(p) for j in range(i + 1, p) if abs(Theta[i, j]) > tol]


def sachs_cov():
    d = json.load(open(os.path.join(DATA_OUT, "ch30-sachs.json")))
    return np.array(d["S"]), d["names"], d["N"]


# =========================================================================== sparse DAG learning: NOTEARS (S30.3.6)
def notears_h(W):
    """The smooth acyclicity measure of Zheng et al. (2018): tr exp(W o W) - d, zero iff W is a DAG."""
    from scipy.linalg import expm
    return float(np.trace(expm(W * W)) - len(W))


def notears_h_poly(W, alpha=None):
    """tr((I + alpha W o W)^d) - d, the polynomial form of (30.33) with W replaced by W o W (alpha = 1/d)."""
    d = len(W)
    alpha = 1.0 / d if alpha is None else alpha
    return float(np.trace(np.linalg.matrix_power(np.eye(d) + alpha * W * W, d)) - d)


def notears(X, lam=0.1, h_tol=1e-8, rho_max=1e16, max_dual=100, threshold=0.3):
    """Linear NOTEARS: min 1/(2N) ||X - XW||_F^2 + lam ||W||_1 subject to h(W) = 0, by the augmented Lagrangian
    with L-BFGS-B on W = W+ - W- (the book's (30.32) and (30.34))."""
    from scipy.linalg import expm
    from scipy.optimize import minimize
    N, d = X.shape
    X = X - X.mean(0)
    rho, alpha, h = 1.0, 0.0, np.inf
    w = np.zeros(2 * d * d)
    bnds = [(0, 0) if i == j else (0, None) for _ in range(2) for i in range(d) for j in range(d)]

    def unpack(w):
        return (w[:d * d] - w[d * d:]).reshape(d, d)

    def fg(w):
        W = unpack(w)
        R = X - X @ W
        loss = 0.5 / N * (R ** 2).sum()
        G = -1.0 / N * X.T @ R
        E = expm(W * W)
        hh = np.trace(E) - d
        obj = loss + 0.5 * rho * hh ** 2 + alpha * hh + lam * w.sum()
        Gh = E.T * W * 2
        Gs = G + (rho * hh + alpha) * Gh
        return obj, np.concatenate([(Gs + lam).ravel(), (-Gs + lam).ravel()])

    for _ in range(max_dual):
        while rho < rho_max:
            sol = minimize(fg, w, method="L-BFGS-B", jac=True, bounds=bnds)
            w_new = sol.x
            h_new = notears_h(unpack(w_new))
            if h_new > 0.25 * h:
                rho *= 10
            else:
                break
        w, h = w_new, h_new
        alpha += rho * h
        if h <= h_tol or rho >= rho_max:
            break
    W = unpack(w)
    Wt = W.copy()
    Wt[np.abs(Wt) < threshold] = 0
    return W, Wt


# =========================================================================== stochastic block models (S30.1)
def sample_sbm(sizes, eta, rng):
    """Directed graph from the stochastic block model with the given block sizes and block connection
    probabilities eta[a, b]. Returns (R, q) with R[i, j] = 1 for an edge i -> j (no self loops)."""
    q = np.repeat(np.arange(len(sizes)), sizes)
    P = np.asarray(eta)[q][:, q]
    R = (rng.random(P.shape) < P).astype(int)
    np.fill_diagonal(R, 0)
    return R, q


def sbm_log_marginal(R, q, K, a=1.0, b=1.0):
    """log p(R | q) with the connection probabilities eta_ab integrated out under Beta(a, b) priors."""
    Z = np.eye(K)[q]
    m = Z.T @ R @ Z
    nk = Z.sum(0)
    tot = np.outer(nk, nk) - np.diag(nk)
    return float((special.betaln(a + m, b + tot - m) - special.betaln(a, b)).sum())


def sbm_log_prior_q(q, K, alpha=1.0):
    nk = np.bincount(q, minlength=K)
    return float(special.gammaln(K * alpha) - special.gammaln(K * alpha + len(q)) + (special.gammaln(alpha + nk) - special.gammaln(alpha)).sum())


def sbm_gibbs(R, K, sweeps=60, restarts=10, rng=None):
    """Collapsed Gibbs sampling of the block labels (pi and eta integrated out); returns the best log joint
    state found over the restarts, as (q, log joint)."""
    rng = np.random.default_rng(0) if rng is None else rng
    n = len(R)
    best = (None, -np.inf)
    for _ in range(restarts):
        q = rng.integers(0, K, n)
        for _ in range(sweeps):
            for i in rng.permutation(n):
                lp = np.empty(K)
                for c in range(K):
                    q[i] = c
                    lp[c] = sbm_log_marginal(R, q, K) + sbm_log_prior_q(q, K)
                p = np.exp(lp - special.logsumexp(lp))
                q[i] = rng.choice(K, p=p)
        # finish with a greedy pass
        for _ in range(5):
            for i in range(n):
                lp = []
                for c in range(K):
                    q[i] = c
                    lp.append(sbm_log_marginal(R, q, K) + sbm_log_prior_q(q, K))
                q[i] = int(np.argmax(lp))
        lj = sbm_log_marginal(R, q, K) + sbm_log_prior_q(q, K)
        if lj > best[1]:
            best = (q.copy(), lj)
    return best


def best_permutation_accuracy(q_true, q_hat, K):
    best = 0.0
    for perm in itertools.permutations(range(K)):
        best = max(best, float((np.array(perm)[q_hat] == q_true).mean()))
    return best


def sample_mmsb(Pi, eta, rng):
    """Mixed membership stochastic block model: each ordered pair draws a sender role from pi_i and a
    receiver role from pi_j, and the edge from Bernoulli(eta[sender, receiver])."""
    n, K = Pi.shape
    R = np.zeros((n, n), dtype=int)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            a = rng.choice(K, p=Pi[i])
            b = rng.choice(K, p=Pi[j])
            R[i, j] = rng.random() < eta[a, b]
    return R


def mmsb_gibbs(R, K, sweeps=300, burn=100, alpha=0.1, a=1.0, b=1.0, rng=None, init=None):
    """Collapsed Gibbs sampler for the mixed membership stochastic block model: the state is the pair of roles
    (s_ij, r_ij) of every ordered pair; pi_i and eta_ab are integrated out. Returns the posterior mean of pi."""
    rng = np.random.default_rng(0) if rng is None else rng
    n = len(R)
    s = rng.integers(0, K, (n, n))
    r = rng.integers(0, K, (n, n))
    if init is not None:                       # start every pair at the hard labels of its two nodes
        s = np.repeat(np.asarray(init)[:, None], n, 1)
        r = np.repeat(np.asarray(init)[None, :], n, 0)
    cnt = np.zeros((n, K))
    m = np.zeros((K, K))
    tot = np.zeros((K, K))
    pairs = [(i, j) for i in range(n) for j in range(n) if i != j]
    for i, j in pairs:
        cnt[i, s[i, j]] += 1
        cnt[j, r[i, j]] += 1
        m[s[i, j], r[i, j]] += R[i, j]
        tot[s[i, j], r[i, j]] += 1
    acc = np.zeros((n, K))
    nacc = 0
    for sw in range(sweeps):
        for k in rng.permutation(len(pairs)):
            i, j = pairs[k]
            a0, b0 = s[i, j], r[i, j]
            cnt[i, a0] -= 1
            cnt[j, b0] -= 1
            m[a0, b0] -= R[i, j]
            tot[a0, b0] -= 1
            like = (a + m) / (a + b + tot) if R[i, j] else (b + tot - m) / (a + b + tot)
            P = np.outer(cnt[i] + alpha, cnt[j] + alpha) * like
            P = P.ravel() / P.sum()
            c = rng.choice(K * K, p=P)
            a1, b1 = divmod(c, K)
            s[i, j], r[i, j] = a1, b1
            cnt[i, a1] += 1
            cnt[j, b1] += 1
            m[a1, b1] += R[i, j]
            tot[a1, b1] += 1
        if sw >= burn:
            acc += (cnt + alpha) / (cnt + alpha).sum(1, keepdims=True)
            nacc += 1
    return acc / nacc


# =========================================================================== cause-effect pairs (S30.5.1)
def poly_resid(x, y, deg):
    """Residuals of the least squares polynomial regression of y on x (x standardised first)."""
    z = (x - x.mean()) / x.std()
    V = np.vander(z, deg + 1, increasing=True)
    coef, *_ = np.linalg.lstsq(V, y, rcond=None)
    return y - V @ coef


def _rbf_gram(x, sigma=None):
    d2 = (x[:, None] - x[None, :]) ** 2
    if sigma is None:
        med = np.median(np.sqrt(d2[np.triu_indices(len(x), 1)]))
        sigma = med if med > 0 else 1.0
    return np.exp(-d2 / (2 * sigma ** 2))


def hsic(x, y):
    """The (biased) Hilbert-Schmidt independence criterion tr(K H L H)/n^2 with Gaussian kernels whose widths are
    the median distances."""
    n = len(x)
    K = _rbf_gram(x)
    L = _rbf_gram(y)
    H = np.eye(n) - 1.0 / n
    return float(np.trace(K @ H @ L @ H) / n ** 2)


def hsic_pvalue(x, y, B=200, rng=None):
    rng = np.random.default_rng(0) if rng is None else rng
    n = len(x)
    K = _rbf_gram(x)
    L = _rbf_gram(y)
    H = np.eye(n) - 1.0 / n
    Kc = H @ K @ H
    obs = np.trace(Kc @ L) / n ** 2
    cnt = 0
    for _ in range(B):
        p = rng.permutation(n)
        cnt += np.trace(Kc @ L[np.ix_(p, p)]) / n ** 2 >= obs
    return obs, (cnt + 1) / (B + 1)


def anm_direction(x, y, deg=5, B=200, rng=None):
    """Additive noise model test (S30.5.1.3): regress each variable on the other with a polynomial of degree deg and
    measure the dependence of the residual on the regressor by HSIC. Returns dict with the HSIC statistics and
    p-values of x -> y and y -> x and the decision (the direction with the smaller statistic)."""
    x = (x - x.mean()) / x.std()
    y = (y - y.mean()) / y.std()
    rf = poly_resid(x, y, deg)
    rb = poly_resid(y, x, deg)
    hf, pf = hsic_pvalue(x, rf, B, rng)
    hb, pb = hsic_pvalue(y, rb, B, rng)
    return dict(hsic_xy=hf, p_xy=pf, hsic_yx=hb, p_yx=pb, decision="x->y" if hf < hb else "y->x")


def _unit(x):
    return (x - x.min()) / (x.max() - x.min())


def igci_slope(x, y):
    """Slope based IGCI (30.58): C_{X->Y} = mean of log |dy / dx| over neighbouring points in increasing x,
    after rescaling both variables to [0, 1]. Returns (C_xy, C_yx)."""
    x, y = _unit(x), _unit(y)
    def c(u, v):
        o = np.argsort(u)
        u, v = u[o], v[o]
        du, dv = np.diff(u), np.diff(v)
        ok = (du != 0) & (dv != 0)
        return float(np.mean(np.log(np.abs(dv[ok] / du[ok]))))
    return c(x, y), c(y, x)


def igci_entropy(x, y):
    """Entropy based IGCI: nearest-neighbour spacing estimates of the differential entropies of x and y rescaled to [0, 1];
    X -> Y is chosen when H(X) > H(Y)."""
    def h(u):
        u = np.sort(_unit(u))
        d = np.diff(u)
        d = d[d > 0]
        n = len(u)
        return float(special.digamma(n) - special.digamma(1) + np.mean(np.log(d)))
    return h(x), h(y)


# =========================================================================== two-node scores with interventions (S30.5.2)
def bdeu_two_node(X, Y, intervened_x=None, intervened_y=None, alpha=2.0):
    """Log BDeu scores of X -> Y and Y -> X for two binary variables. Cases where a variable was set by an
    intervention are left out of the counts of that variable's own family (S30.5.2)."""
    ix = np.zeros(len(X), bool) if intervened_x is None else intervened_x
    iy = np.zeros(len(X), bool) if intervened_y is None else intervened_y

    def fam(child, par, skip):
        keep = ~skip
        Nt = np.zeros((2, 2)) if par is not None else np.zeros((1, 2))
        for c in range(Nt.shape[0]):
            for k in range(2):
                sel = keep & (child == k)
                if par is not None:
                    sel = sel & (par == c)
                Nt[c, k] = sel.sum()
        return bdeu_from_counts(Nt, alpha)

    s_xy = fam(X, None, ix) + fam(Y, X, iy)
    s_yx = fam(Y, None, iy) + fam(X, Y, ix)
    return s_xy, s_yx


# =========================================================================== data sets
def load_news():
    """Binary bag-of-words of four newsgroup families (16 075 documents, 100 words), as in the Chapter 5 module."""
    path = os.path.join(HERE, "cache", "ch05_news_binary.npz")
    if not os.path.exists(path):
        import ch05_information_theory as c5
        c5.load_newsgroups_binary()
    z = np.load(path, allow_pickle=True)
    return z["X"].astype(int), [str(w) for w in z["words"]]


def dependency_network(X, Cs=(0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0, 2.0)):
    """Nodewise l1-penalised logistic regressions (S30.4.1); the penalty of every node is chosen by BIC.
    Returns the D x D weight matrix B (B[t, s] = weight of word s in the regression for word t)."""
    from sklearn.linear_model import LogisticRegression
    N, D = X.shape
    B = np.zeros((D, D))
    for t in range(D):
        Z = np.delete(X, t, 1).astype(float)
        best = (np.inf, None)
        for C in Cs:
            m = LogisticRegression(penalty="l1", solver="liblinear", C=C, tol=1e-5, max_iter=200).fit(Z, X[:, t])
            p = np.clip(m.predict_proba(Z)[:, 1], 1e-12, 1 - 1e-12)
            nll = -(X[:, t] * np.log(p) + (1 - X[:, t]) * np.log(1 - p)).sum()
            bic = 2 * nll + (np.count_nonzero(m.coef_) + 1) * np.log(N)
            if bic < best[0]:
                best = (bic, m.coef_.ravel().copy())
        B[t, np.delete(np.arange(D), t)] = best[1]
    return B


def ising_pl_lasso(X, lam, iters=300):
    """Sparse binary Markov network by l1-penalised pseudo-likelihood (S30.4.3; for binary nodes the group of an
    edge has one element, so the group lasso is the l1 penalty on the symmetric coupling matrix). x in {-1, +1},
    p(x_t | rest) = sigmoid(2 x_t (b_t + sum_s w_ts x_s)). FISTA on the average negative pseudo-log-likelihood."""
    Xs = 2.0 * X - 1.0
    N, D = Xs.shape
    W = np.zeros((D, D))
    b = np.zeros(D)
    L = float(np.linalg.eigvalsh(Xs.T @ Xs / N).max()) * 2 + 1.0
    Wy, by, tk = W.copy(), b.copy(), 1.0
    for _ in range(iters):
        H = Xs @ Wy + by
        G = -2.0 * Xs * special.expit(-2.0 * Xs * H)
        gW = Xs.T @ G / N
        gW = gW + gW.T
        np.fill_diagonal(gW, 0)
        gb = G.mean(0)
        W_new = _soft(Wy - gW / L, lam / L)
        np.fill_diagonal(W_new, 0)
        W_new = 0.5 * (W_new + W_new.T)
        b_new = by - gb / L
        tn = 0.5 * (1 + np.sqrt(1 + 4 * tk ** 2))
        Wy = W_new + (tk - 1) / tn * (W_new - W)
        by = b_new + (tk - 1) / tn * (b_new - b)
        W, b, tk = W_new, b_new, tn
    return W, b


# =========================================================================== drawing helpers
def circle_pos(n, r=1.0, phase=np.pi / 2):
    th = phase - 2 * np.pi * np.arange(n) / n
    return {i: (r * np.cos(t), r * np.sin(t)) for i, t in enumerate(th)}


def draw_graph(ax, pos, P, labels=None, node_color="white", edge_color="#333333", fs=9, rad=0.11, directed_color=None, lw=1.3, node_size=None):
    """Draw a partially directed graph: P[i, j] = 1 and P[j, i] = 0 is i -> j (arrow), both 1 an undirected line."""
    P = np.asarray(P)
    n = len(P)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if P[i, j] and P[j, i]:
                if i < j:
                    ax.plot([pos[i][0], pos[j][0]], [pos[i][1], pos[j][1]], color=edge_color, lw=lw, zorder=1, solid_capstyle="round")
            elif P[i, j]:
                ax.annotate("", xy=pos[j], xytext=pos[i], zorder=2,
                            arrowprops=dict(arrowstyle="-|>", color=directed_color or edge_color, lw=lw, shrinkA=rad * 70, shrinkB=rad * 70, mutation_scale=10))
    for i in range(n):
        if node_size is None:
            ax.text(pos[i][0], pos[i][1], labels[i] if labels else str(i), ha="center", va="center", fontsize=fs, zorder=3,
                    bbox=dict(boxstyle="circle,pad=0.25", fc=node_color, ec="#333333", lw=0.9))
        else:
            ax.scatter([pos[i][0]], [pos[i][1]], s=node_size, c=node_color, edgecolors="#333333", linewidths=0.5, zorder=3)
            if labels:
                ax.text(pos[i][0], pos[i][1], labels[i], ha="center", va="bottom", fontsize=fs, zorder=4)
    ax.set_aspect("equal")
    ax.axis("off")
    xs = [p[0] for p in pos.values()]
    ys = [p[1] for p in pos.values()]
    mx = 0.28 * (max(xs) - min(xs) + 1e-9) / 2 + 0.25
    my = 0.28 * (max(ys) - min(ys) + 1e-9) / 2 + 0.25
    ax.set_xlim(min(xs) - mx, max(xs) + mx)
    ax.set_ylim(min(ys) - my, max(ys) + my)


def dag_to_pdag(A):
    return np.asarray(A).astype(int)


# =========================================================================== figures
def fig_30_1(out=None):
    """Figure 30.1: graphical lasso graphs of the flow cytometry data for lambda = 36, 27, 7, 0."""
    S, names, N = sachs_cov()
    # layout: a circle in the order of the book's figure (signalling pathway roughly left to right)
    pos = circle_pos(11)
    fig, axes = panel_grid(1, 4, size=(2.9, 3.0))
    for ax, lam, lab in zip(axes[0], (36, 27, 7, 0), "abcd"):
        r = glasso(S, lam)
        E = edges_of(r["Theta"])
        P = np.zeros((11, 11), int)
        for i, j in E:
            P[i, j] = P[j, i] = 1
        draw_graph(ax, pos, P, names, fs=6.2, rad=0.07)
        ax.set_title(r"(%s) $\lambda=%d$: %d edges" % (lab, lam, len(E)), fontsize=9)
    return savefig(fig, CH, "fig30-1", out)


def _sbm_demo_graph():
    rng = np.random.default_rng(3)
    eta = np.array([[0.1, 0.9, 0.1], [0.1, 0.1, 0.9], [0.9, 0.1, 0.1]])
    R, q = sample_sbm([3, 4, 2], eta, rng)
    perm = rng.permutation(9)
    return R[np.ix_(perm, perm)], q[perm], eta


def fig_S30_2(out=None):
    """Figure S30.2: a nine-node directed graph from a ring-structured stochastic block model, its adjacency matrix in
    the original order, and the same matrix with the nodes sorted by the blocks found by collapsed Gibbs sampling."""
    R, q, eta = _sbm_demo_graph()
    qh, lj = sbm_gibbs(R, 3, sweeps=40, restarts=8, rng=np.random.default_rng(1))
    acc = best_permutation_accuracy(q, qh, 3)
    order = np.argsort(qh, kind="stable")
    Z = np.eye(3)[qh]
    m = Z.T @ R @ Z
    tot = np.outer(Z.sum(0), Z.sum(0)) - np.diag(Z.sum(0))
    eta_hat = (1 + m) / (2 + tot)
    fig, axes = panel_grid(1, 3, size=(2.9, 2.9))
    axes[0, 0].imshow(R, cmap="Greys", vmin=0, vmax=1)
    axes[0, 0].set_title("(a) original node order", fontsize=9)
    axes[0, 1].imshow(R[np.ix_(order, order)], cmap="Greys", vmin=0, vmax=1)
    cuts = np.cumsum(np.bincount(qh, minlength=3))[:-1] - 0.5
    for c in cuts:
        axes[0, 1].axhline(c, color=RED, lw=1)
        axes[0, 1].axvline(c, color=RED, lw=1)
    axes[0, 1].set_title("(b) sorted by inferred block (%.0f%% correct)" % (100 * acc), fontsize=9)
    for a in axes[0, :2]:
        a.set_xticks(range(9))
        a.set_yticks(range(9))
        a.set_xticklabels([str(i + 1) for i in (range(9) if a is axes[0, 0] else order)], fontsize=7)
        a.set_yticklabels([str(i + 1) for i in (range(9) if a is axes[0, 0] else order)], fontsize=7)
    # match estimated blocks to the true ones for the eta panel
    axes[0, 2].imshow(eta_hat, cmap="Greys", vmin=0, vmax=1)
    for a in range(3):
        for b in range(3):
            axes[0, 2].text(b, a, "%.2f" % eta_hat[a, b], ha="center", va="center", color="white" if eta_hat[a, b] > 0.5 else "black", fontsize=9)
    axes[0, 2].set_title(r"(c) posterior mean of $\eta_{ab}$", fontsize=9)
    axes[0, 2].set_xticks(range(3))
    axes[0, 2].set_yticks(range(3))
    axes[0, 2].set_xticklabels(["B%d" % (k + 1) for k in range(3)])
    axes[0, 2].set_yticklabels(["B%d" % (k + 1) for k in range(3)])
    return savefig(fig, CH, "figS30-2", out)


def sbm_patterns(K=4):
    """Block connection matrices of Figure S30.3: ring, dominance hierarchy, common cause, common effect."""
    ring = np.full((K, K), 0.04)
    for a in range(K):
        ring[a, (a + 1) % K] = 0.9
    hier = np.full((K, K), 0.04)
    for a in range(K):
        for b in range(a + 1, K):
            hier[a, b] = 0.9
    cc = np.full((K, K), 0.04)
    cc[0, 1:] = 0.9
    ce = np.full((K, K), 0.04)
    ce[1:, 0] = 0.9
    return [("ring", ring), ("dominance hierarchy", hier), ("common cause", cc), ("common effect", ce)]


def fig_S30_3(out=None):
    """Figure S30.3: adjacency matrices sampled from stochastic block models with four kinds of block structure."""
    rng = np.random.default_rng(4)
    fig, axes = panel_grid(2, 4, size=(2.5, 2.5))
    for k, (name, eta) in enumerate(sbm_patterns()):
        R, q = sample_sbm([6] * 4, eta, rng)
        ax = axes[0, k]
        ax.imshow(eta, cmap="Greys", vmin=0, vmax=1)
        ax.set_title(name, fontsize=9)
        ax.set_xticks(range(4))
        ax.set_yticks(range(4))
        ax.set_xticklabels("ABCD")
        ax.set_yticklabels("ABCD")
        ax = axes[1, k]
        ax.imshow(R, cmap="Greys", vmin=0, vmax=1)
        for c in (5.5, 11.5, 17.5):
            ax.axhline(c, color=RED, lw=0.7)
            ax.axvline(c, color=RED, lw=0.7)
        ax.set_xticks([])
        ax.set_yticks([])
    axes[0, 0].set_ylabel(r"$\eta$ (block to block)")
    axes[1, 0].set_ylabel("sampled graph, 24 nodes")
    return savefig(fig, CH, "figS30-3", out)


def mmsb_demo():
    """A stand-in for Sampson's monks: 24 nodes in three assortative groups, three of them with mixed membership."""
    rng = np.random.default_rng(11)
    K = 3
    Pi = np.zeros((24, K))
    for g in range(3):
        Pi[7 * g:7 * g + 7, g] = 0.94
        Pi[7 * g:7 * g + 7, [h for h in range(3) if h != g]] = 0.03
    Pi[21] = [0.48, 0.48, 0.04]
    Pi[22] = [0.04, 0.48, 0.48]
    Pi[23] = [0.48, 0.04, 0.48]
    eta = np.full((K, K), 0.04)
    np.fill_diagonal(eta, 0.8)
    R = sample_mmsb(Pi, eta, rng)
    return R, Pi, eta


def fig_S30_5(out=None):
    """Figure S30.5: the mixed membership stochastic block model on a network of 24 nodes with three mixed members."""
    R, Pi, eta = mmsb_demo()
    from sklearn.cluster import KMeans
    evals, evecs = np.linalg.eigh(R + R.T)
    init = KMeans(3, n_init=10, random_state=0).fit_predict(evecs[:, -3:])
    est = mmsb_gibbs(R, 3, sweeps=220, burn=80, rng=np.random.default_rng(2), init=init)
    perm = max(itertools.permutations(range(3)), key=lambda p: -np.abs(est[:, list(p)] - Pi).sum())
    est = est[:, list(perm)]
    err = np.abs(est - Pi).mean()
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.1), gridspec_kw=dict(width_ratios=[1, 1.9]))
    axes[0].imshow(R, cmap="Greys", vmin=0, vmax=1)
    axes[0].set_title("(a) who links to whom", fontsize=9)
    axes[0].set_xticks([])
    axes[0].set_yticks([])
    cols = [RED, BLUE, GREEN]
    bottom = np.zeros(24)
    for k in range(3):
        axes[1].bar(np.arange(1, 25), est[:, k], bottom=bottom, color=cols[k], width=0.8, label="role %d" % (k + 1))
        bottom += est[:, k]
    axes[1].plot(np.arange(1, 25), Pi[:, 0], "k_", ms=7, label="true weight of role 1")
    axes[1].set_xlabel("node")
    axes[1].set_ylabel(r"posterior mean of $\pi_i$")
    axes[1].set_title("(b) mixed membership (mean abs. error %.3f)" % err, fontsize=9)
    axes[1].legend(fontsize=7, ncol=2, loc="upper center", bbox_to_anchor=(0.5, -0.22))
    axes[1].set_xticks(range(1, 25, 2))
    return savefig(fig, CH, "figS30-5", out)


def fig_S30_8(out=None):
    """Figure S30.8: the Chow-Liu tree of the binary newsgroups data."""
    import networkx as nx
    X, words = load_news()
    MI = mutual_info_matrix(X)
    E = kruskal(MI)
    G = nx.Graph()
    G.add_nodes_from(range(len(words)))
    for i, j in E:
        G.add_edge(i, j, w=MI[i, j])
    pos = nx.kamada_kawai_layout(G)
    fig, ax = plt.subplots(figsize=(7.4, 7.0))
    for i, j in E:
        ax.plot([pos[i][0], pos[j][0]], [pos[i][1], pos[j][1]], color=GREY, lw=0.4 + 14 * MI[i, j], alpha=0.8, zorder=1)
    for i, w in enumerate(words):
        ax.text(pos[i][0], pos[i][1], w, ha="center", va="center", fontsize=5.6, zorder=3, bbox=dict(boxstyle="round,pad=0.12", fc="white", ec="#555555", lw=0.4))
    ax.axis("off")
    ax.set_title("Chow-Liu tree, 100 words, %d documents (line width = mutual information)" % len(X), fontsize=9)
    return savefig(fig, CH, "figS30-8", out)


DAGS_FIG = {
    "G1": [(0, 4), (0, 1), (2, 1), (1, 3)],
    "G2": [(0, 4), (0, 1), (2, 1), (3, 1)],
    "G3": [(4, 0), (0, 1), (2, 1), (1, 3)],
}
POS5 = {0: (0.0, 2.0), 2: (1.2, 2.0), 4: (-0.6, 1.0), 1: (0.6, 1.0), 3: (0.6, 0.0)}


def edges_to_A(n, edges):
    A = np.zeros((n, n), dtype=int)
    for i, j in edges:
        A[i, j] = 1
    return A


def fig_S30_10(out=None):
    """Figures S30.10 and S30.11: three DAGs (G1 and G3 are Markov equivalent, G2 is not) and their essential graphs."""
    labels = ["X%d" % (i + 1) for i in range(5)]
    fig, axes = panel_grid(2, 3, size=(2.7, 2.7))
    for k, (name, ed) in enumerate(DAGS_FIG.items()):
        A = edges_to_A(5, ed)
        draw_graph(axes[0, k], POS5, A, labels, fs=7.5, rad=0.1)
        axes[0, k].set_title("%s" % name, fontsize=10)
        draw_graph(axes[1, k], POS5, cpdag(A), labels, fs=7.5, rad=0.1)
        axes[1, k].set_title("essential graph of %s" % name, fontsize=9)
    return savefig(fig, CH, "figS30-10", out)


def fig_S30_11(out=None):
    """Figure S30.11: the three DAGs on X, Y, Z with X independent of Z given Y, and the PDAG that represents them."""
    pos = {0: (0, 0), 1: (1, 0), 2: (2, 0)}
    labs = ["X", "Y", "Z"]
    chains = [[(0, 1), (1, 2)], [(1, 0), (2, 1)], [(1, 0), (1, 2)], [(0, 1), (2, 1)]]
    names = ["X -> Y -> Z", "X <- Y <- Z", "X <- Y -> Z", "X -> Y <- Z"]
    fig, axes = panel_grid(1, 5, size=(2.2, 1.5))
    for k, ed in enumerate(chains):
        draw_graph(axes[0, k], pos, edges_to_A(3, ed), labs, fs=9, rad=0.12)
        axes[0, k].set_title(names[k], fontsize=8.5)
    draw_graph(axes[0, 4], pos, cpdag(edges_to_A(3, chains[0])), labs, fs=9, rad=0.12)
    axes[0, 4].set_title("PDAG of the first three", fontsize=8.5)
    return savefig(fig, CH, "figS30-11", out)


# college plans, simulated from the network of Figure S30.16 (binary variables; H is the hidden common cause)
CP_NAMES = ["SEX", "SES", "IQ", "PE", "CP"]


def college_cpts():
    pH1 = 0.37
    pSES = {0: 0.088, 1: 0.51}                                            # p(SES = high | H)
    pIQ = {(0, 0): 0.098, (0, 1): 0.22, (1, 0): 0.21, (1, 1): 0.49}       # p(IQ = high | PE, H)  keys (PE, H)
    pPE = {(0, 0): 0.32, (0, 1): 0.166, (1, 0): 0.86, (1, 1): 0.81}       # p(PE = high | SES, SEX) keys (SES, SEX) SEX 0 = male
    pCP = {(0, 0, 0): 0.011, (0, 0, 1): 0.170, (0, 1, 0): 0.124, (0, 1, 1): 0.53,
           (1, 0, 0): 0.093, (1, 0, 1): 0.39, (1, 1, 0): 0.24, (1, 1, 1): 0.84}      # keys (SES, IQ, PE)
    return pH1, pSES, pIQ, pPE, pCP


def college_data(N=10318, seed=0, with_hidden=False):
    rng = np.random.default_rng(seed)
    pH1, pSES, pIQ, pPE, pCP = college_cpts()
    sex = (rng.random(N) < 0.52).astype(int)                              # 1 = female (p(male) = 0.48)
    h = (rng.random(N) < pH1).astype(int)
    ses = (rng.random(N) < np.where(h == 1, pSES[1], pSES[0])).astype(int)
    pe = (rng.random(N) < np.array([pPE[(s, x)] for s, x in zip(ses, sex)])).astype(int)
    iq = (rng.random(N) < np.array([pIQ[(p, hh)] for p, hh in zip(pe, h)])).astype(int)
    cp = (rng.random(N) < np.array([pCP[(s, i, p)] for s, i, p in zip(ses, iq, pe)])).astype(int)
    X = np.stack([sex, ses, iq, pe, cp], 1)
    return (X, h) if with_hidden else X


def college_allowed(A):
    """The structural constraints of S30.3.3.4: SEX and SES have no parents, CP has no children."""
    return A[:, 0].sum() == 0 and A[:, 1].sum() == 0 and A[4].sum() == 0


def fig_S30_12(out=None):
    """Figure S30.12: the exact posterior over all 29 281 five-node DAGs for the college plans variables (simulated)."""
    X = college_data()
    K = [2] * 5
    dags = all_dags(5)
    ls, post = dag_posterior(X, K, dags, alpha=5.0, allowed=college_allowed)
    order = np.argsort(-post)
    pos = {0: (0.0, 2.0), 1: (1.0, 2.0), 3: (0.5, 1.0), 2: (-0.3, 0.2), 4: (1.3, 0.2)}
    fig, axes = panel_grid(1, 3, size=(3.0, 2.9))
    for k in range(2):
        A = dags[order[k]]
        draw_graph(axes[0, k], pos, A, CP_NAMES, fs=7.5, rad=0.1)
        axes[0, k].set_title("(%s) posterior probability %.3f" % ("ab"[k], post[order[k]]), fontsize=8.5)
    ax = axes[0, 2]
    ax.bar(range(1, 9), post[order[:8]], color=BLUE)
    ax.set_xlabel("DAG (ranked)")
    ax.set_ylabel("posterior probability")
    ax.set_title("(c) the posterior is sharply peaked", fontsize=8.5)
    return savefig(fig, CH, "figS30-12", out)


def fig_S30_13(out=None):
    """Figure S30.13: a locally optimal DAG for the newsgroups data, by hill climbing started from the Chow-Liu tree."""
    import networkx as nx
    X, words = load_news()
    D = X.shape[1]
    K = [2] * D
    MI = mutual_info_matrix(X)
    E = kruskal(MI)
    # direct the tree away from the root (the word with the largest degree)
    deg = np.zeros(D, int)
    for i, j in E:
        deg[i] += 1
        deg[j] += 1
    root = int(np.argmax(deg))
    adj = {i: [] for i in range(D)}
    for i, j in E:
        adj[i].append(j)
        adj[j].append(i)
    A0 = np.zeros((D, D), np.uint8)
    seen = {root}
    queue = [root]
    for v in queue:
        for u in adj[v]:
            if u not in seen:
                seen.add(u)
                A0[v, u] = 1
                queue.append(u)
    cache_path = os.path.join(CACHE_DIR, "hill_news.npz")
    if os.path.exists(cache_path):
        z = np.load(cache_path)
        A, score, moves = z["A"], float(z["score"]), int(z["moves"])
    else:
        A, score, moves = hill_climb(X, K, alpha=5.0, init=A0, max_parents=3)
        np.savez(cache_path, A=A, score=score, moves=moves)
    G = nx.Graph()
    G.add_nodes_from(range(D))
    G.add_edges_from([(i, j) for i in range(D) for j in range(D) if A[i, j]])
    pos = nx.kamada_kawai_layout(G)
    fig, ax = plt.subplots(figsize=(7.4, 7.0))
    for i in range(D):
        for j in range(D):
            if A[i, j]:
                ax.annotate("", xy=pos[j], xytext=pos[i], arrowprops=dict(arrowstyle="-|>", color="#666666", lw=0.5, shrinkA=8, shrinkB=8, mutation_scale=6), zorder=1)
    for i, w in enumerate(words):
        ax.text(pos[i][0], pos[i][1], w, ha="center", va="center", fontsize=5.4, zorder=3, bbox=dict(boxstyle="round,pad=0.12", fc="white", ec="#555555", lw=0.4))
    px = np.array([pos[i][0] for i in range(D)])
    py = np.array([pos[i][1] for i in range(D)])
    ax.set_xlim(px.min() - 0.1, px.max() + 0.1)
    ax.set_ylim(py.min() - 0.1, py.max() + 0.1)
    ax.axis("off")
    ax.set_title("hill climbing from the Chow-Liu tree: %d edges, BDeu score %.0f (tree: %.0f)" % (A.sum(), score, bdeu_dag(X, K, A0)), fontsize=8.5)
    return savefig(fig, CH, "figS30-13", out)


PC_TRUE = [(0, 1), (1, 2), (1, 3), (2, 4), (3, 4)]
PC_POS = {0: (0.0, 1.0), 1: (1.0, 1.0), 2: (2.0, 2.0), 3: (2.0, 0.0), 4: (3.0, 1.0)}


def pc_levels(A):
    """Run the oracle PC algorithm and return the skeleton after each level together with the separating sets."""
    n = len(A)
    P, sep, trace = pc(n, oracle_ci(A))
    states = []
    adj = np.ones((n, n), int) - np.eye(n, dtype=int)
    states.append(adj.copy())
    maxlev = max(l for l, _, _ in trace) if trace else 0
    for lev in range(maxlev + 1):
        for l, (a, b), S in trace:
            if l == lev:
                adj[a, b] = adj[b, a] = 0
        states.append(adj.copy())
    return P, sep, trace, states


def fig_S30_15(out=None):
    """Figure S30.15: step 1 of the PC algorithm on the five-node example, with a d-separation oracle."""
    A = edges_to_A(5, PC_TRUE)
    P, sep, trace, states = pc_levels(A)
    L = list("ABCDE")
    fig, axes = panel_grid(1, 5, size=(2.5, 1.75))
    draw_graph(axes[0, 0], PC_POS, A, L, fs=8, rad=0.12)
    axes[0, 0].set_title("true graph", fontsize=9)
    titles = ["size-0 sets: none found", "after size-1 sets", "after size-2 sets"]
    for k in range(1, 4):
        draw_graph(axes[0, k], PC_POS, states[k], L, fs=8, rad=0.12)
        axes[0, k].set_title(titles[k - 1], fontsize=9)
    draw_graph(axes[0, 4], PC_POS, P, L, fs=8, rad=0.12)
    axes[0, 4].set_title("after orientation", fontsize=9)
    return savefig(fig, CH, "figS30-15", out)


def fig_S30_21(out=None):
    """Figure S30.21: a dependency network of the newsgroups data (l1 logistic regressions, penalty by BIC)."""
    import networkx as nx
    X, words = load_news()
    path = os.path.join(CACHE_DIR, "depnet_news.npy")
    if os.path.exists(path):
        B = np.load(path)
    else:
        B = dependency_network(X)
        np.save(path, B)
    D = len(words)
    off = ~np.eye(D, dtype=bool)
    neg, pos_, zero = int((B[off] < 0).sum()), int((B[off] > 0).sum()), int((B[off] == 0).sum())
    thr = 0.5
    G = nx.Graph()
    G.add_nodes_from(range(D))
    both = 0
    for i in range(D):
        for j in range(i + 1, D):
            if abs(B[i, j]) > thr or abs(B[j, i]) > thr:
                G.add_edge(i, j)
                both += int(abs(B[i, j]) > thr and abs(B[j, i]) > thr)
    pos = nx.spring_layout(G, seed=3, k=0.35, iterations=200)
    fig, ax = plt.subplots(figsize=(7.4, 7.0))
    for i, j in G.edges:
        w = B[i, j] if abs(B[i, j]) > abs(B[j, i]) else B[j, i]
        ax.plot([pos[i][0], pos[j][0]], [pos[i][1], pos[j][1]], color=RED if w < 0 else BLUE, lw=0.6 + 0.35 * min(abs(w), 4), alpha=0.8, zorder=1)
    for i, w in enumerate(words):
        if G.degree(i) > 0:
            ax.text(pos[i][0], pos[i][1], w, ha="center", va="center", fontsize=5.6, zorder=3, bbox=dict(boxstyle="round,pad=0.12", fc="white", ec="#555555", lw=0.4))
    ax.axis("off")
    ax.set_title("dependency network: weights above %.1f (blue positive, red negative); %d negative, %d positive, %d zero weights" % (thr, neg, pos_, zero), fontsize=7.5)
    return savefig(fig, CH, "figS30-21", out)


def fig_S30_22(out=None):
    """Figure S30.22: a sparse binary Markov network of the newsgroups data by l1-penalised pseudo-likelihood."""
    import networkx as nx
    X, words = load_news()
    lam = 0.08
    W, b = ising_pl_lasso(X, lam, iters=300)
    D = len(words)
    G = nx.Graph()
    G.add_nodes_from(range(D))
    G.add_edges_from([(i, j) for i in range(D) for j in range(i + 1, D) if abs(W[i, j]) > 1e-8])
    iso = [v for v in G if G.degree(v) == 0]
    G.remove_nodes_from(iso)
    pos = nx.spring_layout(G, seed=2, k=0.3, iterations=200)
    fig, ax = plt.subplots(figsize=(7.4, 7.0))
    for i, j in G.edges:
        ax.plot([pos[i][0], pos[j][0]], [pos[i][1], pos[j][1]], color=RED if W[i, j] < 0 else BLUE, lw=0.6 + 1.5 * min(abs(W[i, j]), 2), alpha=0.8, zorder=1)
    for i in G.nodes:
        ax.text(pos[i][0], pos[i][1], words[i], ha="center", va="center", fontsize=5.6, zorder=3, bbox=dict(boxstyle="round,pad=0.12", fc="white", ec="#555555", lw=0.4))
    ax.axis("off")
    ax.set_title("l1-penalised pseudo-likelihood, lambda = %.3f: %d edges, %d isolated words not drawn" % (lam, G.number_of_edges(), len(iso)), fontsize=8)
    return savefig(fig, CH, "figS30-22", out)


def anm_sim(n=300, seed=1):
    rng = np.random.default_rng(seed)
    x = rng.uniform(-2, 2, n)
    y = x + x ** 3 / 2.0 + rng.uniform(-1.2, 1.2, n)
    return x, y


def fig_S30_23(out=None):
    """Figure S30.23: the signature of X causing Y in a nonlinear additive noise model."""
    x, y = anm_sim()
    xs = (x - x.mean()) / x.std()
    ys = (y - y.mean()) / y.std()
    res = anm_direction(x, y, deg=5, B=300, rng=np.random.default_rng(0))
    rf = poly_resid(xs, ys, 5)
    rb = poly_resid(ys, xs, 5)
    fig, axes = panel_grid(2, 2, size=(3.2, 2.7))
    fig.subplots_adjust(hspace=0.55, wspace=0.35)
    ax = axes[0, 0]
    ax.scatter(xs, ys, s=5, c=GREY, alpha=0.7)
    o = np.argsort(xs)
    ax.plot(xs[o], (ys - rf)[o], color=RED, lw=1.5)
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.set_title("(a) predict y from x", fontsize=9)
    ax = axes[0, 1]
    ax.scatter(xs, rf, s=5, c=BLUE, alpha=0.7)
    ax.axhline(0, color="k", lw=0.6)
    ax.set_xlabel("x")
    ax.set_ylabel("residual")
    ax.set_title("(b) residual vs x: HSIC p = %.2f" % res["p_xy"], fontsize=9)
    ax = axes[1, 0]
    ax.scatter(ys, xs, s=5, c=GREY, alpha=0.7)
    o = np.argsort(ys)
    ax.plot(ys[o], (xs - rb)[o], color=RED, lw=1.5)
    ax.set_xlabel("y")
    ax.set_ylabel("x")
    ax.set_title("(c) predict x from y", fontsize=9)
    ax = axes[1, 1]
    ax.scatter(ys, rb, s=5, c=BLUE, alpha=0.7)
    ax.axhline(0, color="k", lw=0.6)
    ax.set_xlabel("y")
    ax.set_ylabel("residual")
    ax.set_title("(d) residual vs y: HSIC p = %.3f" % res["p_yx"], fontsize=9)
    return savefig(fig, CH, "figS30-23", out)


def igci_sim(n=500, seed=2, k=3.0):
    rng = np.random.default_rng(seed)
    comp = rng.random(n) < 0.5
    x = np.where(comp, rng.beta(2, 6, n), rng.beta(6, 2, n))
    f = lambda u: (1 - np.exp(-k * u)) / (1 - np.exp(-k))
    return x, f(x), f


def fig_S30_24(out=None):
    """Figure S30.24: information-geometric causal inference: p(Y) is high where f is flat."""
    x, y, f = igci_sim()
    u = np.linspace(0, 1, 200)
    fig, axes = panel_grid(1, 3, size=(3.0, 2.8))
    fig.subplots_adjust(wspace=0.4)
    ax = axes[0, 0]
    ax.plot(u, f(u), color=RED, lw=2)
    ax.plot(x[:60], np.zeros(60) - 0.03, "|", color=BLUE, ms=6)
    ax.plot(np.zeros(60) - 0.03, y[:60], "_", color=GREEN, ms=6)
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.set_title("(a) a monotone f with f(0)=0, f(1)=1", fontsize=9)
    ax = axes[0, 1]
    ax.hist(x, bins=25, range=(0, 1), density=True, histtype="step", color=BLUE, lw=1.5, label=r"$p_X$")
    ax.hist(y, bins=25, range=(0, 1), density=True, histtype="step", color=GREEN, lw=1.5, label=r"$p_Y$")
    ax.set_xlabel("value")
    ax.set_ylabel("density")
    ax.set_title(r"(b) $p_Y$ is high where $f$ is flat", fontsize=9)
    ax.legend(fontsize=7)
    rng = np.random.default_rng(5)
    ok_s = ok_e = 0
    T = 300
    for t in range(T):
        kk = rng.uniform(0.5, 5)
        comp = rng.random(300) < rng.uniform(0.2, 0.8)
        xx = np.where(comp, rng.beta(rng.uniform(1.5, 4), rng.uniform(4, 8), 300), rng.beta(rng.uniform(4, 8), rng.uniform(1.5, 4), 300))
        yy = (1 - np.exp(-kk * xx)) / (1 - np.exp(-kk))
        cxy, cyx = igci_slope(xx, yy)
        hx, hy = igci_entropy(xx, yy)
        ok_s += cxy < cyx
        ok_e += hx > hy
    ax = axes[0, 2]
    ax.bar([0, 1], [ok_s / T, ok_e / T], color=[BLUE, GREEN], width=0.5)
    ax.set_xticks([0, 1])
    ax.set_xticklabels(["slope", "entropy"])
    ax.set_ylim(0, 1.05)
    ax.axhline(0.5, color="k", ls=":", lw=0.8)
    ax.set_ylabel("fraction correct")
    ax.set_title("(c) %d random pairs" % T, fontsize=9)
    return savefig(fig, CH, "figS30-24", out)


def fig_x30_1(out=None):
    """Own figure x30.1: faithfulness. corr(X, Z) in X -> Y -> Z with the direct effect c of X on Z: zero at c = -ab."""
    rng = np.random.default_rng(0)
    cs = np.linspace(-2.5, 0.5, 61)
    a = b = 1.0
    # exact: Var(X) = 1, Cov(X, Z) = ab + c, Var(Z) = (ab + c)^2 + b^2 + 1 (Y = aX + eY, Z = bY + cX + eZ)
    corr = lambda c: (a * b + c) / np.sqrt((a * b + c) ** 2 + b ** 2 + 1)
    fig, axes = panel_grid(1, 2, size=(3.4, 2.7))
    ax = axes[0, 0]
    ax.plot(cs, [corr(c) for c in cs], color=BLUE)
    emp = []
    for c in cs[::6]:
        x = rng.standard_normal(20000)
        yv = a * x + rng.standard_normal(20000)
        z = b * yv + c * x + rng.standard_normal(20000)
        emp.append(np.corrcoef(x, z)[0, 1])
    ax.plot(cs[::6], emp, "o", color=RED, ms=3.5, label="simulated, 20 000 cases")
    ax.axhline(0, color="k", lw=0.6)
    ax.axvline(-a * b, color=GREY, ls="--", lw=0.8)
    ax.set_xlabel("direct effect c of X on Z")
    ax.set_ylabel("corr(X, Z)")
    ax.set_title("(a) independent at c = -ab", fontsize=9)
    ax.legend(fontsize=7)
    # probability of an accidental near-cancellation with random coefficients
    ax = axes[0, 1]
    eps = np.array([0.005, 0.01, 0.02, 0.05, 0.1, 0.2])
    prob = []
    for e in eps:
        A_ = rng.normal(0, 1, 400000)
        B_ = rng.normal(0, 1, 400000)
        C_ = rng.normal(0, 1, 400000)
        v = (A_ * B_ + C_) / np.sqrt((A_ * B_ + C_) ** 2 + B_ ** 2 + 1)
        prob.append((np.abs(v) < e).mean())
    ax.loglog(eps, prob, "o-", color=BLUE)
    ax.loglog(eps, prob[0] * eps / eps[0], "k:", lw=0.8, label="slope 1")
    ax.set_xlabel(r"$\epsilon$")
    ax.set_ylabel(r"$\Pr(|\mathrm{corr}(X,Z)|<\epsilon)$")
    ax.set_title("(b) random coefficients", fontsize=9)
    ax.legend(fontsize=7)
    return savefig(fig, CH, "figx30-1", out)


def lc_data(N, rng, D=3, pi1=0.5, th=((0.15, 0.85), (0.2, 0.8), (0.1, 0.9))):
    z = (rng.random(N) < pi1).astype(int)
    th = np.array(th)
    return (rng.random((N, D)) < th[np.arange(D)[None, :], z[:, None]]).astype(float)


def lc_scores(X, K=2):
    """Exact log marginal likelihood and the three approximations. The approximations describe one labelling of the
    classes, the exact value sums over all K! of them, so log K! is added to each approximation."""
    ex = lc_exact_logml(X, K)
    corr = float(special.gammaln(K + 1))
    return dict(exact=ex, bic=lc_bic(X, K) + corr, cs=lc_cs(X, K) + corr, vb=lc_vb(X, K) + corr)


def fig_x30_2(out=None):
    """Own figure x30.2: BIC, Cheeseman-Stutz and the variational bound against the exact log marginal likelihood of
    a latent class model with one hidden binary variable (S30.3.8)."""
    path = os.path.join(CACHE_DIR, "lc_scores.json")
    Ns = [6, 8, 10, 12, 14]
    reps = 25
    if os.path.exists(path):
        res = json.load(open(path))
    else:
        res = {}
        for N in Ns:
            rng = np.random.default_rng(100 + N)
            res[str(N)] = [lc_scores(lc_data(N, rng)) for _ in range(reps)]
        json.dump(res, open(path, "w"))
    fig, axes = panel_grid(1, 2, size=(3.5, 2.8))
    ax = axes[0, 0]
    for key, col, lab in (("bic", GREY, "BIC"), ("cs", ORANGE, "Cheeseman-Stutz"), ("vb", BLUE, "variational bound")):
        m = [np.mean([r[key] - r["exact"] for r in res[str(N)]]) for N in Ns]
        s = [np.std([r[key] - r["exact"] for r in res[str(N)]]) for N in Ns]
        ax.errorbar(Ns, m, yerr=s, color=col, marker="o", ms=4, capsize=2, label=lab)
    ax.axhline(0, color="k", lw=0.6)
    ax.set_xlabel("number of cases N")
    ax.set_ylabel("approximation minus exact log p(D)")
    ax.set_title("(a) error of three approximations", fontsize=9)
    ax.legend(fontsize=7)
    ax = axes[0, 1]
    r = res["14"]
    ex = np.array([q["exact"] for q in r])
    for key, col, lab in (("bic", GREY, "BIC"), ("cs", ORANGE, "CS"), ("vb", BLUE, "VB")):
        ax.plot(ex, [q[key] for q in r], "o", color=col, ms=3.5, label=lab)
    lo, hi = ex.min() - 1, ex.max() + 1
    ax.plot([lo, hi], [lo, hi], "k:", lw=0.8)
    ax.set_xlabel("exact log p(D)")
    ax.set_ylabel("approximation")
    ax.set_title("(b) N = 14, %d data sets" % len(r), fontsize=9)
    ax.legend(fontsize=7)
    return savefig(fig, CH, "figx30-2", out)


def notears_demo(seed=0, d=6, N=1000):
    rng = np.random.default_rng(seed)
    Wt = np.zeros((d, d))
    for (i, j) in [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (2, 5)]:
        Wt[i, j] = rng.choice([-1, 1]) * rng.uniform(0.8, 1.6)
    X = sem_sample(Wt, N, rng)
    return Wt, X


def fig_x30_3(out=None):
    """Own figure x30.3: NOTEARS recovers the weighted adjacency matrix of a linear Gaussian DAG; the acyclicity measure."""
    Wt, X = notears_demo()
    W, Wth = notears(X, lam=0.05)
    d = len(Wt)
    fig, axes = panel_grid(1, 4, size=(2.5, 2.5))
    vm = np.abs(Wt).max()
    for ax, M, title in ((axes[0, 0], Wt, "(a) true W"), (axes[0, 1], Wth, "(b) NOTEARS, thresholded at 0.3")):
        ax.imshow(M, cmap="RdBu_r", vmin=-vm, vmax=vm)
        ax.set_title(title, fontsize=8.5)
        ax.set_xticks(range(d))
        ax.set_yticks(range(d))
    ax = axes[0, 2]
    t = np.linspace(0, 1, 41)
    Wc = np.zeros((3, 3))
    Wc[0, 1], Wc[1, 2] = 1.0, 1.0
    hs, hp = [], []
    for s in t:
        M = Wc.copy()
        M[2, 0] = s
        hs.append(notears_h(M))
        hp.append(notears_h_poly(M))
    ax.plot(t, hs, color=BLUE, label=r"$\mathrm{tr}\,e^{W\circ W}-d$")
    ax.plot(t, hp, color=ORANGE, ls="--", label=r"$\mathrm{tr}(I+W\circ W/d)^d-d$")
    ax.set_xlabel("weight of the closing edge 3 -> 1")
    ax.set_ylabel("h(W)")
    ax.set_title("(c) h = 0 only without a cycle", fontsize=8.5)
    ax.legend(fontsize=6.5)
    ax = axes[0, 3]
    ax.axis("off")
    shd = int(((np.abs(Wth) > 0) != (np.abs(Wt) > 0)).sum())
    ax.text(0, 0.9, "d = %d, N = %d" % (d, len(X)), fontsize=9, va="top")
    ax.text(0, 0.7, "h(W) = %.1e" % notears_h(W), fontsize=9, va="top")
    ax.text(0, 0.5, "edge errors: %d" % shd, fontsize=9, va="top")
    ax.text(0, 0.3, "max weight error:\n%.3f" % np.abs(W * (np.abs(Wth) > 0) - Wt).max(), fontsize=9, va="top")
    return savefig(fig, CH, "figx30-3", out)


def fig_x30_4(out=None):
    """Own figure x30.4: interventional data separate the Markov equivalent models X -> Y and Y -> X."""
    reps = 40
    Ns = [20, 50, 100, 200, 500, 1000]
    obs, intv = [], []
    for N in Ns:
        po, pi_ = [], []
        for r in range(reps):
            rng = np.random.default_rng(1000 * N + r)
            # X -> Y, binary, p(x = 1) = 0.5, p(y = 1 | x) = 0.8 / 0.25
            def gen(n, do_x=None):
                x = (rng.random(n) < 0.5).astype(int) if do_x is None else do_x
                y = (rng.random(n) < np.where(x == 1, 0.8, 0.25)).astype(int)
                return x, y
            x, y = gen(N)
            s1, s2 = bdeu_two_node(x, y)
            po.append(special.expit(s1 - s2))
            n_i = N // 2
            x1, y1 = gen(N - n_i)
            do = (rng.random(n_i) < 0.5).astype(int)
            x2, y2 = gen(n_i, do)
            xx, yy = np.concatenate([x1, x2]), np.concatenate([y1, y2])
            flag = np.concatenate([np.zeros(N - n_i, bool), np.ones(n_i, bool)])
            s1, s2 = bdeu_two_node(xx, yy, intervened_x=flag)
            pi_.append(special.expit(s1 - s2))
        obs.append(np.mean(po))
        intv.append(np.mean(pi_))
    fig, ax = plt.subplots(figsize=(4.3, 2.9))
    ax.semilogx(Ns, obs, "o-", color=GREY, label="observational data only")
    ax.semilogx(Ns, intv, "o-", color=BLUE, label="half the cases with X set by intervention")
    ax.axhline(0.5, color="k", ls=":", lw=0.7)
    ax.set_xlabel("number of cases N")
    ax.set_ylabel(r"$p(X\to Y\,|\,D)$")
    ax.set_ylim(0.4, 1.02)
    ax.legend(fontsize=7, loc="center right")
    ax.set_title("the true model is X -> Y (average of %d data sets)" % reps, fontsize=8.5)
    return savefig(fig, CH, "figx30-4", out)


# =========================================================================== data for the browser demonstrations
def export_glasso_json():
    """Covariance matrices for the graphical lasso demonstration: the flow cytometry data and two simulated
    Gaussian graphical models (a chain and a grid-like graph) at two sample sizes."""
    S, names, N = sachs_cov()
    out = {"sets": []}
    out["sets"].append(dict(name="Flow cytometry, 11 proteins (N = %d)" % N, labels=names, S=np.round(S, 6).tolist(), N=N, lams=[36, 27, 7, 0]))
    p = 8
    Om = np.eye(p) * 1.0
    for i in range(p - 1):
        Om[i, i + 1] = Om[i + 1, i] = -0.4
    Sig = np.linalg.inv(Om)
    for N_ in (60, 1000):
        rng = np.random.default_rng(7 + N_)
        Xs = rng.multivariate_normal(np.zeros(p), Sig, size=N_)
        Ss = np.cov(Xs.T, bias=True)
        out["sets"].append(dict(name="Simulated chain, 8 variables (N = %d)" % N_, labels=["V%d" % (i + 1) for i in range(p)], S=np.round(Ss, 6).tolist(), N=N_, lams=[0.35, 0.2, 0.1, 0.0], truth=[[i, i + 1] for i in range(p - 1)]))
    S4 = np.array([[10, 1, 5, 4], [1, 10, 2, 6], [5, 2, 10, 3], [4, 6, 3, 10.]])
    out["sets"].append(dict(name="Four-variable example of (30.48)", labels=["X1", "X2", "X3", "X4"], S=S4.tolist(), N=0, lams=[3.0, 2.0, 1.0, 0.0]))
    json.dump(out, open(os.path.join(DATA_OUT, "ch30-glasso.json"), "w"))
    return out


PC_GRAPHS = {
    "fig30-15": dict(labels=list("ABCDE"), edges=[(0, 1), (1, 2), (1, 3), (2, 4), (3, 4)], pos=[[0, 1], [1, 1], [2, 2], [2, 0], [3, 1]]),
    "fig30-10-G1": dict(labels=["X1", "X2", "X3", "X4", "X5"], edges=[(0, 4), (0, 1), (2, 1), (1, 3)], pos=[[0, 2], [0.6, 1], [1.2, 2], [0.6, 0], [-0.6, 1]]),
    "collider-chain": dict(labels=list("ABCDEF"), edges=[(0, 2), (1, 2), (2, 3), (3, 4), (3, 5)], pos=[[0, 2], [0, 0], [1, 1], [2, 1], [3, 2]] + [[3, 0]]),
}


def export_pc_json(N=4000):
    out = {"graphs": []}
    for k, (name, g) in enumerate(PC_GRAPHS.items()):
        n = len(g["labels"])
        rng = np.random.default_rng(300 + k)
        W = np.zeros((n, n))
        for (i, j) in g["edges"]:
            W[i, j] = rng.choice([-1, 1]) * rng.uniform(0.6, 1.4)
        X = sem_sample(W, N, rng)
        out["graphs"].append(dict(name=name, labels=g["labels"], edges=g["edges"], pos=g["pos"], W=np.round(W, 4).tolist(), X=np.round(X, 3).tolist()))
    json.dump(out, open(os.path.join(DATA_OUT, "ch30-pc.json"), "w"), separators=(",", ":"))
    return out


def pairs_data(n=500):
    rng = np.random.default_rng(21)
    out = []
    x = rng.standard_normal(n)
    out.append(("Nonlinear additive noise, Gaussian noise", x, x + 0.5 * x ** 3 + 0.6 * rng.standard_normal(n)))
    x = rng.standard_normal(n)
    out.append(("Linear, Gaussian noise", x, 0.8 * x + 0.6 * rng.standard_normal(n)))
    x = rng.uniform(-np.sqrt(3), np.sqrt(3), n)
    out.append(("Linear, uniform noise", x, 0.8 * x + 0.6 * rng.uniform(-np.sqrt(3), np.sqrt(3), n)))
    comp = rng.random(n) < 0.5
    x = np.where(comp, rng.beta(2, 6, n), rng.beta(6, 2, n))
    out.append(("Deterministic monotone map (IGCI)", x, (1 - np.exp(-3 * x)) / (1 - np.exp(-3))))
    return out


def export_pairs_json():
    sets = [dict(name=nm, x=np.round(x, 9).tolist(), y=np.round(y, 9).tolist()) for nm, x, y in pairs_data()]
    json.dump({"sets": sets}, open(os.path.join(DATA_OUT, "ch30-pairs.json"), "w"), separators=(",", ":"))
    return sets


def export_all(out=None):
    """Write the JSON files used by the three demonstrations."""
    export_glasso_json()
    export_pc_json()
    export_pairs_json()
    print("wrote the data files in", DATA_OUT)


FIGURES = {
    "30.1": fig_30_1,
    "S30.2": fig_S30_2,
    "S30.3": fig_S30_3,
    "S30.5": fig_S30_5,
    "S30.8": fig_S30_8,
    "S30.10": fig_S30_10,
    "S30.11": fig_S30_11,
    "S30.12": fig_S30_12,
    "S30.13": fig_S30_13,
    "S30.15": fig_S30_15,
    "S30.21": fig_S30_21,
    "S30.22": fig_S30_22,
    "S30.23": fig_S30_23,
    "S30.24": fig_S30_24,
    "x30.1": fig_x30_1,
    "x30.2": fig_x30_2,
    "x30.3": fig_x30_3,
    "x30.4": fig_x30_4,
    "data": export_all,
}

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