familytree

commit 2358b8078b8d5c9da860df5ec6d18f27345b5815
parent 9272e3917019c24464776878c720a8107cd687fc
Author: Julian Piribauer <julian.piribauer@gmail.com>
Date:   Sat,  9 May 2026 18:49:11 +0000

Prevent cyclic parent links from breaking the tree layout

- Frontend: buildAcyclicParentLinks() does incremental BFS cycle
  detection before layout, skipping any link that would make a child
  an ancestor of its own parent
- Backend: add_parent_link rejects cycles with HTTP 422 before insert
- Deleted bad DB link (id=15) that caused Ingeborg's generation to
  reach ~40 and y-positions to exceed 10 000 px

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>

Diffstat:
M
app/main.py
 | 
35
+++++++++++++++++++++++++++++++++++
M
static/app.js
 | 
43
++++++++++++++++++++++++++++++++++++++++++-

2 files changed, 77 insertions(+), 1 deletion(-)
diff --git a/app/main.py b/app/main.py
@@ -419,6 +419,41 @@ def add_parent_link(tree_id: int, body: ParentLinkCreate, request: Request, db: 
     if body.parent_id:
         if not db.query(Person).filter(Person.id == body.parent_id, Person.tree_id == tree_id).first():
             raise HTTPException(status_code=404, detail="Parent not in tree")
+
+    # Cycle detection: reject if child is an ancestor of any proposed parent
+    parent_ids: list[int] = []
+    if body.partnership_id:
+        ps = db.query(Partnership).filter(Partnership.id == body.partnership_id).first()
+        if ps:
+            parent_ids = [ps.person1_id, ps.person2_id]
+    elif body.parent_id:
+        parent_ids = [body.parent_id]
+
+    if parent_ids:
+        all_links = db.query(ParentLink).join(Person, ParentLink.child_id == Person.id).filter(Person.tree_id == tree_id).all()
+        all_partnerships = db.query(Partnership).filter(Partnership.tree_id == tree_id).all()
+        ps_map = {p.id: (p.person1_id, p.person2_id) for p in all_partnerships}
+        children_of: dict[int, list[int]] = {}
+        for link in all_links:
+            if link.partnership_id and link.partnership_id in ps_map:
+                for pid in ps_map[link.partnership_id]:
+                    children_of.setdefault(pid, []).append(link.child_id)
+            elif link.parent_id:
+                children_of.setdefault(link.parent_id, []).append(link.child_id)
+        def can_reach(start: int, targets: set[int]) -> bool:
+            queue, seen = [start], {start}
+            while queue:
+                cur = queue.pop()
+                for child in children_of.get(cur, []):
+                    if child in targets:
+                        return True
+                    if child not in seen:
+                        seen.add(child)
+                        queue.append(child)
+            return False
+        if can_reach(body.child_id, set(parent_ids)):
+            raise HTTPException(status_code=422, detail="Adding this link would create a cycle in the family tree")
+
     pl = ParentLink(**body.model_dump())
     db.add(pl)
     db.commit()
diff --git a/static/app.js b/static/app.js
@@ -181,7 +181,48 @@ function fitCanvas() {
   svg.call(zoom.transform, d3.zoomIdentity.translate(tx, ty).scale(scale));
 }
 
-function computeLayout({ people, partnerships, parentLinks }, opts = {}) {
+function buildAcyclicParentLinks(people, partnerships, parentLinks) {
+  function getParents(pl) {
+    if (pl.partnership_id) {
+      const ps = partnerships.find(p => p.id === pl.partnership_id);
+      return ps ? [ps.person1_id, ps.person2_id] : [];
+    }
+    return pl.parent_id != null ? [pl.parent_id] : [];
+  }
+
+  const adj = new Map(people.map(p => [p.id, new Set()]));
+
+  function canReachAny(from, targets) {
+    const q = [from], seen = new Set([from]);
+    while (q.length) {
+      const cur = q.shift();
+      for (const next of (adj.get(cur) || [])) {
+        if (targets.has(next)) return true;
+        if (!seen.has(next)) { seen.add(next); q.push(next); }
+      }
+    }
+    return false;
+  }
+
+  const sorted = [...parentLinks].sort((a, b) => a.id - b.id);
+  const safe = [];
+
+  for (const pl of sorted) {
+    const parents = getParents(pl);
+    if (parents.length && canReachAny(pl.child_id, new Set(parents))) {
+      console.warn(`Layout: skipping cyclic parent link id=${pl.id} (child=${pl.child_id} would create cycle)`);
+    } else {
+      safe.push(pl);
+      for (const pid of parents) {
+        if (adj.has(pid)) adj.get(pid).add(pl.child_id);
+      }
+    }
+  }
+  return safe;
+}
+
+function computeLayout({ people, partnerships, parentLinks: rawLinks }, opts = {}) {
+  const parentLinks = buildAcyclicParentLinks(people, partnerships, rawLinks);
   const pos = {};
   const _NW = opts.nodeW ?? NODE_W;
   const _CG = opts.coupleGap ?? COUPLE_GAP;