depth.py
python
sha256:1ccb8409daa5aabe577bd26d11b56ed12f3376d64011d0e75a247e81211a66ee
docs(mwp4/phase5): tick Phase 5 checkboxes, close musehub#109
Sonnet 4.6
20 days ago
| 1 | """I2 — Root distance invariant. |
| 2 | |
| 3 | Multi-source BFS from all human nodes simultaneously. |
| 4 | Distance to a human node is always 0. |
| 5 | None means no path to any human exists (orphan agent or disconnected org). |
| 6 | """ |
| 7 | |
| 8 | from collections import deque |
| 9 | |
| 10 | from .dag import IdentityDAG, NodeType |
| 11 | |
| 12 | class RootDistanceIndex: |
| 13 | def __init__( |
| 14 | self, |
| 15 | distances: dict[str, int | None], |
| 16 | ancestors: dict[str, set[str]], |
| 17 | ) -> None: |
| 18 | self._distances = distances |
| 19 | self._ancestors = ancestors |
| 20 | |
| 21 | @classmethod |
| 22 | def build(cls, dag: IdentityDAG) -> "RootDistanceIndex": |
| 23 | handles = dag.all_handles() |
| 24 | |
| 25 | distances: dict[str, int | None] = {h: None for h in handles} |
| 26 | ancestors: dict[str, set[str]] = {h: set() for h in handles} |
| 27 | |
| 28 | # Humans are roots — distance 0, ancestor = self |
| 29 | queue: deque[str] = deque() |
| 30 | for handle, ntype in dag.nodes.items(): |
| 31 | if ntype == NodeType.HUMAN: |
| 32 | distances[handle] = 0 |
| 33 | ancestors[handle] = {handle} |
| 34 | queue.append(handle) |
| 35 | |
| 36 | # BFS outward along forward edges (from → to) |
| 37 | while queue: |
| 38 | node = queue.popleft() |
| 39 | node_dist = distances[node] |
| 40 | assert node_dist is not None |
| 41 | |
| 42 | for neighbour in dag.successors(node): |
| 43 | new_dist = node_dist + 1 |
| 44 | cur = distances.get(neighbour) |
| 45 | if cur is None or new_dist < cur: |
| 46 | distances[neighbour] = new_dist |
| 47 | ancestors[neighbour] = set(ancestors[node]) |
| 48 | queue.append(neighbour) |
| 49 | elif new_dist == cur: |
| 50 | ancestors[neighbour] |= ancestors[node] |
| 51 | |
| 52 | return cls(distances, ancestors) |
| 53 | |
| 54 | def distance(self, handle: str) -> int | None: |
| 55 | if handle not in self._distances: |
| 56 | raise KeyError(handle) |
| 57 | return self._distances[handle] |
| 58 | |
| 59 | def human_ancestors(self, handle: str) -> set[str]: |
| 60 | if handle not in self._ancestors: |
| 61 | raise KeyError(handle) |
| 62 | return set(self._ancestors[handle]) |
File History
2 commits
sha256:1ccb8409daa5aabe577bd26d11b56ed12f3376d64011d0e75a247e81211a66ee
docs(mwp4/phase5): tick Phase 5 checkboxes, close musehub#109
Sonnet 4.6
20 days ago
sha256:2c523da45351334b5c4dbefed4dc3dd553b3faa8737a4e6caf301e5dc82141be
test(mwp4): Phase 0 RED reproduction tests for RC-4 ordering race
Sonnet 4.6
20 days ago