"""Murphy (2023), Chapter 9: Message passing algorithms.

Companion code for Chapter 9 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics (MIT Press, 2023;
December 2025 draft), pp. 401-438, and its supplement (Supplementary Chapter 9, pp. 99-122), written from scratch
with numpy, scipy and matplotlib (PyTorch only for inference by differentiation), to be read next to the lecture notes
(../ch09-message-passing.html).

Methods implemented (the notes use these functions by name)
* HMMs (Section 9.2): the casino and speech HMMs, sampling, the forwards algorithm (9.5)-(9.8) with the log marginal
  likelihood, the backwards recursion (9.18), forwards-backwards smoothing and two-slice marginals (9.12), (9.27),
  forwards filtering backwards smoothing (9.37), the Viterbi algorithm (9.43)-(9.45) with traceback, forwards
  filtering backwards sampling (9.48)-(9.49), enumeration for comparison.
* Trees and loopy graphs (Sections 9.3-9.4): pairwise MRFs (PairwiseMRF) with exact enumeration; sum-product and
  max-product on trees (tree_bp, with the product-of-others and division forms (9.60)-(9.61)); loopy BP with damping
  (9.77) and synchronous, asynchronous and residual schedules (loopy_bp); Ising grids and their exact marginals by
  column transfer matrices; factor-graph BP (9.68)-(9.70); Gaussian BP (gaussian_bp); pi-lambda message passing on
  polytrees (Polytree, Supplement 9.1.1); the three-bit error-correcting example, LDPC matrices and a sum-product
  decoder (tanh rule); affinity propagation.
* Exact inference (Sections 9.5-9.6, Supplement 9.2): factors (Factor), variable elimination with its trace
  (Tables 9.1-9.2), symbolic elimination (induced graph, fill-in, cliques, width, the cost (9.92)), the min-fill
  heuristic, exact treewidth by dynamic programming, junction trees as maximum-weight spanning trees, the
  Lauritzen-Spiegelhalter calibration with division.
* Inference as optimisation (Section 9.7, Supplement 9.3): marginals as the gradient of log Z (PyTorch version of
  Listing 9.1), Gaussian and Gumbel perturb-and-MAP, the LP relaxation over the local polytope, a maximum-flow
  routine (Edmonds-Karp) and exact minimum-energy labelling of submodular binary MRFs by graph cuts.

Data. Everything is simulated or built from the numbers printed in the book (casino and speech HMMs, the three-bit code,
the graph-cut example). The student network of Section 9.5 is given in the book as a structure only; the conditional
probability tables are our own illustrative numbers. The 11 x 11 Ising grid of Figure 9.13 uses seeded random couplings
(the book's coupling scale is not precise enough to copy; the scale 1.7 was chosen to show the same behaviour). The
noisy-data interpolation of Figure 9.11, the points of Figure 9.17 and the images of Figure 9.S3 are simulated. All seeds
are fixed in the code.

Figures. Reproduced here: 9.3, 9.6(b), 9.11, 9.13, 9.17, 9.18, S9.4, S9.10(a) with S9.11(b), S9.13 (S = supplement).
Our own supplementary figures: 9.S1 (LDPC decoding), 9.S2 (Gaussian BP on a loopy grid), 9.S3 (graph-cut denoising),
9.S4 (perturb-and-MAP), 9.S5 (all elimination orders). Skipped, with the reason:
  9.1, 9.4, 9.5, 9.7-9.10, 9.14-9.16, 9.19, 9.20, S9.1-S9.3, S9.5-S9.9, S9.14
         diagrams and schematics with nothing computed (graphs, message-passing pictures, trellis sketches, hyper-graphs,
         a factor graph, the SAT encoding, drawings of moves); the numbers they illustrate are reproduced in the text;
  9.2    the casino transition diagram (its numbers are the model's inputs);
  9.12   the computation tree of a four-node graph (a drawing);
  9.15   the LDPC factor graph drawing (the decoding itself is reproduced as 9.S1);
  S9.11(a) a drawing of pseudo-marginals on a triangle (its content is in S9.10(b));
  S9.12, S9.15  stereo depth estimation on the Venus and Tsukuba image pairs: the images are not available.
Run `python3 ch09_message_passing.py --list`, `python3 ch09_message_passing.py` (all figures, under a minute) or
`python3 ch09_message_passing.py --fig 9.3`. Files go to ../img/ch09/; the data used by the browser demonstrations go to
../data/ch09-*.json.
"""
import heapq
import itertools
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import special

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

CH = 9
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))


def normalize(v, axis=None):
    v = np.asarray(v, float)
    return v / v.sum(axis=axis, keepdims=axis is not None)


# =========================================================================== hidden Markov models (Section 9.2)
# Conventions of the book: A[i, j] = p(z_t = j | z_{t-1} = i), lik[t, j] = lambda_t(j) = p(y_t | z_t = j).
def casino_hmm():
    """The occasionally dishonest casino of Section 9.2.1.1: state 0 = fair, 1 = loaded (Figure 9.2).

    The initial distribution is the stationary distribution of A, (2/3, 1/3)."""
    A = np.array([[0.95, 0.05], [0.10, 0.90]])
    B = np.array([[1 / 6] * 6, [0.1] * 5 + [0.5]])
    pi = np.array([2 / 3, 1 / 3])
    return pi, A, B


def sample_hmm(pi, A, B, T, rng):
    K = len(pi)
    z = np.zeros(T, int)
    y = np.zeros(T, int)
    z[0] = rng.choice(K, p=pi)
    for t in range(T):
        if t:
            z[t] = rng.choice(K, p=A[z[t - 1]])
        y[t] = rng.choice(B.shape[1], p=B[z[t]])
    return z, y


def forwards(pi, A, lik):
    """The forwards algorithm (9.5)-(9.8): alpha[t] = p(z_t | y_1:t), the predictions p(z_t | y_1:t-1) and the
    normalisers Z_t = p(y_t | y_1:t-1); sum(log Z) is the log marginal likelihood."""
    T, K = lik.shape
    alpha = np.zeros((T, K))
    pred = np.zeros((T, K))
    Z = np.zeros(T)
    for t in range(T):
        pred[t] = pi if t == 0 else A.T @ alpha[t - 1]          # (9.5)
        u = lik[t] * pred[t]                                      # (9.6)
        Z[t] = u.sum()                                            # (9.7)
        alpha[t] = u / Z[t]
    return alpha, pred, Z


def backwards(A, lik):
    """The backwards recursion (9.18) with normalisation after each step: beta[t] is proportional to
    p(y_{t+1:T} | z_t = .) (the constant does not matter once gamma is normalised)."""
    T, K = lik.shape
    beta = np.ones((T, K))
    for t in range(T - 1, 0, -1):
        b = A @ (lik[t] * beta[t])                                # (9.18)
        beta[t - 1] = b / b.sum()
    return beta


def forwards_backwards(pi, A, lik):
    """Smoothing by two-filter smoothing (9.12) and the two-slice marginals (9.27)."""
    alpha, pred, Z = forwards(pi, A, lik)
    beta = backwards(A, lik)
    gamma = alpha * beta
    gamma /= gamma.sum(1, keepdims=True)
    T, K = lik.shape
    xi = np.zeros((T - 1, K, K))
    for t in range(T - 1):
        x = alpha[t][:, None] * A * (lik[t + 1] * beta[t + 1])[None, :]
        xi[t] = x / x.sum()
    return dict(alpha=alpha, pred=pred, Z=Z, beta=beta, gamma=gamma, xi=xi, loglik=np.log(Z).sum())


def smooth_ffbs(pi, A, lik):
    """Forwards filtering, backwards smoothing (9.32)-(9.37): gamma from alpha without any beta."""
    alpha, pred, Z = forwards(pi, A, lik)
    T, K = lik.shape
    gamma = np.zeros((T, K))
    gamma[-1] = alpha[-1]
    xi = np.zeros((T - 1, K, K))
    for t in range(T - 2, -1, -1):
        ratio = gamma[t + 1] / pred[t + 1]                        # gamma_{t+1}(j) / alpha_{t+1|t}(j)
        xi[t] = alpha[t][:, None] * A * ratio[None, :]            # (9.35)
        gamma[t] = xi[t].sum(1)                                   # (9.37)
    return gamma, xi


def viterbi(pi, A, lik):
    """The Viterbi algorithm (9.43)-(9.45) in the log domain, with the traceback of Section 9.2.6.2.
    Returns the MAP path, the table delta (log scale) and the ancestor table."""
    T, K = lik.shape
    with np.errstate(divide="ignore"):
        lA, ll, lpi = np.log(A), np.log(lik), np.log(pi)
    delta = np.zeros((T, K))
    anc = np.zeros((T, K), int)
    delta[0] = lpi + ll[0]
    for t in range(1, T):
        cand = delta[t - 1][:, None] + lA                         # cand[i, j] = delta_{t-1}(i) + log A_ij
        anc[t] = cand.argmax(0)
        delta[t] = ll[t] + cand.max(0)
    path = np.zeros(T, int)
    path[-1] = delta[-1].argmax()
    for t in range(T - 2, -1, -1):
        path[t] = anc[t + 1][path[t + 1]]
    return path, delta, anc


def ffbs_sample(pi, A, lik, rng, n=1):
    """Forwards filtering, backwards sampling (9.48)-(9.49): n exact samples from p(z_1:T | y_1:T)."""
    alpha, _, _ = forwards(pi, A, lik)
    T, K = lik.shape
    out = np.zeros((n, T), int)
    for s in range(n):
        out[s, -1] = rng.choice(K, p=alpha[-1])
        for t in range(T - 2, -1, -1):
            p = alpha[t] * A[:, out[s, t + 1]]
            out[s, t] = rng.choice(K, p=p / p.sum())
    return out


def hmm_bruteforce(pi, A, lik):
    """Enumerate all K^T paths: the posterior marginals, the MAP path and the likelihood p(y_1:T)."""
    T, K = lik.shape
    best, bestp, tot = None, -1.0, 0.0
    marg = np.zeros((T, K))
    for path in itertools.product(range(K), repeat=T):
        p = pi[path[0]] * lik[0, path[0]]
        for t in range(1, T):
            p *= A[path[t - 1], path[t]] * lik[t, path[t]]
        tot += p
        for t in range(T):
            marg[t, path[t]] += p
        if p > bestp:
            bestp, best = p, path
    return marg / tot, np.array(best), tot


def speech_hmm():
    """The 3-state left-to-right HMM of Figure 9.6 (7 codebook symbols C1..C7, started in S1)."""
    A = np.array([[0.3, 0.7, 0.0], [0.0, 0.9, 0.1], [0.0, 0.0, 0.4]])
    B = np.array([[0.5, 0.2, 0.3, 0.0, 0.0, 0.0, 0.0],
                  [0.0, 0.0, 0.2, 0.7, 0.1, 0.0, 0.0],
                  [0.0, 0.0, 0.0, 0.1, 0.0, 0.5, 0.4]])
    pi = np.array([1.0, 0.0, 0.0])
    return pi, A, B


def viterbi_prob(pi, A, lik):
    """delta_t(j) on the probability scale (9.42), without logs, for the small worked example."""
    T, K = lik.shape
    d = np.zeros((T, K))
    d[0] = pi * lik[0]
    for t in range(1, T):
        d[t] = lik[t] * (d[t - 1][:, None] * A).max(0)
    return d


