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

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]
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