8.1 分支拓扑：分叉、汇聚、并行

#!/usr/bin/env python3
# file: sim/na_08_1_topology.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/na_08_1_topology.py
"""卷一 8.1 分支拓扑（S 层）：把 48 个对话节点读成有向图，量三种拓扑原语。

  分叉 fork    出度 >= 2 且目标不唯一（一出多，真的分出不同去向）
  扇出 fanout  出度 >= 2 但全部指向同一目标（多个选项共用一个去向）
  汇聚 merge   入度 >= 2（多入一，由不同前驱汇到一起）
  强制汇流     入度 >= 2 且是支配点：从起点到任一结局的路径都必经它
  并行         同一分叉点分出的两条去向互不可达（两条线彼此不干扰）

产出 out/narr08_topology.csv（48 行）与控制台摘要；节点/边计数不符即非零退出。
"""
from __future__ import annotations

import csv
import json
import os
import sys

HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
SPEC = os.path.join(ROOT, "config/story_spec.json")


def reachable(succ: dict, start: str) -> set:
    seen, stack = set(), [start]
    while stack:
        x = stack.pop()
        if x not in seen:
            seen.add(x)
            stack.extend(succ[x])
    return seen


def dominators(succ: dict, preds: dict, start: str) -> dict:
    """n 被 m 支配 <=> 从起点到 n 的每条路径都经过 m。DAG 上迭代求不动点。"""
    r = reachable(succ, start)
    dom = {n: set(r) for n in r}
    dom[start] = {start}
    changed = True
    while changed:
        changed = False
        for n in sorted(r):
            ps = [p for p in preds[n] if p in r]
            if n == start or not ps:
                continue
            new = set.intersection(*(dom[p] for p in ps)) | {n}
            if new != dom[n]:
                dom[n] = new
                changed = True
    return dom


def nearest_join(succ: dict, a: str, b: str):
    """a、b 分出的两条线「最近重逢」的节点与跳数：BFS 序遇到的第一个共同后继。"""
    both = reachable(succ, a) & reachable(succ, b)
    seen, queue = {a}, [(a, 0)]
    while queue:
        x, d = queue.pop(0)
        if x in both:
            return x, d
        for y in succ[x]:
            if y not in seen:
                seen.add(y)
                queue.append((y, d + 1))
    return None, None