# =========================================================================== pairwise MRFs and belief propagation (Sections 9.3-9.4)
class PairwiseMRF:
    """p(z) proportional to prod_s psi_s(z_s) prod_{(s,t) in E} psi_st(z_s, z_t) (9.50).

    node_pot[s] is a vector, edge_pot[(s, t)] a matrix with rows indexed by z_s, for each edge stored once (s < t)."""

    def __init__(self, node_pot, edge_pot):
        self.node_pot = [np.asarray(p, float) for p in node_pot]
        self.n = len(self.node_pot)
        self.edge_pot = {}
        for (s, t), M in edge_pot.items():
            if s > t:
                s, t, M = t, s, np.asarray(M, float).T
            self.edge_pot[(s, t)] = np.asarray(M, float)
        self.nbrs = {s: [] for s in range(self.n)}
        for s, t in self.edge_pot:
            self.nbrs[s].append(t)
            self.nbrs[t].append(s)
        self.card = [len(p) for p in self.node_pot]

    def psi(self, s, t):
        """The matrix psi_st indexed [z_s, z_t] for either orientation."""
        return self.edge_pot[(s, t)] if s < t else self.edge_pot[(t, s)].T

    def joint(self):
        shape = tuple(self.card)
        P = np.ones(shape)
        for s in range(self.n):
            sh = [1] * self.n
            sh[s] = self.card[s]
            P = P * self.node_pot[s].reshape(sh)
        for (s, t), M in self.edge_pot.items():
            sh = [1] * self.n
            sh[s], sh[t] = self.card[s], self.card[t]
            P = P * M.reshape(sh)
        return P

    def exact_marginals(self):
        P = self.joint()
        Z = P.sum()
        return [P.sum(axis=tuple(a for a in range(self.n) if a != s)) / Z for s in range(self.n)], Z

    def max_marginals(self):
        P = self.joint()
        P = P / P.sum()
        return [P.max(axis=tuple(a for a in range(self.n) if a != s)) for s in range(self.n)]

    def map_states(self):
        P = self.joint()
        m = P.max()
        return [tuple(int(i) for i in idx) for idx in zip(*np.nonzero(np.isclose(P, m, rtol=1e-12, atol=0)))]


def _msg(mrf, s, t, inc, mode):
    """m_{s->t}(z_t) = sum_{z_s} psi_s(z_s) psi_st(z_s, z_t) prod_{u in nbr(s)\\t} m_{u->s}(z_s)   (9.60), (9.67)
    (max instead of sum for max-product)."""
    b = mrf.node_pot[s].copy()
    for u in mrf.nbrs[s]:
        if u != t:
            b = b * inc[(u, s)]
    M = b[:, None] * mrf.psi(s, t)
    m = M.sum(0) if mode == "sum" else M.max(0)
    return m / m.sum()


def _tree_order(mrf, root):
    """Pre-order (parents first) of the tree rooted at `root`; returns the order and the parent map."""
    parent = {root: None}
    order = [root]
    for s in order:
        for t in mrf.nbrs[s]:
            if t not in parent:
                parent[t] = s
                order.append(t)
    return order, parent


def tree_bp(mrf, root=0, mode="sum", division=False):
    """Belief propagation on a tree (Algorithm 9.8): collect to the root in post-order, distribute in pre-order.

    Returns the beliefs (marginals for mode 'sum', max-marginals for 'max', each normalised) and the messages.
    With division=True the downward message uses (9.61), bel_s / m_{t->s}, instead of the product over the other
    children; the two agree whenever no message has a zero entry."""
    order, parent = _tree_order(mrf, root)
    assert len(order) == mrf.n and len(mrf.edge_pot) == mrf.n - 1, "the graph must be a tree"
    inc = {}
    for s in reversed(order):                                      # collect (post-order)
        p = parent[s]
        if p is not None:
            inc[(s, p)] = _msg(mrf, s, p, inc, mode)
    bel = [None] * mrf.n
    for t in order:                                                # distribute (pre-order)
        s = parent[t]
        if s is not None:
            if division:
                full = mrf.node_pot[s].copy()
                for u in mrf.nbrs[s]:
                    full = full * inc[(u, s)]
                M = (full / inc[(t, s)])[:, None] * mrf.psi(s, t)
                m = M.sum(0) if mode == "sum" else M.max(0)
                inc[(s, t)] = m / m.sum()
            else:
                inc[(s, t)] = _msg(mrf, s, t, inc, mode)
        b = mrf.node_pot[t].copy()
        for u in mrf.nbrs[t]:
            b = b * inc[(u, t)]
        bel[t] = b / b.sum()
    return bel, inc


def loopy_bp(mrf, iters=100, damping=1.0, schedule="sync", tol=1e-3, mode="sum", track=None, seed=0):
    """Loopy belief propagation (Section 9.4.1) with damping (9.77) and three update schedules:
    'sync'  all messages from the old ones, (9.78) (Jacobi);
    'async' a fixed round-robin order, each message uses the newest values, (9.79) (Gauss-Seidel);
    'residual' the message with the largest residual (9.80) is sent next (Elidan et al., 2006); one 'iteration'
            is E message updates.
    damping = lambda in (9.77) (1 = no damping). Returns a dict with the final beliefs, the messages, the fraction of
    messages that changed by less than tol per iteration (history) and the belief history of the nodes in `track`."""
    edges = [(s, t) for (s, t) in mrf.edge_pot] + [(t, s) for (s, t) in mrf.edge_pot]
    inc = {e: np.ones(mrf.card[e[1]]) / mrf.card[e[1]] for e in edges}
    hist_conv, hist_bel = [], {s: [] for s in (track or [])}

    def beliefs_of(s):
        b = mrf.node_pot[s].copy()
        for u in mrf.nbrs[s]:
            b = b * inc[(u, s)]
        return b / b.sum()

    def record(changed):
        hist_conv.append(float(np.mean(changed)))
        for s in hist_bel:
            hist_bel[s].append(beliefs_of(s))

    record([False] * len(edges))
    n_iter = 0
    if schedule in ("sync", "async"):
        for it in range(iters):
            n_iter = it + 1
            changed = []
            if schedule == "sync":
                new = {}
                for (s, t) in edges:
                    m = _msg(mrf, s, t, inc, mode)
                    new[(s, t)] = damping * m + (1 - damping) * inc[(s, t)]
                for e in edges:
                    changed.append(np.abs(new[e] - inc[e]).max() < tol)
                inc = new
            else:
                for (s, t) in edges:
                    m = _msg(mrf, s, t, inc, mode)
                    m = damping * m + (1 - damping) * inc[(s, t)]
                    changed.append(np.abs(m - inc[(s, t)]).max() < tol)
                    inc[(s, t)] = m
            record(changed)
            if all(changed):
                break
    else:                                                          # residual BP with a priority queue
        cand = {e: _msg(mrf, e[0], e[1], inc, mode) for e in edges}
        heap = []
        stamp = {e: 0 for e in edges}

        def residual(e):
            return float(np.max(np.abs(np.log(cand[e] + 1e-300) - np.log(inc[e] + 1e-300))))
        for e in edges:
            heapq.heappush(heap, (-residual(e), 0, e))
        sent = 0
        E = len(edges)
        for it in range(iters):
            n_iter = it + 1
            for _ in range(E):
                while heap:
                    r, st, e = heapq.heappop(heap)
                    if st == stamp[e]:
                        break
                else:
                    break
                if -r < 1e-12:
                    heapq.heappush(heap, (r, st, e))
                    break
                inc[e] = damping * cand[e] + (1 - damping) * inc[e]
                sent += 1
                s, t = e
                for u in mrf.nbrs[t]:
                    if u != s:
                        f = (t, u)
                        cand[f] = _msg(mrf, t, u, inc, mode)
                        stamp[f] += 1
                        heapq.heappush(heap, (-residual(f), stamp[f], f))
            cur = max((residual(e) for e in edges), default=0.0)
            changed = [np.abs(cand[e] - inc[e]).max() < tol for e in edges]
            record(changed)
            if all(changed):
                break
    return dict(bel=[beliefs_of(s) for s in range(mrf.n)], msgs=inc, converged=bool(hist_conv[-1] == 1.0),
                frac=hist_conv, hist=hist_bel, iters=n_iter)


def ising_grid(R, C, w_h, w_v, h):
    """A pairwise MRF on an R x C grid of spins s in {-1,+1} (state 0 -> s=-1, state 1 -> s=+1) with
    psi_s = exp(h_s s), psi_st = exp(w_st s_s s_t). w_h[i, j] couples (i, j)-(i, j+1), w_v[i, j] couples (i, j)-(i+1, j)."""
    sp = np.array([-1.0, 1.0])
    nodes = [np.exp(h[i, j] * sp) for i in range(R) for j in range(C)]
    edges = {}
    idx = lambda i, j: i * C + j  # noqa: E731
    for i in range(R):
        for j in range(C):
            if j + 1 < C:
                edges[(idx(i, j), idx(i, j + 1))] = np.exp(w_h[i, j] * np.outer(sp, sp))
            if i + 1 < R:
                edges[(idx(i, j), idx(i + 1, j))] = np.exp(w_v[i, j] * np.outer(sp, sp))
    return PairwiseMRF(nodes, edges)


def ising_grid_exact(R, C, w_h, w_v, h):
    """Exact node marginals p(s_ij = +1) of an R x C Ising grid by column transfer matrices (cost 4^R C),
    with R columns of 2^R joint states: the junction tree of Section 9.6 with the grid's columns as cliques."""
    S = np.array([[1.0 if (a >> i) & 1 else -1.0 for i in range(R)] for a in range(2 ** R)])      # (2^R, R) spins
    def colE(j):
        e = S @ h[:, j]
        if R > 1:
            e = e + (S[:, :-1] * S[:, 1:]) @ w_v[:R - 1, j]
        return e
    def trans(j):
        return np.exp((S * w_h[:, j][None, :]) @ S.T)
    a = [None] * C
    b = [None] * C
    for j in range(C):
        v = np.exp(colE(j))
        if j:
            v = v * (a[j - 1] @ trans(j - 1))
        a[j] = v / v.sum()
    b[C - 1] = np.ones(2 ** R)
    for j in range(C - 2, -1, -1):
        v = trans(j) @ (np.exp(colE(j + 1)) * b[j + 1])
        b[j] = v / v.sum()
    out = np.zeros((R, C))
    for j in range(C):
        q = a[j] * b[j]
        q = q / q.sum()
        out[:, j] = (q[:, None] * (S > 0)).sum(0)
    return out


# =========================================================================== factor-graph BP (Section 9.4.2)
def factor_graph_bp(factors, card, iters=100, damping=1.0, tol=1e-10):
    """Sum-product on a bipartite factor graph, (9.68)-(9.70), flooding schedule.
    factors: list of (variables tuple, table with one axis per variable); card: dict/list of cardinalities.
    Returns the beliefs bel[x] (9.70), the iterations used and whether it converged (exact on trees)."""
    nvars = len(card)
    nbr_f = {x: [k for k, (vs, _) in enumerate(factors) if x in vs] for x in range(nvars)}
    v2f = {(x, k): np.ones(card[x]) / card[x] for x in range(nvars) for k in nbr_f[x]}
    f2v = {(k, x): np.ones(card[x]) / card[x] for k, (vs, _) in enumerate(factors) for x in vs}
    it = 0
    for it in range(1, iters + 1):
        for (x, k) in v2f:                                        # (9.68)
            m = np.ones(card[x])
            for h in nbr_f[x]:
                if h != k:
                    m = m * f2v[(h, x)]
            v2f[(x, k)] = m / m.sum()
        delta = 0.0
        for k, (vs, tab) in enumerate(factors):                   # (9.69)
            for pos, x in enumerate(vs):
                t = tab
                for q, y in enumerate(vs):
                    if y != x:
                        sh = [1] * len(vs)
                        sh[q] = card[y]
                        t = t * v2f[(y, k)].reshape(sh)
                m = t.sum(axis=tuple(q for q in range(len(vs)) if q != pos))
                m = m / m.sum()
                m = damping * m + (1 - damping) * f2v[(k, x)]
                delta = max(delta, np.abs(m - f2v[(k, x)]).max())
                f2v[(k, x)] = m
        if delta < tol:
            break
    bel = []
    for x in range(nvars):
        b = np.ones(card[x])
        for k in nbr_f[x]:
            b = b * f2v[(k, x)]
        bel.append(b / b.sum())
    return bel, it, delta < tol


