关于「世系是有向无环图:拓扑排序与查环」,《族谱合龙与义庄永续》给出的定量结论是什么?

结论:第三章把世系写成有向无环图,用卡恩拓扑排序与塔扬强连通分量查错;单处误挂父亲,同代同名、结构看不见者占 0.136。

数据口径:按字辈起名,同代人只剩一字可变,示意参数下一代 11 人就有一半机会撞名;两本 60 人对 40 人之支谱按全名硬接,接对者只占 0.208。 书中数据全为合成或示意,不含任何真实在世者资料;全部计算由书中程序生成;本书是非个人化分析,不构成法律、理财或经营建议,也不做任何血统高下或族群比较。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.136

Book885 men in 12 generations
Single re-attachment errors to a namesake father10,406
creates a cycle (SCC)166 share 0.016
wrong depth only8,827 share 0.848
same generation, blind1,413 share 0.136
Errors among identical full names1,413, all blind
Planted 5 cycle errors; Tarjan finds 5 loops of sizes [3, 3, 4, 4, 4]
查看完整验算程序
# Chapter 3. p32: which copying errors a structural check can see.
# Model: a synthetic book (cap 1,500 men, 12 generations); names
# are generation character (one per generation, poem longer than 12)
# plus a Zipf free character (K = 400, s = 0.8, as in p11). A copying
# error re-attaches a man to a wrong father who shares the true
# father's free character. All single errors are enumerated. If the
# wrong father is a descendant of the man, the graph gets a cycle that
# Tarjan's (1972) strongly connected components expose; if he sits in
# another generation, the depth check of p31 flags it; if he sits in
# the same generation (an identical full name), no structural check
# can see the error. Synthetic data only.
import math
import random
from collections import defaultdict

K, S = 400, 0.8


def zipf_cum(k, s):
    raw = [1.0 / (i ** s) for i in range(1, k + 1)]
    tot = math.fsum(raw)
    return [math.fsum(raw[:i + 1]) / tot for i in range(k)]


def build(rng, cum):
    gen, name, father = {0: 0}, {0: 0}, {}
    layer, nid = [0], 1
    while layer and gen[layer[0]] < 11:
        nxt = []
        for f in layer:
            n_sons = rng.choice((0, 1, 1, 2, 2, 2, 3)) if f else 3
            if nid >= 1500:
                n_sons = 0
            for _ in range(n_sons):
                u = rng.random()
                name[nid] = next(i for i, c in enumerate(cum) if c >= u)
                gen[nid], father[nid] = gen[f] + 1, f
                nxt.append(nid)
                nid += 1
        layer = nxt
    return gen, name, father


def tarjan(nodes, kids):
    index, low, on, stack, comps = {}, {}, set(), [], []
    counter = [0]

    def visit(v):
        index[v] = low[v] = counter[0]
        counter[0] += 1
        stack.append(v)
        on.add(v)
        for w in kids[v]:
            if w not in index:
                visit(w)
                low[v] = min(low[v], low[w])
            elif w in on:
                low[v] = min(low[v], index[w])
        if low[v] == index[v]:
            comp = []
            while True:
                w = stack.pop()
                on.discard(w)
                comp.append(w)
                if w == v:
                    break
            comps.append(comp)

    for v in nodes:
        if v not in index:
            visit(v)
    return comps


if __name__ == "__main__":
    rng = random.Random(3343)
    gen, name, father = build(rng, zipf_cum(K, S))
    nodes = sorted(gen)
    anc = {0: set()}
    for v in nodes[1:]:
        anc[v] = anc[father[v]] | {father[v]}
    by_name = defaultdict(list)
    for v in nodes:
        by_name[name[v]].append(v)
    cyc, depth, blind, same_full = 0, 0, 0, 0
    for v in nodes[1:]:
        f = father[v]
        for w in by_name[name[f]]:
            if w in (f, v):
                continue
            if v in anc[w]:
                cyc += 1
            elif gen[w] != gen[f]:
                depth += 1
            else:
                blind += 1
                same_full += 1
    tot = cyc + depth + blind
    print("Book: {} men in {} generations".format(
        len(nodes), max(gen.values()) + 1))
    print("Single re-attachment errors to a namesake father: {:,}".format(
        tot))
    print("  creates a cycle (SCC)     {:>6,}  share {:.3f}".format(
        cyc, cyc / tot))
    print("  wrong depth only          {:>6,}  share {:.3f}".format(
        depth, depth / tot))
    print("  same generation, blind    {:>6,}  share {:.3f}".format(
        blind, blind / tot))
    print("Errors among identical full names: {:,}, all blind".format(
        same_full))
    kids = defaultdict(list)
    for v in nodes[1:]:
        kids[father[v]].append(v)
    planted = 0
    for v in nodes[200:]:
        hits = [w for w in by_name[name[father[v]]] if v in anc[w]]
        if hits and planted < 5:
            kids[father[v]].remove(v)
            kids[hits[0]].append(v)
            planted += 1
    loops = [c for c in tarjan(nodes, kids) if len(c) > 1]
    print("Planted 5 cycle errors; Tarjan finds {} loops of sizes {}"
          .format(len(loops), sorted(len(c) for c in loops)))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《宗族世系有向无环图合龙算法、字辈同余编码与范氏义庄跨代治理母典》第 3 章「世系是有向无环图:拓扑排序与查环」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-334 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026334,
  author    = {Fan, Yafu},
  title     = {Genealogical DAG Merge Algorithms, Generation-Poem Congruence Coding and the Institutional Economics of the Fan Clan Charitable Estate},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论