What does Joining Genealogies and the Perpetual Clan Estate conclude, in numbers, about “A Lineage Is a Directed Acyclic Graph: Topological Sorting and Cycle Detection”?
Answer: Chapter 3 checks descent as a directed acyclic graph with Kahn's sort and Tarjan's components; among single misattachments, same-generation namesakes invisible to the structure make up 0.136.
Scope of the numbers: All data are synthetic or illustrative, all calculations come from its programs, and it is general analysis, not legal, financial or business advice; it compares no lineages or ethnic groups. Marked boxes separate published evidence, runnable Python calculations (20 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 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] |
Show the full program
# 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)))Single source and citation
Fan, Y. (2026). Genealogical DAG Merge Algorithms, Generation-Poem Congruence Coding and the Institutional Economics of the Fan Clan Charitable Estate (Version 1.0.0), Chapter 3: A Lineage Is a Directed Acyclic Graph: Topological Sorting and Cycle Detection. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 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}
}Other chapter answers in this book
- Chapter 1 · Same Name, Same Generation: Collisions Are Far Commoner Than They Look
- Chapter 2 · Keeping a Ledger of Likelihood Ratios: Two Thresholds and a Review Zone
- Chapter 4 · The Generation Poem Is a Congruence Code: Dropped Generations, Extra Generations and Collisions Across Cycles
- Chapter 5 · Going to the Southern Seas Was Chain Migration: Branching Processes and the Crowding of Ports
- Chapter 6 · The Perpetual Charitable Estate: Extinction Probabilities, a Ration Ledger and the Risk of Governance
- Chapter 7 · The Classics Examined: Fan Zhongyan's Rules for the Charitable Estate and the Extinction Problem of Galton and Watson
- Chapter 8 · The Quarterly Merge Check-up: Procedure, Distilled Tool and Pre-registered Refutation