def factor_marginals_bruteforce(factors, card):
    """The full joint table and the single-variable marginals of a factor graph by enumeration (small models)."""
    nvars = len(card)
    L = "abcdefghijklmnopqrstuvwxyz"
    subs = ",".join("".join(L[x] for x in vs) for vs, _ in factors)
    P = np.einsum(subs + "->" + L[:nvars], *[t for _, t in factors])
    P = P / P.sum()
    return [P.sum(axis=tuple(a for a in range(nvars) if a != x)) for x in range(nvars)], P


# =========================================================================== Gaussian BP (Section 9.4.3)
def gaussian_bp(J, h, iters=200, damping=1.0, tol=1e-12):
    """Gaussian belief propagation for p(x) proportional to exp(-x'Jx/2 + h'x) with the pairwise structure given by the
    non-zeros of J. Messages are (precision, shift) pairs
        P_{i->j} = -J_ij^2 / (J_ii + sum_{k != j} P_{k->i}),   m_{i->j} = -J_ij (h_i + sum_{k != j} m_{k->i}) / (J_ii + sum_{k != j} P_{k->i}).
    Returns the beliefs (means, variances), the number of sweeps and the history of the mean error."""
    n = len(h)
    nb = [[j for j in range(n) if j != i and J[i, j] != 0] for i in range(n)]
    P = {(i, j): 0.0 for i in range(n) for j in nb[i]}
    M = {(i, j): 0.0 for i in range(n) for j in nb[i]}
    mu_true = np.linalg.solve(J, h)
    err = []
    for it in range(iters):
        P2, M2 = {}, {}
        for (i, j) in P:
            a = J[i, i] + sum(P[(k, i)] for k in nb[i] if k != j)
            b = h[i] + sum(M[(k, i)] for k in nb[i] if k != j)
            P2[(i, j)] = damping * (-J[i, j] ** 2 / a) + (1 - damping) * P[(i, j)]
            M2[(i, j)] = damping * (-J[i, j] * b / a) + (1 - damping) * M[(i, j)]
        d = max(abs(P2[e] - P[e]) + abs(M2[e] - M[e]) for e in P) if P else 0
        P, M = P2, M2
        prec = np.array([J[i, i] + sum(P[(k, i)] for k in nb[i]) for i in range(n)])
        mean = np.array([(h[i] + sum(M[(k, i)] for k in nb[i])) / prec[i] for i in range(n)])
        err.append(np.abs(mean - mu_true).max())
        if d < tol:
            break
    return mean, 1.0 / prec, it + 1, np.array(err)


# =========================================================================== polytrees (Supplement 9.1.1)
class Polytree:
    """A discrete polytree Bayes net with the pi/lambda message passing of Pearl (Supplement (9.1)-(9.24)).

    parents[x] is the list of parents of x, cpt[x] a table with axes (parents..., x), evidence[x] an optional
    likelihood vector p(e_x | x) (the local evidence lambda_{X->X})."""

    def __init__(self, parents, cpt, card, evidence=None):
        self.pa, self.cpt, self.card = parents, cpt, card
        self.ev = evidence or {}
        self.ch = {x: [] for x in parents}
        for x, ps in parents.items():
            for p in ps:
                self.ch[p].append(x)

    def local_ev(self, x):
        return self.ev.get(x, np.ones(self.card[x]))

    def lam(self, x, excl=None):
        """lambda_X(x) (9.6), leaving out the message from child `excl`."""
        out = self.local_ev(x).copy()
        for y in self.ch[x]:
            if y != excl:
                out = out * self.lam_msg(y, x)
        return out

    def pi(self, x):
        """pi_X(x) (9.11)."""
        if not self.pa[x]:
            return self.cpt[x].copy()
        T = self.cpt[x]
        for i, u in enumerate(self.pa[x]):
            m = self.pi_msg(u, x)
            sh = [1] * T.ndim
            sh[i] = self.card[u]
            T = T * m.reshape(sh)
        return T.sum(axis=tuple(range(len(self.pa[x]))))

    def pi_msg(self, x, child):
        """Pi_{X->child}(x) (9.24): the belief in x with the evidence below `child` suppressed."""
        m = self.pi(x) * self.lam(x, excl=child)
        return m / m.sum()

    def lam_msg(self, x, u):
        """lambda_{X->U_i}(u_i) (9.22) for the parent u of x."""
        T = self.cpt[x] * self.lam(x).reshape([1] * len(self.pa[x]) + [self.card[x]])
        i0 = self.pa[x].index(u)
        for i, uk in enumerate(self.pa[x]):
            if uk != u:
                sh = [1] * T.ndim
                sh[i] = self.card[uk]
                T = T * self.pi_msg(uk, x).reshape(sh)
        m = T.sum(axis=tuple(a for a in range(T.ndim) if a != i0))
        return m / m.sum()

    def belief(self, x):
        b = self.lam(x) * self.pi(x)
        return b / b.sum()

    def joint(self):
        names = list(self.pa)
        L = "abcdefghijklmnopqrstuvwxyz"
        pos = {x: L[i] for i, x in enumerate(names)}
        subs = [("".join(pos[p] for p in self.pa[x]) + pos[x]) for x in names]
        ops = [self.cpt[x] for x in names]
        for x in names:
            if x in self.ev:
                subs.append(pos[x])
                ops.append(self.ev[x])
        return names, np.einsum(",".join(subs) + "->" + "".join(pos[x] for x in names), *ops)

    def exact_marginals(self):
        names, P = self.joint()
        P = P / P.sum()
        return {x: P.sum(axis=tuple(a for a in range(len(names)) if a != i)) for i, x in enumerate(names)}


# =========================================================================== variable elimination (Section 9.5)
class Factor:
    """A non-negative table over named variables (a potential, a CPT or an intermediate tau of Table 9.1)."""

    def __init__(self, vars_, table):
        self.vars = tuple(vars_)
        self.table = np.asarray(table, float)
        assert self.table.ndim == len(self.vars)

    def __repr__(self):
        return "Factor(%s)" % ",".join(self.vars)


def _letters(names):
    L = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    return {n: L[i] for i, n in enumerate(sorted(names))}


def factor_product(fs):
    allv = sorted(set(v for f in fs for v in f.vars))
    pos = _letters(allv)
    out = np.einsum(",".join("".join(pos[v] for v in f.vars) for f in fs) + "->" + "".join(pos[v] for v in allv), *[f.table for f in fs])
    return Factor(allv, out)


def factor_sum_out(f, v, mode="sum"):
    ax = f.vars.index(v)
    t = f.table.sum(axis=ax) if mode == "sum" else f.table.max(axis=ax)
    return Factor([u for u in f.vars if u != v], t)


def factor_reduce(f, evidence):
    """Clamp the variables of `evidence` (a dict var -> state) in f."""
    idx = tuple(evidence[v] if v in evidence else slice(None) for v in f.vars)
    return Factor([v for v in f.vars if v not in evidence], f.table[idx])


def factor_divide(f, g):
    """f / g on the union of their variables (g's variables must be contained in f's), with 0/0 = 0."""
    pos = _letters(f.vars)
    gt = np.einsum("".join(pos[v] for v in g.vars) + "->" + "".join(pos[v] for v in f.vars if v in g.vars), g.table)
    sh = [f.table.shape[i] if v in g.vars else 1 for i, v in enumerate(f.vars)]
    gb = gt.reshape(sh)
    with np.errstate(divide="ignore", invalid="ignore"):
        out = np.where(gb == 0, 0.0, f.table / np.where(gb == 0, 1, gb))
    return Factor(f.vars, out)


def variable_elimination(factors, order, evidence=None, mode="sum"):
    """Variable elimination (Section 9.5.1): for each variable in `order`, multiply the factors that mention it
    (tau'), sum it out (tau) and put tau back. Returns the product of what remains and the trace
    [(variable, scope of tau', size of tau')]; the trace is Table 9.1 / 9.2."""
    fs = [factor_reduce(f, evidence) if evidence else f for f in factors]
    trace = []
    for v in order:
        involved = [f for f in fs if v in f.vars]
        if not involved:
            continue
        rest = [f for f in fs if v not in f.vars]
        tp = factor_product(involved)
        tau = factor_sum_out(tp, v, mode)
        trace.append((v, tp.vars, len(tp.vars)))
        fs = rest + [tau]
    return factor_product(fs), trace


def student8():
    """The 8-variable student network of Figure 4.38 / Section 9.5: C -> D, (D, I) -> G, I -> S, G -> L, (L, S) -> J,
    (G, J) -> H, all variables binary. The book gives only the structure for this example; the tables below are our own
    illustrative numbers (state 1 = 'high', 'hard', 'good', 'yes')."""
    parents = {"C": [], "D": ["C"], "I": [], "G": ["D", "I"], "S": ["I"], "L": ["G"], "J": ["L", "S"], "H": ["G", "J"]}
    cpt = {
        "C": np.array([0.6, 0.4]),
        "D": np.array([[0.7, 0.3], [0.4, 0.6]]),                                        # [C, D]
        "I": np.array([0.7, 0.3]),
        "G": np.array([[[0.4, 0.6], [0.7, 0.3]], [[0.1, 0.9], [0.3, 0.7]]]),         # [D, I, G]
        "S": np.array([[0.9, 0.1], [0.2, 0.8]]),                                        # [I, S]
        "L": np.array([[0.9, 0.1], [0.2, 0.8]]),                                        # [G, L]
        "J": np.array([[[0.95, 0.05], [0.6, 0.4]], [[0.5, 0.5], [0.1, 0.9]]]),       # [L, S, J]
        "H": np.array([[[0.8, 0.2], [0.4, 0.6]], [[0.5, 0.5], [0.05, 0.95]]]),       # [G, J, H]
    }
    # the book's dictionary of the C, D table orientation: cpt["D"][c] is p(D | C = c); cpt["G"][d, i] = p(G | D = d, I = i)
    facs = []
    for x in parents:
        facs.append(Factor(tuple(parents[x]) + (x,), cpt[x]))
    return parents, cpt, facs


def moral_graph(parents):
    adj = {v: set() for v in parents}
    for v, ps in parents.items():
        for p in ps:
            adj[v].add(p)
            adj[p].add(v)
        for a, b in itertools.combinations(ps, 2):
            adj[a].add(b)
            adj[b].add(a)
    return adj


def induced_graph(adj, order):
    """Run VE symbolically (Section 9.5.2): eliminate the nodes of `order` one by one, joining all remaining neighbours
    of the eliminated node (fill-in edges). Returns the elimination cliques C_i = {v_i} + remaining neighbours, the list
    of fill-in edges, and the maximal cliques of the induced (chordal) graph."""
    g = {v: set(n) for v, n in adj.items()}
    cliques, fills = [], []
    for v in order:
        nb = sorted(g[v])
        cliques.append((v, frozenset([v] + nb)))
        for a, b in itertools.combinations(nb, 2):
            if b not in g[a]:
                g[a].add(b)
                g[b].add(a)
                fills.append((a, b))
        for u in nb:
            g[u].discard(v)
        del g[v]
    cl = [c for _, c in cliques]
    maximal = []
    for c in cl:
        if not any(c < d for d in cl) and c not in maximal:
            maximal.append(c)
    return cliques, fills, maximal


def eliminate_nodes(adj, nodes):
    """The graph left after eliminating `nodes` (in this order) with fill-in edges added; eliminated nodes are removed."""
    g = {v: set(n) for v, n in adj.items()}
    for v in nodes:
        nb = sorted(g[v])
        for a, b in itertools.combinations(nb, 2):
            g[a].add(b)
            g[b].add(a)
        for u in nb:
            g[u].discard(v)
        del g[v]
    return g


def induced_width(adj, order):
    return max(len(c) for _, c in induced_graph(adj, order)[0]) - 1


