关于「世系是有向无环图:拓扑排序与查环」,《族谱合龙与义庄永续》给出的定量结论是什么?
结论:第三章把世系写成有向无环图,用卡恩拓扑排序与塔扬强连通分量查错;单处误挂父亲,同代同名、结构看不见者占 0.136。
数据口径:按字辈起名,同代人只剩一字可变,示意参数下一代 11 人就有一半机会撞名;两本 60 人对 40 人之支谱按全名硬接,接对者只占 0.208。 书中数据全为合成或示意,不含任何真实在世者资料;全部计算由书中程序生成;本书是非个人化分析,不构成法律、理财或经营建议,也不做任何血统高下或族群比较。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.136
| Book | 885 men in 12 generations |
| Single re-attachment errors to a namesake father | 10,406 |
| creates a cycle (SCC) | 166 share 0.016 |
| wrong depth only | 8,827 share 0.848 |
| same generation, blind | 1,413 share 0.136 |
| Errors among identical full names | 1,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}
}