def main() -> int:
    spec = json.load(open(SPEC, encoding="utf-8"))
    nodes = spec["dialogue"]
    by = {n["id"]: n for n in nodes}
    start = spec["meta"]["start"]
    scale = spec["meta"]["scale"]

    succ = {n["id"]: [] for n in nodes}
    preds = {n["id"]: set() for n in nodes}
    edges = []
    for n in nodes:
        for c in (n.get("choices") or []):
            succ[n["id"]].append(c["goto"])
            preds[c["goto"]].add(n["id"])
            edges.append((n["id"], c["id"], c["goto"]))
    preds = {k: sorted(v) for k, v in preds.items()}

    out_deg = {n["id"]: len(n.get("choices") or []) for n in nodes}
    dst = {n["id"]: len({c["goto"] for c in (n.get("choices") or [])}) for n in nodes}
    in_deg = {n["id"]: len(preds[n["id"]]) for n in nodes}
    leaves = sorted(n["id"] for n in nodes if out_deg[n["id"]] == 0)
    end_dom = set.intersection(*(dominators(succ, preds, start)[e] for e in leaves))

    forks = sorted(n for n in out_deg if dst[n] >= 2)
    fanouts = sorted(n for n in out_deg if out_deg[n] >= 2 and dst[n] == 1)
    merges = sorted(n for n in in_deg if in_deg[n] >= 2)
    forced = sorted(n for n in merges if n in end_dom)

    parallel = []
    for f in forks:
        tg = sorted({c["goto"] for c in by[f]["choices"]})
        for i in range(len(tg)):
            for j in range(i + 1, len(tg)):
                a, b = tg[i], tg[j]
                if b not in reachable(succ, a) and a not in reachable(succ, b):
                    parallel.append((f, a, b))
    mid = [p for p in parallel if p[1] not in leaves and p[2] not in leaves]

    bad = []
    if len(nodes) != scale["dialogue_nodes"]:
        bad.append(f"节点数 {len(nodes)} != scale {scale['dialogue_nodes']}")
    if len(edges) != scale["choices"]:
        bad.append(f"边数 {len(edges)} != scale {scale['choices']}")

    print(f"nodes={len(nodes)}  edges={len(edges)}  start={start}")
    print(f"分叉 fork（出度>=2 且目标不唯一）    {len(forks)}  {forks}")
    print(f"扇出 fanout（出度>=2 但目标唯一）    {len(fanouts)}")
    print(f"汇聚 merge（入度>=2）                {len(merges)}  {merges}")
    print(f"强制汇流（入度>=2 且所有路径必经）   {len(forced)}  {forced}")
    print(f"结局节点 leaf（出度=0）              {len(leaves)}  {leaves}")
    print(f"并行去向对 {len(parallel)}（终局对 {len(parallel) - len(mid)}、中途并行 {len(mid)}）")
    for f, a, b in mid:
        j, d = nearest_join(succ, a, b)
        print(f"    {f} -> {a} ∥ {b}  最近重逢 {j}（{d} 跳）")

    rows = [{"id": n["id"], "scene": n["scene"], "speaker": n.get("speaker", "-"),
             "in_deg": in_deg[n["id"]], "out_deg": out_deg[n["id"]], "distinct": dst[n["id"]],
             "role": ("ending" if n.get("ending") else "forced-merge" if n["id"] in forced
                      else "fork" if n["id"] in forks else "merge" if n["id"] in merges
                      else "fanout" if n["id"] in fanouts else "chain")} for n in nodes]
    os.makedirs(OUT, exist_ok=True)
    with open(os.path.join(OUT, "narr08_topology.csv"), "w", encoding="utf-8", newline="") as fh:
        w = csv.DictWriter(fh, fieldnames=list(rows[0]))
        w.writeheader()
        w.writerows(rows)
    print(f"wrote out/narr08_topology.csv rows={len(rows)}")

    for e in bad:
        print(f"FAIL {e}")
    if bad:
        print(f"== na_08_1_topology：FAIL {len(bad)}")
        return 1
    print("OK na_08_1_topology：拓扑原语清点一致")
    return 0


if __name__ == "__main__":
    sys.exit(main())

nodes=48  edges=115  start=d_pier_1
分叉 fork（出度>=2 且目标不唯一）    9  ['d_bw_3', 'd_dq_2', 'd_hub_a1', 'd_hub_a2', 'd_hub_b2', 'd_lb_3', 'd_lt_3', 'd_mr_3', 'd_pier_2']
扇出 fanout（出度>=2 但目标唯一）    34
汇聚 merge（入度>=2）                8  ['d_bw_1', 'd_dq_1', 'd_fg_1', 'd_ho_1', 'd_hub_a1', 'd_hub_a2', 'd_hub_b2', 'd_mr_1']
强制汇流（入度>=2 且所有路径必经）   4  ['d_dq_1', 'd_hub_a1', 'd_hub_a2', 'd_hub_b2']
结局节点 leaf（出度=0）              5  ['e_dark', 'e_lit', 'e_loss', 'e_silence', 'e_truth']
并行去向对 14（终局对 10、中途并行 4）
    d_hub_a1 -> d_ch_1 ∥ d_wp_1  最近重逢 d_hub_a2（3 跳）
    d_lb_3 -> d_mr_1 ∥ d_tc_1  最近重逢 d_ho_1（3 跳）
    d_mr_3 -> d_db_1 ∥ d_ho_1  最近重逢 d_hub_b2（3 跳）
    d_pier_2 -> d_chapel_1 ∥ d_tavern_1  最近重逢 d_hub_a1（3 跳）
wrote out/narr08_topology.csv rows=48
OK na_08_1_topology：拓扑原语清点一致