def ve_cost(adj, order, card=2):
    """The cost (9.92) of VE: the sum over maximal cliques c of the induced graph of K^|c|."""
    return sum(card ** len(c) for c in induced_graph(adj, order)[2])


def min_fill_order(adj, weights=None):
    """The greedy min-fill heuristic of Section 9.5.3: eliminate a node with no fill-in if there is one, else the node
    that adds the fewest fill-in edges (ties broken alphabetically)."""
    g = {v: set(n) for v, n in adj.items()}
    order = []
    while g:
        best, bestf = None, None
        for v in sorted(g):
            nb = sorted(g[v])
            f = sum(1 for a, b in itertools.combinations(nb, 2) if b not in g[a])
            if bestf is None or f < bestf:
                best, bestf = v, f
                if f == 0:
                    break
        nb = sorted(g[best])
        for a, b in itertools.combinations(nb, 2):
            g[a].add(b)
            g[b].add(a)
        for u in nb:
            g[u].discard(best)
        del g[best]
        order.append(best)
    return order


def treewidth_exact(adj):
    """Exact treewidth by dynamic programming over subsets (Bodlaender et al.), for graphs with up to about 16 nodes:
    TW(S) = min over v in S of max(TW(S - v), |Q(S - v, v)|), where Q(S, v) are the nodes outside S + v that
    can be reached from v through S."""
    nodes = sorted(adj)
    n = len(nodes)
    ix = {v: i for i, v in enumerate(nodes)}
    nb = [sum(1 << ix[u] for u in adj[v]) for v in nodes]
    full = (1 << n) - 1
    TW = {0: -1}

    def q(S, v):
        seen, stack, out = 1 << v, [v], 0
        while stack:
            x = stack.pop()
            m = nb[x] & ~seen
            while m:
                b = m & -m
                m ^= b
                i = b.bit_length() - 1
                seen |= b
                if (S >> i) & 1:
                    stack.append(i)
                else:
                    out |= b
        return bin(out).count("1")
    for S in range(1, full + 1):
        best = n
        m = S
        while m:
            b = m & -m
            m ^= b
            v = b.bit_length() - 1
            S2 = S ^ b
            best = min(best, max(TW[S2], q(S2, v)))
        TW[S] = best
    return TW[full]


def grid_graph(w, h):
    adj = {(i, j): set() for i in range(w) for j in range(h)}
    for i in range(w):
        for j in range(h):
            for di, dj in ((1, 0), (0, 1)):
                if (i + di, j + dj) in adj:
                    adj[(i, j)].add((i + di, j + dj))
                    adj[(i + di, j + dj)].add((i, j))
    return adj


# =========================================================================== junction trees (Section 9.6, Supplement 9.2)
def junction_tree(cliques):
    """A maximum-weight spanning tree of the junction graph (edge weight = size of the intersection) over the given
    cliques (Kruskal). For the maximal cliques of a chordal graph this is a junction tree [Jensen and Jensen, 1994]."""
    n = len(cliques)
    cand = sorted(((len(cliques[i] & cliques[j]), i, j) for i in range(n) for j in range(i + 1, n) if cliques[i] & cliques[j]), reverse=True)
    parent = list(range(n))

    def find(a):
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a
    edges = []
    for w, i, j in cand:
        ri, rj = find(i), find(j)
        if ri != rj:
            parent[ri] = rj
            edges.append((i, j))
    return edges


def running_intersection(cliques, edges):
    """True iff for every variable the cliques containing it form a connected subtree."""
    n = len(cliques)
    nb = {i: [] for i in range(n)}
    for i, j in edges:
        nb[i].append(j)
        nb[j].append(i)
    if len(edges) != n - 1:
        return False
    for v in set().union(*cliques):
        have = [i for i in range(n) if v in cliques[i]]
        seen, stack = {have[0]}, [have[0]]
        while stack:
            x = stack.pop()
            for y in nb[x]:
                if y not in seen and v in cliques[y]:
                    seen.add(y)
                    stack.append(y)
        if len(seen) != len(have):
            return False
    return True


def calibrate_junction_tree(cliques, edges, factors, root=0, verbose=False):
    """The Lauritzen-Spiegelhalter calibration (Supplement 9.2.2, Figure 9.7): assign each factor to one clique that contains it,
    multiply, then collect to the root (post-order) and distribute (pre-order) with 'divide out the old separator,
    multiply in the new one'. Returns the calibrated clique potentials, the separator potentials and the
    normalising constant. Every calibrated potential is proportional to the clique marginal."""
    n = len(cliques)
    # the cardinality of each variable is read from the factors
    card = {}
    for f in factors:
        for v, k in zip(f.vars, f.table.shape):
            card[v] = k
    pot = [Factor(sorted(c), np.ones([card[v] for v in sorted(c)])) for c in cliques]
    for f in factors:
        k = next(i for i, c in enumerate(cliques) if set(f.vars) <= c)
        pot[k] = factor_product([pot[k], f])
    nb = {i: [] for i in range(n)}
    for i, j in edges:
        nb[i].append(j)
        nb[j].append(i)
    order, parent = [root], {root: None}
    for s in order:
        for t in nb[s]:
            if t not in parent:
                parent[t] = s
                order.append(t)
    sep = {}

    def marg_to(f, keep):
        g = f
        for v in f.vars:
            if v not in keep:
                g = factor_sum_out(g, v)
        return g
    for nde in reversed(order):                                    # collect evidence
        p = parent[nde]
        if p is None:
            continue
        S = cliques[nde] & cliques[p]
        msg = marg_to(pot[nde], S)
        old = sep.get((nde, p))
        if old is not None:
            pot[p] = factor_product([pot[p], factor_divide(msg, old)])
        else:
            pot[p] = factor_product([pot[p], msg])
        sep[(nde, p)] = msg
        sep[(p, nde)] = msg
    for nde in order:                                              # distribute evidence
        p = parent[nde]
        if p is None:
            continue
        S = cliques[nde] & cliques[p]
        msg = marg_to(pot[p], S)
        old = sep[(p, nde)]
        pot[nde] = factor_product([pot[nde], factor_divide(msg, old)])
        sep[(p, nde)] = msg
        sep[(nde, p)] = msg
    Z = pot[root].table.sum()
    return pot, sep, Z


# =========================================================================== inference by differentiation (Section 9.7.1)
def autodiff_marginals(log_pots, spec="A,B,C,AB,BC"):
    """Listing 9.1 in PyTorch: log Z(eta) = log einsum(exp(eta)); its gradient with respect to each log potential
    is the corresponding marginal (9.94), mu = grad A(eta). Returns logZ and the list of gradients."""
    import torch
    lps = [torch.tensor(np.asarray(lp, float), dtype=torch.float64, requires_grad=True) for lp in log_pots]
    logZ = torch.log(torch.einsum(spec, *[torch.exp(lp) for lp in lps]))
    grads = torch.autograd.grad(logZ, lps)
    return float(logZ.detach()), [g.numpy() for g in grads]


# =========================================================================== perturb and MAP (Section 9.7.2)
def pam_gaussian(G, Sp, mu_p, H, Sn, y, c, n, rng):
    """Perturb-and-MAP for the Gaussian MRF (9.96)-(9.104): n exact samples from the posterior N(mu, K^-1) obtained by
    perturbing the prior mean and the data with the noise models and returning the MAP (posterior mean) of each
    perturbed problem."""
    Spi, Sni = np.linalg.inv(Sp), np.linalg.inv(Sn)
    K = G.T @ Spi @ G + H.T @ Sni @ H
    Kinv = np.linalg.inv(K)
    mu = Kinv @ (G.T @ Spi @ mu_p + H.T @ Sni @ (y - c))
    Lp, Ln = np.linalg.cholesky(Sp), np.linalg.cholesky(Sn)
    out = np.zeros((n, K.shape[0]))
    for s in range(n):
        mup = mu_p + Lp @ rng.standard_normal(len(mu_p))
        yt = y + Ln @ rng.standard_normal(len(y))
        out[s] = Kinv @ (G.T @ Spi @ mup + H.T @ Sni @ (yt - c))
    return mu, Kinv, out


def gumbel_noise(shape, rng):
    return -np.log(-np.log(rng.uniform(size=shape)))


def gumbel_max_samples(logp, n, rng):
    """argmax_x (log p(x) + eps_x) with iid Gumbel eps_x is an exact sample from p (the Gumbel-max trick)."""
    flat = np.asarray(logp).ravel()
    idx = (flat[None, :] + gumbel_noise((n, flat.size), rng)).argmax(1)
    return np.bincount(idx, minlength=flat.size) / n


def pam_unary_gumbel(node_logpot, edge_logpot_dense, n, rng):
    """The cheap approximation of Section 9.7.2.2: Gumbel noise only on the unary potentials of a pairwise model, then the
    exact MAP (by enumeration here). Returns the empirical distribution of the MAP states over the n perturbations."""
    nn = len(node_logpot)
    K = len(node_logpot[0])
    states = np.array(list(itertools.product(range(K), repeat=nn)))
    base = edge_logpot_dense(states)
    counts = np.zeros(len(states))
    for _ in range(n):
        s = base.copy()
        for i in range(nn):
            s = s + node_logpot[i][states[:, i]] + gumbel_noise(K, rng)[states[:, i]]
        counts[s.argmax()] += 1
    return counts / n


# =========================================================================== affinity propagation (Section 9.4.9)
def affinity_propagation(S, damping=0.5, iters=200, conv_iter=15, keep_history=False):
    """Affinity propagation (Frey and Dueck, 2007): max-product loopy BP on the factor graph of Figure 9.16, reduced to the
    responsibility r(i, k) and availability a(i, k) messages. S is the N x N similarity matrix, with the 'preferences'
    S(k, k) on the diagonal."""
    N = len(S)
    R = np.zeros((N, N))
    A = np.zeros((N, N))
    hist = []
    idx = np.arange(N)
    last, stable = None, 0
    for it in range(iters):
        AS = A + S
        I = AS.argmax(1)
        Y = AS[idx, I].copy()
        AS[idx, I] = -np.inf
        Y2 = AS.max(1)
        Rn = S - Y[:, None]
        Rn[idx, I] = S[idx, I] - Y2
        R = damping * R + (1 - damping) * Rn
        Rp = np.maximum(R, 0)
        Rp[idx, idx] = R[idx, idx]
        An = Rp.sum(0)[None, :] - Rp
        dA = An[idx, idx].copy()
        An = np.minimum(An, 0)
        An[idx, idx] = dA
        A = damping * A + (1 - damping) * An
        ex = np.flatnonzero((A + R).diagonal() > 0)
        if keep_history:
            hist.append((R.copy(), A.copy(), ex.copy()))
        if last is not None and len(ex) == len(last) and np.all(ex == last):
            stable += 1
        else:
            stable = 0
        last = ex
        if stable >= conv_iter and len(ex) > 0:
            break
    ex = np.flatnonzero((A + R).diagonal() > 0)
    lab = ex[S[:, ex].argmax(1)] if len(ex) else np.zeros(N, int)
    lab[ex] = ex
    return ex, lab, it + 1, hist


# =========================================================================== MAP: polytopes, LP relaxation, graph cuts (Supplement 9.3)
def local_polytope_lp(theta_s, theta_st, edges):
    """max theta'tau over the local polytope L(G) (9.63)-(9.66) by linear programming (HiGHS). theta_s: (V, K); theta_st:
    dict edge -> (K, K). Returns the optimal value and the pseudo-marginals (tau_s, tau_st)."""
    from scipy.optimize import linprog
    V, K = theta_s.shape
    nv = V * K + len(edges) * K * K
    c = np.zeros(nv)
    c[:V * K] = -theta_s.ravel()
    off = {}
    for e, (s, t) in enumerate(edges):
        o = V * K + e * K * K
        off[(s, t)] = o
        c[o:o + K * K] = -np.asarray(theta_st[(s, t)]).ravel()
    Aeq, beq = [], []
    for s in range(V):
        r = np.zeros(nv)
        r[s * K:(s + 1) * K] = 1
        Aeq.append(r)
        beq.append(1)
    for (s, t), o in off.items():
        for j in range(K):                                         # sum_k tau_st(j, k) = tau_s(j)
            r = np.zeros(nv)
            r[o + j * K:o + (j + 1) * K] = 1
            r[s * K + j] -= 1
            Aeq.append(r)
            beq.append(0)
        for k in range(K):                                         # sum_j tau_st(j, k) = tau_t(k)
            r = np.zeros(nv)
            r[o + k:o + K * K:K] = 1
            r[t * K + k] -= 1
            Aeq.append(r)
            beq.append(0)
    res = linprog(c, A_eq=np.array(Aeq), b_eq=np.array(beq), bounds=(0, None), method="highs")
    tau_s = res.x[:V * K].reshape(V, K)
    tau_st = {e: res.x[o:o + K * K].reshape(K, K) for e, o in off.items()}
    return -res.fun, tau_s, tau_st


def map_bruteforce(theta_s, theta_st, edges):
    V, K = theta_s.shape
    best, arg = -np.inf, None
    for x in itertools.product(range(K), repeat=V):
        v = sum(theta_s[s, x[s]] for s in range(V)) + sum(theta_st[(s, t)][x[s], x[t]] for (s, t) in edges)
        if v > best + 1e-12:
            best, arg = v, [x]
        elif abs(v - best) <= 1e-12:
            arg.append(x)
    return best, arg


def max_flow_edmonds_karp(cap, s, t):
    """Maximum flow by shortest augmenting paths (Edmonds-Karp) on a dense capacity matrix; returns the flow value and the set
    of nodes on the source side of a minimum cut (reachable in the residual graph)."""
    n = len(cap)
    res = np.array(cap, float)
    flow = 0.0
    while True:
        prev = [-1] * n
        prev[s] = s
        queue = [s]
        for u in queue:
            for v in range(n):
                if prev[v] < 0 and res[u, v] > 1e-12:
                    prev[v] = u
                    queue.append(v)
        if prev[t] < 0:
            return flow, set(i for i in range(n) if prev[i] >= 0)
        b, v = np.inf, t
        while v != s:
            b = min(b, res[prev[v], v])
            v = prev[v]
        v = t
        while v != s:
            res[prev[v], v] -= b
            res[v, prev[v]] += b
            v = prev[v]
        flow += b


def is_submodular(E):
    """E[a, b] = E_uv(x_u = a, x_v = b): (9.71) E(1,1) + E(0,0) <= E(1,0) + E(0,1)."""
    return E[1, 1] + E[0, 0] <= E[1, 0] + E[0, 1] + 1e-12


def graphcut_map(E0, E1, pairs, maxflow=max_flow_edmonds_karp):
    """Exact minimum-energy configuration of a binary MRF with unary energies E0[u], E1[u] and submodular pairwise
    energies pairs[(u, v)] = 2 x 2 table (Supplement 9.3.4): minimum s-t cut of the graph of Figure 9.13. A node on the source
    side takes state 0, on the sink side state 1. Pairwise terms are decomposed as
    E(0,0) + (E(1,0)-E(0,0))[x_u=1] + (E(1,1)-E(1,0))[x_v=1] + (E(0,1)+E(1,0)-E(0,0)-E(1,1))[x_u=0, x_v=1]."""
    n = len(E0)
    s, t = n, n + 1
    U0 = np.array(E0, float)
    U1 = np.array(E1, float)
    const = 0.0
    cap = np.zeros((n + 2, n + 2))
    for (u, v), E in pairs.items():
        E = np.asarray(E, float)
        assert is_submodular(E), "the pairwise energy must be submodular"
        const += E[0, 0]
        U1[u] += E[1, 0] - E[0, 0]
        U1[v] += E[1, 1] - E[1, 0]
        cap[u, v] += E[0, 1] + E[1, 0] - E[0, 0] - E[1, 1]
    for u in range(n):                                             # unary: pay U1 in state 1 (sink side), U0 in state 0
        const += min(U0[u], U1[u])
        if U1[u] > U0[u]:
            cap[s, u] += U1[u] - U0[u]                              # cut when u is on the sink side
        else:
            cap[u, t] += U0[u] - U1[u]                              # cut when u is on the source side
    flow, src = maxflow(cap, s, t)
    x = np.array([0 if u in src else 1 for u in range(n)])
    return x, flow + const


def ising_energy_graphcut(E0, E1, edges, lam):
    """The symmetric Ising energies (9.68): E_uv = 0 if x_u = x_v, lam_uv otherwise."""
    return {(u, v): np.array([[0.0, l], [l, 0.0]]) for (u, v), l in zip(edges, lam)}


def energy_binary(x, E0, E1, pairs):
    e = sum(E1[u] if x[u] else E0[u] for u in range(len(x)))
    for (u, v), E in pairs.items():
        e += E[x[u], x[v]]
    return e


# =========================================================================== error correcting codes (Section 9.4.8)
def parity_code_posterior(alpha=0.2, y=(1, 0, 0)):
    """The three-bit example of Section 9.3.3.2: z3 = z1 xor z2, uniform priors on z1, z2, bit-flip channel with flip
    probability alpha. Returns the posterior marginals, the max-marginals, the MAP set and the MPM estimate."""
    words = [(a, b, a ^ b) for a in (0, 1) for b in (0, 1)]
    joint = {}
    for w in words:
        p = 0.25
        for zi, yi in zip(w, y):
            p *= (1 - alpha) if zi == yi else alpha
        joint[w] = p
    Z = sum(joint.values())
    marg = np.zeros((3, 2))
    mx = np.zeros((3, 2))
    for w, p in joint.items():
        for i in range(3):
            marg[i, w[i]] += p / Z
            mx[i, w[i]] = max(mx[i, w[i]], p / Z)
    best = max(joint.values())
    return marg, mx, [w for w, p in joint.items() if abs(p - best) < 1e-15], tuple(int(m.argmax()) for m in marg)


def ldpc_gallager(n, dv=3, dc=6, seed=0):
    """A regular (dv, dc) low-density parity check matrix of Gallager: dv stacked blocks, the first with the checks on
    consecutive groups of dc bits and the others with a random column permutation."""
    rng = np.random.default_rng(seed)
    m0 = n // dc
    base = np.zeros((m0, n), int)
    for i in range(m0):
        base[i, i * dc:(i + 1) * dc] = 1
    blocks = [base] + [base[:, rng.permutation(n)] for _ in range(dv - 1)]
    return np.vstack(blocks)


def ldpc_bp_decode(H, llr, iters=50):
    """Sum-product decoding of an LDPC code (loopy BP on the factor graph of Figure 9.15, in the log-likelihood-ratio form
    tanh(m_{c->v} / 2) = prod_{v' != v} tanh(m_{v'->c} / 2)). llr: (trials, n) channel LLRs log p(y|0)/p(y|1).
    Returns the hard decisions (trials, n)."""
    m, n = H.shape
    rows = [np.flatnonzero(H[i]) for i in range(m)]
    dc = len(rows[0])
    R = np.array(rows)                                             # (m, dc) variable indices of each check
    T = llr.shape[0]
    c2v = np.zeros((m, dc, T))
    for _ in range(iters):
        total = llr.T.copy()                                       # (n, T)
        for k in range(dc):
            np.add.at(total, R[:, k], c2v[:, k, :])
        v2c = total[R] - c2v                                       # (m, dc, T)
        th = np.tanh(np.clip(v2c, -30, 30) / 2)
        pre = np.ones_like(th)
        suf = np.ones_like(th)
        for k in range(1, dc):
            pre[:, k] = pre[:, k - 1] * th[:, k - 1]
        for k in range(dc - 2, -1, -1):
            suf[:, k] = suf[:, k + 1] * th[:, k + 1]
        ex = np.clip(pre * suf, -1 + 1e-12, 1 - 1e-12)
        c2v = 2 * np.arctanh(ex)
    total = llr.T.copy()
    for k in range(dc):
        np.add.at(total, R[:, k], c2v[:, k, :])
    return (total < 0).astype(int).T


# =========================================================================== reproducible set-ups shared by figures, exports and checks
CASINO_SEED = 1
CASINO_T = 300
GRID_SEED, GRID_SCALE, GRID_N = 1, 1.7, 11


def casino_data():
    pi, A, B = casino_hmm()
    z, y = sample_hmm(pi, A, B, CASINO_T, np.random.default_rng(CASINO_SEED))
    return pi, A, B, z, y


def grid_potentials(R=GRID_N, C=GRID_N, scale=GRID_SCALE, seed=GRID_SEED):
    """Unit-scale random couplings U(-1, 1) and fields U(-1/2, 1/2) of the Ising grid of Figure 9.13; the couplings used are
    scale * (unit couplings). Seeded, so figures, demonstration and checks all use the same numbers."""
    rng = np.random.default_rng(seed)
    uh = rng.uniform(-1, 1, (R, C))
    uv = rng.uniform(-1, 1, (R, C))
    h = rng.uniform(-0.5, 0.5, (R, C))
    return uh, uv, h


def _loaded_spans(z):
    spans, t = [], 0
    while t < len(z):
        if z[t] == 1:
            s = t
            while t < len(z) and z[t] == 1:
                t += 1
            spans.append((s, t))
        else:
            t += 1
    return spans


# =========================================================================== figures
def fig_9_3(out=None):
    """Inference in the dishonest casino: filtered, smoothed and Viterbi estimates for a sequence of 300 rolls."""
    pi, A, B, z, y = casino_data()
    lik = B[:, y].T
    r = forwards_backwards(pi, A, lik)
    path, _, _ = viterbi(pi, A, lik)
    spans = _loaded_spans(z)
    fig, axes = plt.subplots(3, 1, figsize=(7.2, 6.0), sharex=True)
    series = [(r["alpha"][:, 1], "p(loaded)", "Filtered", "(a)"), (r["gamma"][:, 1], "p(loaded)", "Smoothed", "(b)"), (path.astype(float), "MAP state", "Viterbi", "(c)")]
    for ax, (v, yl, title, lab) in zip(axes, series):
        for a, b in spans:
            ax.axvspan(a - 0.5, b - 0.5, color="#cccccc", lw=0)
        ax.plot(np.arange(1, len(v) + 1) - 1, v, color=BLUE, lw=1.3, drawstyle="steps-mid" if title == "Viterbi" else "default")
        ax.set_ylim(-0.04, 1.04)
        ax.set_ylabel(yl)
        ax.set_title(title, fontsize=9.5, loc="left")
        common.panel_label(ax, lab[1], "upper right")
    axes[-1].set_xlabel("observation number")
    axes[-1].set_xlim(0, len(z))
    fig.tight_layout()
    savefig(fig, CH, "fig9-3", out)
    return dict(mpm_errors=int((r["gamma"].argmax(1) != z).sum()), map_errors=int((path != z).sum()))


def fig_9_6(out=None):
    """The Viterbi trellis for the three-state speech HMM and the observations C1, C3, C4, C6."""
    pi, A, B = speech_hmm()
    obs = [0, 2, 3, 5]
    lik = B[:, obs].T
    d = viterbi_prob(pi, A, lik)
    path, _, _ = viterbi(pi, A, lik)
    T, K = lik.shape
    fig, ax = plt.subplots(figsize=(7.0, 3.6))
    xs = np.arange(T) * 2.0
    ys = -np.arange(K) * 1.5
    for t in range(1, T):
        for i in range(K):
            for j in range(K):
                if A[i, j] > 0 and d[t - 1, i] > 0 and lik[t, j] > 0:
                    on = path[t - 1] == i and path[t] == j
                    ax.annotate("", xy=(xs[t] - 0.33, ys[j]), xytext=(xs[t - 1] + 0.33, ys[i]),
                                arrowprops=dict(arrowstyle="-|>", color=RED if on else "#888888", lw=1.8 if on else 0.8, shrinkA=0, shrinkB=0))
                    mx, my = (xs[t - 1] + xs[t]) / 2 + (0.0 if i == j else 0.0), (ys[i] + ys[j]) / 2
                    ax.text(mx, my + (0.13 if i == j else 0.0), "%g, %g" % (A[i, j], lik[t, j]), fontsize=6.5, ha="center", va="bottom", color=RED if on else "#555555",
                            bbox=dict(fc="white", ec="none", pad=0.4, alpha=0.8))
    for t in range(T):
        for k in range(K):
            on = path[t] == k
            ax.add_patch(plt.Circle((xs[t], ys[k]), 0.33, fc="white", ec=RED if on else BLUE, lw=1.8 if on else 1.0, zorder=3))
            ax.text(xs[t], ys[k] + 0.08, "S%d" % (k + 1), ha="center", va="center", fontsize=8, zorder=4)
            ax.text(xs[t], ys[k] - 0.14, "%.4g" % d[t, k], ha="center", va="center", fontsize=6.5, zorder=4, color="#333333")
    for t, o in enumerate(obs):
        ax.text(xs[t], 0.75, "$t=%d$,  $y_t=$C%d" % (t + 1, o + 1), ha="center", fontsize=8.5)
    ax.set_xlim(-0.8, xs[-1] + 0.8)
    ax.set_ylim(ys[-1] - 0.6, 1.1)
    ax.set_aspect("equal")
    ax.axis("off")
    fig.tight_layout()
    savefig(fig, CH, "fig9-6", out)
    return d, path


def gauss_interp_problem(G=40, N=14, sigma=0.12, tau=0.35, seed=2):
    """The 1d interpolation model (9.71)-(9.76): grid z_0..z_G on [0, 10], N noisy measurements of a sine wave."""
    rng = np.random.default_rng(seed)
    g = np.linspace(0, 10, G + 1)
    xm = np.sort(rng.uniform(0.3, 9.7, N))
    ym = np.sin(xm) + sigma * rng.standard_normal(N)
    J = np.zeros((G + 1, G + 1))
    h = np.zeros(G + 1)
    dg = g[1] - g[0]
    for x, yv in zip(xm, ym):
        k = min(int(x // dg), G - 1)
        gam = (x - g[k]) / dg
        v = np.zeros(G + 1)
        v[k], v[k + 1] = 1 - gam, gam                              # predicted measurement = v'z
        J += np.outer(v, v) / sigma ** 2
        h += v * yv / sigma ** 2
    for k in range(G):                                             # smoothness factors (z_k - z_{k+1})^2 / tau^2
        v = np.zeros(G + 1)
        v[k], v[k + 1] = 1, -1
        J += np.outer(v, v) / tau ** 2
    return g, xm, ym, J, h


def fig_9_11(out=None):
    """Interpolating noisy data with Gaussian belief propagation on a 1d chain MRF (exact on a chain)."""
    g, xm, ym, J, h = gauss_interp_problem()
    mean, var, it, err = gaussian_bp(J, h)
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 2.7), sharey=True)
    axes[0].plot(xm, ym, "o", color=BLUE, ms=4)
    axes[0].set_ylabel("measurements")
    axes[0].set_xlabel("$x$")
    axes[0].set_xlim(0, 10)
    common.panel_label(axes[0], "a", "upper right")
    sd = np.sqrt(var)
    axes[1].fill_between(g, mean - 2 * sd, mean + 2 * sd, color="#9ec5f4", alpha=0.7, lw=0, label="BP belief $\\pm2$ sd")
    axes[1].plot(g, mean, color=BLUE, lw=1.6, label="BP mean")
    axes[1].plot(xm, ym, "o", color=RED, ms=3.5, label="measurements")
    axes[1].plot(g, np.sin(g), color="k", lw=0.8, ls="--", label="true function")
    axes[1].set_xlabel("$x$")
    axes[1].set_xlim(0, 10)
    axes[1].legend(loc="lower left", fontsize=7, frameon=False, ncol=2)
    common.panel_label(axes[1], "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig9-11", out)
    return mean, var, it


GRID_SCHEDULES = (("synchronous, undamped", "sync", 1.0, RED, "--"), ("synchronous, damped", "sync", 0.5, ORANGE, ":"),
                  ("asynchronous, undamped", "async", 1.0, PURPLE, "-."), ("asynchronous, damped", "async", 0.5, BLUE, "-"))


def grid_lbp_runs(R=GRID_N, C=GRID_N, iters=100, nodes=None):
    uh, uv, h = grid_potentials(R, C)
    mrf = ising_grid(R, C, GRID_SCALE * uh, GRID_SCALE * uv, h)
    exact = ising_grid_exact(R, C, GRID_SCALE * uh, GRID_SCALE * uv, h)
    runs = {}
    for lab, sch, d, col, ls in GRID_SCHEDULES:
        runs[(sch, d)] = loopy_bp(mrf, iters, damping=d, schedule=sch, tol=1e-3, track=nodes)
    return mrf, exact, runs


def fig_9_13(out=None):
    """Loopy BP on an 11 x 11 Ising grid with random couplings: update schedules and damping."""
    R = C = GRID_N
    uh, uv, h = grid_potentials()
    mrf = ising_grid(R, C, GRID_SCALE * uh, GRID_SCALE * uv, h)
    exact = ising_grid_exact(R, C, GRID_SCALE * uh, GRID_SCALE * uv, h).ravel()
    probe = loopy_bp(mrf, 100, damping=1.0, schedule="sync", tol=1e-3, track=list(range(R * C)))
    rng_osc = [np.ptp([b[1] for b in probe["hist"][s][20:]]) for s in range(R * C)]
    nodes = [int(s) for s in np.argsort(rng_osc)[::-1][:5]]
    runs = {}
    for lab, sch, d, col, ls in GRID_SCHEDULES:
        runs[(sch, d)] = loopy_bp(mrf, 100, damping=d, schedule=sch, tol=1e-3, track=nodes)
    fig = plt.figure(figsize=(9.6, 5.0))
    gs = fig.add_gridspec(2, 5, hspace=0.5, wspace=0.55)
    ax = fig.add_subplot(gs[0, :])
    for lab, sch, d, col, ls in GRID_SCHEDULES:
        f = np.array(runs[(sch, d)]["frac"]) * 100
        ax.plot(np.arange(len(f)), f, color=col, ls=ls, lw=1.6, label=lab)
    ax.set_xlabel("iteration")
    ax.set_ylabel("% messages converged")
    ax.set_xlim(0, 100)
    ax.set_ylim(-3, 103)
    ax.legend(fontsize=7.5, frameon=False, loc="center right")
    common.panel_label(ax, "a", "upper left")
    axs = [fig.add_subplot(gs[1, k]) for k in range(5)]
    for a, s, lab in zip(axs, nodes, "bcdef"):
        a.axhline(exact[s], color="k", lw=1.0, label="exact")
        for lb, sch, d, col, ls in (GRID_SCHEDULES[0], GRID_SCHEDULES[3]):
            hist = np.array([b[1] for b in runs[(sch, d)]["hist"][s]])
            a.plot(np.arange(len(hist)), hist, color=col, ls=ls, lw=1.3)
        a.set_ylim(-0.03, 1.03)
        a.set_xlim(0, 100)
        a.set_xlabel("iteration")
        a.set_ylabel("$p(s_{%d,%d}=+1)$" % (s // C + 1, s % C + 1), fontsize=8)
        common.panel_label(a, lab, "upper right")
    savefig(fig, CH, "fig9-13", out)
    return {k: (v["converged"], v["frac"][-1]) for k, v in runs.items()}


def fig_9_17(out=None):
    """Affinity propagation on two-dimensional data: messages at successive iterations and the final clusters."""
    rng = np.random.default_rng(4)
    X = np.vstack([rng.normal(c, 0.6, (40, 2)) for c in ([-3.0, -2.0], [3.0, -2.0], [0.0, 3.5])])
    S = -((X[:, None] - X[None]) ** 2).sum(-1)
    pref = np.median(S[np.triu_indices(len(S), 1)])
    np.fill_diagonal(S, pref)
    ex, lab, it, hist = affinity_propagation(S, damping=0.5, iters=300, keep_history=True)
    show = [("initialization", None), ("iteration 1", 0), ("iteration 2", 1), ("iteration 3", 2), ("iteration 5", 4), ("iteration 10", 9), ("iteration 20", 19), ("convergence", it - 1)]
    fig, axes = common.panel_grid(2, 4, size=(2.5, 2.4))
    for ax, (title, k) in zip(axes.ravel(), show):
        if k is None:
            ax.scatter(X[:, 0], X[:, 1], s=14, c="#888888", edgecolor="k", lw=0.3)
        else:
            R, A, exk = hist[k]
            crit = (R + A).diagonal()
            choice = (R + A).argmax(1)
            for i in range(len(X)):
                if choice[i] != i:
                    ax.plot([X[i, 0], X[choice[i], 0]], [X[i, 1], X[choice[i], 1]], color="#444444", lw=0.35, alpha=0.7)
            sc = ax.scatter(X[:, 0], X[:, 1], s=14, c=crit, cmap="RdYlGn_r", vmin=-30, vmax=30, edgecolor="k", lw=0.3, zorder=3)
            ax.scatter(X[exk, 0], X[exk, 1], s=70, marker="*", c="k", zorder=4)
        ax.set_title(title, fontsize=8.5)
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig9-17", out)
    return len(ex), it


def _draw_graph(ax, pos, edges, node_style=None, edge_style=None, fs=8, r=0.28):
    for (a, b) in edges:
        st = (edge_style or {}).get((a, b)) or (edge_style or {}).get((b, a)) or dict(color="#555555", lw=1.2)
        ax.plot([pos[a][0], pos[b][0]], [pos[a][1], pos[b][1]], zorder=1, **st)
    for v, (x, y) in pos.items():
        st = (node_style or {}).get(v, dict(fc="white", ec="k", ls="-", tc="k"))
        ax.add_patch(plt.Circle((x, y), r, fc=st["fc"], ec=st["ec"], lw=1.3, ls=st.get("ls", "-"), zorder=2))
        ax.text(x, y, v, ha="center", va="center", fontsize=fs, color=st.get("tc", "k"), zorder=3)
    ax.set_aspect("equal")
    ax.axis("off")


STUDENT_POS = {"C": (0.2, 4.0), "D": (0.2, 3.0), "I": (3.2, 3.0), "G": (1.6, 2.0), "S": (4.0, 2.0), "L": (0.6, 1.0), "J": (3.0, 1.0), "H": (1.8, 0.0)}


def fig_9_18(out=None):
    """The elimination process on the moral student graph in the order C, D, I, H, G, S, L: the fill-in edge G-S."""
    parents, _, _ = student8()
    adj = moral_graph(parents)
    order = ["C", "D", "I", "H", "G", "S", "L", "J"]
    cliques, fills, maximal = induced_graph(adj, order)
    fig, axes = plt.subplots(1, 3, figsize=(8.4, 3.0))
    steps = [(0, "(a) moral graph"), (2, "(b) after eliminating C, D"), (3, "(c) after eliminating I")]
    for ax, (k, title) in zip(axes, steps):
        gone = set(order[:k])
        g = eliminate_nodes(adj, order[:k])
        nstyle = {v: (dict(fc="#e8e8e8", ec="#aaaaaa", ls="--", tc="#999999") if v in gone else dict(fc="white", ec="k", tc="k")) for v in adj}
        es, edge_style = [], {}
        for a in g:
            for b in g[a]:
                if a < b:
                    es.append((a, b))
                    if b not in adj[a]:
                        edge_style[(a, b)] = dict(color=RED, lw=1.8, ls="--")
        _draw_graph(ax, STUDENT_POS, es, nstyle, edge_style, fs=8, r=0.3)
        ax.set_xlim(-0.5, 4.6)
        ax.set_ylim(-0.6, 4.5)
        ax.set_title(title, fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig9-18", out)
    return fills, [sorted(c) for c in maximal]


def fig_S9_4(out=None):
    """Supplementary Figure 9.4: the triangulated student graph, its maximal cliques and the junction tree."""
    parents, _, _ = student8()
    adj = moral_graph(parents)
    order = ["C", "D", "I", "H", "G", "S", "L", "J"]
    cliques, fills, maximal = induced_graph(adj, order)
    mx = [frozenset(c) for c in maximal]
    edges = junction_tree(mx)
    fig = plt.figure(figsize=(8.6, 3.2))
    ax = fig.add_axes([0.0, 0.0, 0.33, 1.0])
    base = sorted({tuple(sorted((a, b))) for a in adj for b in adj[a]})
    es = list(base) + list(fills)
    style = {tuple(f): dict(color=RED, lw=1.8, ls="--") for f in fills}
    _draw_graph(ax, STUDENT_POS, es, None, style, fs=8, r=0.3)
    ax.set_xlim(-0.5, 4.6)
    ax.set_ylim(-0.6, 4.5)
    ax.set_title("(a) moral graph + fill-in (chordal)", fontsize=9)
    ax2 = fig.add_axes([0.34, 0.0, 0.66, 1.0])
    # lay the tree out along its (path-like) structure by breadth-first search from the clique containing C
    nb = {i: [] for i in range(len(mx))}
    for i, j in edges:
        nb[i].append(j)
        nb[j].append(i)
    root = next(i for i, c in enumerate(mx) if "C" in c)
    seen, order_nodes = {root}, [root]
    for s in order_nodes:
        for t in nb[s]:
            if t not in seen:
                seen.add(t)
                order_nodes.append(t)
    pos = {}
    depth = {root: 0}
    for s in order_nodes:
        for t in nb[s]:
            if t not in depth:
                depth[t] = depth[s] + 1
    byd = {}
    for v in order_nodes:
        byd.setdefault(depth[v], []).append(v)
    for dpt, vs in byd.items():
        for q, v in enumerate(vs):
            pos[v] = (dpt * 2.0, (len(vs) - 1) / 2 * 1.4 - q * 1.4)
    for i, j in edges:
        ax2.plot([pos[i][0], pos[j][0]], [pos[i][1], pos[j][1]], color="#555555", lw=1.2, zorder=1)
        sep = "".join(sorted(mx[i] & mx[j]))
        ax2.text((pos[i][0] + pos[j][0]) / 2, (pos[i][1] + pos[j][1]) / 2 + 0.12, sep, fontsize=7.5, color=RED, ha="center", va="bottom", bbox=dict(fc="white", ec="none", pad=0.3))
    for i, c in enumerate(mx):
        x, y = pos[i]
        label = "".join(sorted(c))
        ax2.text(x, y, label, ha="center", va="center", fontsize=9, bbox=dict(boxstyle="round,pad=0.35", fc="#eaf1fb", ec=BLUE), zorder=3)
    ax2.set_xlim(-0.8, 2.0 * max(byd) + 0.8)
    ax2.set_ylim(-1.8, 1.8)
    ax2.axis("off")
    ax2.set_title("(b) junction tree (separators in red)", fontsize=9)
    savefig(fig, CH, "figS9-4", out)
    return [sorted(c) for c in mx], edges


def fig_S9_10(out=None):
    """Supplementary Figures 9.10(a) and 9.11(b): the marginal polytope of a two-node Ising model, and the local polytope
    against the marginal polytope for a triangle (node marginals fixed at 1/2)."""
    from mpl_toolkits.mplot3d.art3d import Poly3DCollection
    fig = plt.figure(figsize=(8.2, 3.8))
    ax = fig.add_subplot(1, 2, 1, projection="3d")
    V = np.array([[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 1]], float)
    faces = [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]
    ax.add_collection3d(Poly3DCollection([V[f] for f in faces], facecolor=BLUE, alpha=0.15, edgecolor="k", lw=0.8))
    ax.scatter(*V.T, color="k", s=18)
    for v, lab in zip(V, ["(0,0,0)", "(1,0,0)", "(0,1,0)", "(1,1,1)"]):
        ax.text(v[0] + 0.03, v[1] + 0.03, v[2] + 0.04, lab, fontsize=7)
    ax.set_xlabel("$\\mu_1$")
    ax.set_ylabel("$\\mu_2$")
    ax.set_zlabel("$\\mu_{12}$")
    ax.set_title("(a) $\\mathcal{M}(G)$ for $x_1 - x_2$", fontsize=9)
    ax.view_init(18, -35)
    ax2 = fig.add_subplot(1, 2, 2, projection="3d")
    cube = np.array([[a, b, c] for a in (0, 1) for b in (0, 1) for c in (0, 1)], float)
    cedges = [(i, j) for i in range(8) for j in range(i + 1, 8) if np.abs(cube[i] - cube[j]).sum() == 1]
    for i, j in cedges:
        ax2.plot(*zip(cube[i], cube[j]), color="#999999", lw=0.8)
    T = np.array([[1, 1, 1], [1, 0, 0], [0, 1, 0], [0, 0, 1]], float)
    ax2.add_collection3d(Poly3DCollection([T[f] for f in faces], facecolor=BLUE, alpha=0.15, edgecolor="k", lw=0.9))
    ax2.scatter([0.8], [0.8], [0.2], color=RED, s=44, depthshade=False)
    ax2.text(0.82, 0.82, 0.2, "pseudo-marginals", color=RED, fontsize=7)
    ax2.set_xlabel("$p(x_1=x_2)$")
    ax2.set_ylabel("$p(x_2=x_3)$")
    ax2.set_zlabel("$p(x_1=x_3)$")
    ax2.set_title("(b) slice: cube $\\mathcal{L}(G)$ vs tetrahedron $\\mathcal{M}(G)$", fontsize=9)
    ax2.view_init(18, -45)
    for a in (ax, ax2):
        a.set_xlim(0, 1)
        a.set_ylim(0, 1)
        a.set_zlim(0, 1)
        a.tick_params(labelsize=6.5)
    fig.tight_layout()
    savefig(fig, CH, "figS9-10", out)


def fig_S9_13(out=None):
    """Supplementary Figure 9.13: the graph-cut construction for the four-node MRF; the minimum cut has cost 6."""
    E0 = [7, 0, 0, 0]
    E1 = [0, 2, 1, 6]
    pe = [(0, 1), (1, 2), (2, 3), (0, 3)]
    lam = [6, 6, 2, 1]
    pairs = ising_energy_graphcut(E0, E1, pe, lam)
    n = 4
    cap = np.zeros((n + 2, n + 2))
    s, t = n, n + 1
    for u in range(n):
        if E1[u] == 0 and E0[u] > 0:
            cap[u, t] = E0[u]
        if E0[u] == 0 and E1[u] > 0:
            cap[s, u] = E1[u]
    for (u, v), l in zip(pe, lam):
        cap[u, v] = cap[v, u] = l
    flow, src = max_flow_edmonds_karp(cap, s, t)
    x, e = graphcut_map(E0, E1, pairs)
    pos = {0: (0.0, 2.0), 1: (2.0, 2.0), 2: (2.0, 0.0), 3: (0.0, 0.0), s: (1.0, -1.7), t: (1.0, 3.5)}
    fig, ax = plt.subplots(figsize=(4.6, 5.0))
    cut = []
    for u in range(n + 2):
        for v in range(n + 2):
            if cap[u, v] > 0 and u in src and v not in src:
                cut.append((u, v))
    drawn = set()
    for u in range(n + 2):
        for v in range(n + 2):
            if cap[u, v] > 0 and (v, u) not in drawn:
                both = cap[v, u] > 0
                drawn.add((u, v))
                iscut = (u, v) in cut or (v, u) in cut
                ax.plot([pos[u][0], pos[v][0]], [pos[u][1], pos[v][1]], color=RED if iscut else "#777777", lw=2.0 if iscut else 1.0, ls="--" if iscut else "-", zorder=1)
                fr = 0.5 if (u < n and v < n) else 0.38
                mx, my = pos[u][0] + fr * (pos[v][0] - pos[u][0]), pos[u][1] + fr * (pos[v][1] - pos[u][1])
                ax.text(mx, my + 0.08, "%g" % cap[u, v], fontsize=8, color=RED if iscut else "k", ha="center", bbox=dict(fc="white", ec="none", pad=0.3))
    names = {0: "$x_1$", 1: "$x_2$", 2: "$x_3$", 3: "$x_4$", s: "s", t: "t"}
    for v, (px, py) in pos.items():
        side = v in src
        ax.add_patch(plt.Circle((px, py), 0.28, fc="#dde9fb" if side else "#fde3d6", ec="k", lw=1.2, zorder=2))
        ax.text(px, py, names[v], ha="center", va="center", fontsize=10, zorder=3)
    ax.text(1.0, -2.5, "minimum cut = %g;   MAP = (%s)   (source side = state 0)" % (flow, ", ".join(str(int(v)) for v in x)), ha="center", fontsize=9)
    ax.set_xlim(-1.4, 3.4)
    ax.set_ylim(-2.9, 4.0)
    ax.set_aspect("equal")
    ax.axis("off")
    savefig(fig, CH, "figS9-13", out)
    return flow, x, e


def fig_9_S1(out=None):
    """Our supplementary figure: sum-product decoding of a (3, 6) LDPC code over the binary symmetric channel."""
    rng = np.random.default_rng(0)
    ps = [0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08, 0.09, 0.10]
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.0))
    res = {}
    for n, col, trials in ((504, BLUE, 200), (1008, GREEN, 120)):
        H = ldpc_gallager(n, 3, 6, seed=1)
        ber, fer = [], []
        for p in ps:
            y = (rng.random((trials, n)) < p).astype(int)
            llr = np.log((1 - p) / p) * (1 - 2 * y)
            dec = ldpc_bp_decode(H, llr, 60)
            ber.append(dec.mean())
            fer.append((dec.sum(1) > 0).mean())
        res[n] = (ber, fer)
        axes[0].semilogy(ps, np.maximum(ber, 0.5 / (trials * n)), "o-", color=col, ms=3.5, label="BP decoding, $n=%d$" % n)
        axes[1].plot(ps, fer, "o-", color=col, ms=3.5, label="$n=%d$" % n)
    axes[0].semilogy(ps, ps, "k--", lw=1, label="uncoded (BER $=p$)")
    for a in axes:
        a.axvline(0.11, color=RED, ls=":", lw=1.2)
        a.set_xlabel("channel flip probability $p$")
    axes[0].text(0.1085, 0.3, "capacity\n(rate 1/2)", color=RED, fontsize=7, va="top", ha="right")
    axes[0].set_ylabel("bit error rate")
    axes[1].set_ylabel("frame error rate")
    axes[0].legend(fontsize=7, frameon=False, loc="lower right", bbox_to_anchor=(1.0, 0.12))
    axes[0].set_ylim(2e-6, 0.5)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S1", out)
    return res


def gaussian_grid_precision(n=6, diag=4.0, off=-1.0, seed=0):
    N = n * n
    J = np.zeros((N, N))
    for i in range(n):
        for j in range(n):
            k = i * n + j
            J[k, k] = diag
            if j + 1 < n:
                J[k, k + 1] = J[k + 1, k] = off
            if i + 1 < n:
                J[k, k + n] = J[k + n, k] = off
    h = np.random.default_rng(seed).normal(size=N)
    return J, h


def fig_9_S2(out=None):
    """Our supplementary figure: Gaussian BP on a loopy grid: the means converge to the exact ones, the variances do not."""
    J, h = gaussian_grid_precision(6, 4.5, -1.0)
    mean, var, it, err = gaussian_bp(J, h, iters=200)
    exact_var = np.diag(np.linalg.inv(J))
    fig, axes = plt.subplots(1, 3, figsize=(8.4, 2.7))
    axes[0].semilogy(np.arange(1, len(err) + 1), np.maximum(err, 1e-16), color=BLUE)
    axes[0].set_xlabel("sweep")
    axes[0].set_ylabel("max error of the means")
    mu = np.linalg.solve(J, h)
    axes[1].plot(mu, mean, "o", ms=3.5, color=BLUE)
    lim = [mu.min() - 0.1, mu.max() + 0.1]
    axes[1].plot(lim, lim, "k-", lw=0.8)
    axes[1].set_xlabel("exact posterior mean")
    axes[1].set_ylabel("BP belief mean")
    axes[2].plot(exact_var, var, "o", ms=3.5, color=RED)
    lim = [exact_var.min() * 0.95, exact_var.max() * 1.02]
    axes[2].plot(lim, lim, "k-", lw=0.8)
    axes[2].set_xlabel("exact posterior variance")
    axes[2].set_ylabel("BP belief variance")
    for a, l in zip(axes, "abc"):
        common.panel_label(a, l, "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig9-S2", out)
    return it, err[-1], (exact_var - var).min(), (exact_var - var).max()


def binary_scene(n=48):
    yy, xx = np.mgrid[:n, :n]
    img = np.zeros((n, n), int)
    img[(xx - 16) ** 2 + (yy - 16) ** 2 < 11 ** 2] = 1
    img[28:42, 22:44] = 1
    img[(xx - 36) ** 2 + (yy - 12) ** 2 < 5 ** 2] = 1
    return img


def denoise_problem(flip=0.15, lam=1.0, seed=0, n=48):
    """Binary image denoising as a Potts/Ising MAP problem: E(x) = sum_u [x_u != y_u] + lam sum_{u~v} [x_u != x_v]."""
    clean = binary_scene(n)
    rng = np.random.default_rng(seed)
    y = np.where(rng.random(clean.shape) < flip, 1 - clean, clean)
    idx = np.arange(n * n).reshape(n, n)
    pe = [(idx[i, j], idx[i, j + 1]) for i in range(n) for j in range(n - 1)] + [(idx[i, j], idx[i + 1, j]) for i in range(n - 1) for j in range(n)]
    return clean, y, pe, lam


def graphcut_scipy(E0, E1, pe, lam, scale=1000):
    """The same minimum cut as graphcut_map for the symmetric Ising energies, with SciPy's maximum-flow routine (Dinic) so that
    it scales to images; capacities are rounded to integers (scale)."""
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import maximum_flow
    n = len(E0)
    s, t = n, n + 1
    rows, cols, vals = [], [], []
    for (u, v) in pe:
        for a, b in ((u, v), (v, u)):
            rows.append(a)
            cols.append(b)
            vals.append(int(round(lam * scale)))
    for u in range(n):
        d = E1[u] - E0[u]
        if d > 0:
            rows.append(s); cols.append(u); vals.append(int(round(d * scale)))  # noqa: E702
        elif d < 0:
            rows.append(u); cols.append(t); vals.append(int(round(-d * scale)))  # noqa: E702
    G = csr_matrix((vals, (rows, cols)), shape=(n + 2, n + 2), dtype=np.int32)
    r = maximum_flow(G, s, t)
    # nodes reachable from s in the residual graph (capacity - flow > 0)
    resid = np.maximum(G.toarray() - r.flow.toarray(), 0)
    seen = np.zeros(n + 2, bool)
    seen[s] = True
    stack = [s]
    while stack:
        u = stack.pop()
        for v in np.flatnonzero((resid[u] > 0) & ~seen):
            seen[v] = True
            stack.append(v)
    return np.where(seen[:n], 0, 1)


def icm_denoise(y, lam, sweeps=20):
    x = y.copy()
    n = x.shape[0]
    for _ in range(sweeps):
        changed = 0
        for i in range(n):
            for j in range(n):
                nb = [x[a, b] for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)) if 0 <= a < n and 0 <= b < n]
                e = [(v != y[i, j]) + lam * sum(1 for q in nb if q != v) for v in (0, 1)]
                new = int(np.argmin(e))
                changed += new != x[i, j]
                x[i, j] = new
        if not changed:
            break
    return x


def denoise_energy(x, y, pe, lam):
    xf = x.ravel()
    yf = y.ravel()
    return float((xf != yf).sum() + lam * sum(xf[u] != xf[v] for u, v in pe))


def fig_9_S3(out=None):
    """Our supplementary figure: exact MAP denoising of a binary image by graph cuts, against iterated conditional modes."""
    clean, y, pe, lam = denoise_problem()
    n = clean.shape[0]
    E0 = (y.ravel() != 0).astype(float)
    E1 = (y.ravel() != 1).astype(float)
    xg = graphcut_scipy(E0, E1, pe, lam).reshape(n, n)
    xi = icm_denoise(y, lam)
    eg, ei, e0 = denoise_energy(xg, y, pe, lam), denoise_energy(xi, y, pe, lam), denoise_energy(y, y, pe, lam)
    fig, axes = common.panel_grid(1, 4, size=(2.2, 2.5))
    for ax, im, tt in zip(axes[0], (clean, y, xi, xg), ("true image", "noisy (15% flipped)", "ICM: energy %.0f" % ei, "graph cut: energy %.0f" % eg)):
        ax.imshow(im, cmap="gray_r", interpolation="nearest")
        ax.set_title(tt, fontsize=8.5)
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig9-S3", out)
    return eg, ei, e0, int((xg != clean).sum()), int((xi != clean).sum()), int((y != clean).sum())


def fig_9_S4(out=None):
    """Our supplementary figure: perturb-and-MAP. (a) Gaussian: sample covariance against K^-1. (b) Discrete: distance of the
    perturb-and-MAP distribution from the Gibbs distribution of a six-node Ising ring, with Gumbel noise on every
    configuration (exact), and on the unary terms only (approximate)."""
    rng = np.random.default_rng(0)
    N = 5
    G = np.eye(N) + np.diag(-0.6 * np.ones(N - 1), 1)
    Sp = 0.5 * np.eye(N)
    H = np.random.default_rng(1).normal(size=(3, N))
    Sn = 0.2 * np.eye(3)
    mu_p = np.zeros(N)
    y = np.array([1.0, -0.5, 0.3])
    mu, Sigma, xs = pam_gaussian(G, Sp, mu_p, H, Sn, y, np.zeros(3), 40000, rng)
    emp = np.cov(xs.T)
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 2.9))
    axes[0].plot(Sigma.ravel(), emp.ravel(), "o", ms=4, color=BLUE)
    lim = [Sigma.min() - 0.02, Sigma.max() + 0.02]
    axes[0].plot(lim, lim, "k-", lw=0.8)
    axes[0].set_xlabel("exact posterior covariance entry")
    axes[0].set_ylabel("covariance of the draws")
    common.panel_label(axes[0], "a", "upper left")
    n, K = 6, 2
    th = np.random.default_rng(2).normal(size=n) * 0.5
    J = 0.8
    states = np.array(list(itertools.product(range(K), repeat=n)))
    spin = 2 * states - 1
    logp = spin @ th + J * sum(spin[:, i] * spin[:, (i + 1) % n] for i in range(n))
    p = np.exp(logp - logp.max())
    p /= p.sum()
    def pairwise(st):
        sp = 2 * st - 1
        return J * sum(sp[:, i] * sp[:, (i + 1) % n] for i in range(n))
    node_lp = [np.array([-th[i], th[i]]) for i in range(n)]
    approx = pam_unary_gumbel(node_lp, pairwise, 20000, rng)
    exact_pam = gumbel_max_samples(logp, 20000, rng)
    tv_a, tv_e = 0.5 * np.abs(approx - p).sum(), 0.5 * np.abs(exact_pam - p).sum()
    axes[1].bar([0, 1], [tv_e, tv_a], color=[BLUE, ORANGE], width=0.55)
    axes[1].set_xticks([0, 1])
    axes[1].set_xticklabels(["Gumbel on all\n64 configurations", "Gumbel on the\nunary terms only"], fontsize=8)
    axes[1].set_ylabel("total variation distance")
    common.panel_label(axes[1], "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig9-S4", out)
    return tv_e, tv_a


def fig_9_S5(out=None):
    """Our supplementary figure: the cost (9.92) of variable elimination over all 8! orders of the student network."""
    parents, _, _ = student8()
    adj = moral_graph(parents)
    nodes = sorted(adj)
    costs, widths = [], []
    for o in itertools.permutations(nodes):
        _, _, mx = induced_graph(adj, list(o))
        costs.append(sum(2 ** len(c) for c in mx))
        widths.append(max(len(c) for c in mx) - 1)
    costs, widths = np.array(costs), np.array(widths)
    o1 = ["C", "D", "I", "H", "G", "S", "L", "J"]
    o2 = ["G", "I", "S", "L", "H", "C", "D", "J"]
    mf = min_fill_order(adj)
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 2.8))
    ws = np.arange(widths.min(), widths.max() + 1)
    axes[0].bar(ws, [(widths == w).sum() for w in ws], color=BLUE, width=0.7)
    axes[0].set_xlabel("induced width of the order")
    axes[0].set_ylabel("number of the 40320 orders")
    axes[0].set_xticks(ws)
    axes[1].hist(np.log2(costs), bins=np.arange(np.log2(costs.min()) - 0.1, np.log2(costs.max()) + 0.4, 0.25), color=BLUE)
    for o, col, lab in ((o1, GREEN, "Table 9.1"), (o2, RED, "Table 9.2"), (mf, ORANGE, "min-fill")):
        axes[1].axvline(np.log2(ve_cost(adj, o)), color=col, lw=1.6, label="%s (%d)" % (lab, ve_cost(adj, o)))
    axes[1].set_xlabel("$\\log_2$ of the cost $\\sum_c 2^{|c|}$")
    axes[1].legend(fontsize=7, frameon=False)
    for a, l in zip(axes, "ab"):
        common.panel_label(a, l, "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig9-S5", out)
    return costs, widths


# =========================================================================== data for the browser demonstrations
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    pi, A, B, z, y = casino_data()
    lik = B[:, y].T
    r = forwards_backwards(pi, A, lik)
    path, _, _ = viterbi(pi, A, lik)
    d = dict(T=CASINO_T, seed=CASINO_SEED, pi=pi.tolist(), A=A.tolist(), B=B.tolist(), z=z.tolist(), y=y.tolist(),
             loaded_filtered=[round(float(v), 12) for v in r["alpha"][:, 1]], loaded_smoothed=[round(float(v), 12) for v in r["gamma"][:, 1]],
             viterbi=path.tolist(), loglik=round(float(r["loglik"]), 6))
    with open(os.path.join(DATA_OUT, "ch09-casino.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote ch09-casino.json")
    uh, uv, h = grid_potentials()
    d = dict(n=GRID_N, scale=GRID_SCALE, seed=GRID_SEED, uh=uh.tolist(), uv=uv.tolist(), h=h.tolist())
    with open(os.path.join(DATA_OUT, "ch09-grid.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote ch09-grid.json")
    parents, cpt, facs = student8()
    adj = moral_graph(parents)
    full, _ = variable_elimination(facs, ["C", "D", "I", "H", "G", "S", "L"])
    d = dict(parents=parents, cpt={k: np.asarray(v).tolist() for k, v in cpt.items()}, pJ1=round(float(full.table[1] / full.table.sum()), 8),
             treewidth=treewidth_exact(adj))
    with open(os.path.join(DATA_OUT, "ch09-student8.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote ch09-student8.json")


FIGURES = {"9.3": fig_9_3, "9.6": fig_9_6, "9.11": fig_9_11, "9.13": fig_9_13, "9.17": fig_9_17, "9.18": fig_9_18,
           "S9.4": fig_S9_4, "S9.10": fig_S9_10, "S9.13": fig_S9_13,
           "9.S1": fig_9_S1, "9.S2": fig_9_S2, "9.S3": fig_9_S3, "9.S4": fig_9_S4, "9.S5": fig_9_S5}


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
