cycle.py
python
sha256:da49a05fd62cda46a7d73ec53a8d0adc5835d2070f6f0c51b12233a673c2e109
docs(mwp-1): mark Phase 5 complete, all acceptance criteria…
Sonnet 4.6
27 days ago
| 1 | """I1 — Acyclicity invariant. |
| 2 | |
| 3 | CycleDetector runs a DFS from the proposed `to` node over the existing graph. |
| 4 | If the DFS reaches `from`, the proposed edge would create a cycle → CycleError. |
| 5 | Self-loops are rejected immediately. |
| 6 | """ |
| 7 | |
| 8 | from .dag import EdgeType, IdentityDAG |
| 9 | |
| 10 | class CycleError(Exception): |
| 11 | """Raised when a proposed edge would introduce a cycle.""" |
| 12 | |
| 13 | class CycleDetector: |
| 14 | def __init__(self, dag: IdentityDAG) -> None: |
| 15 | self._dag = dag |
| 16 | |
| 17 | def assert_no_cycle( |
| 18 | self, |
| 19 | from_handle: str, |
| 20 | to_handle: str, |
| 21 | edge_type: EdgeType, |
| 22 | ) -> None: |
| 23 | """Raise CycleError if adding from_handle → to_handle would create a cycle.""" |
| 24 | if from_handle == to_handle: |
| 25 | raise CycleError( |
| 26 | f"Self-loop rejected: {from_handle!r} → {to_handle!r}" |
| 27 | ) |
| 28 | |
| 29 | # DFS from to_handle — if we can reach from_handle, the new edge closes a cycle. |
| 30 | visited: set[str] = set() |
| 31 | stack = [to_handle] |
| 32 | while stack: |
| 33 | node = stack.pop() |
| 34 | if node == from_handle: |
| 35 | raise CycleError( |
| 36 | f"Cycle detected: adding {from_handle!r} → {to_handle!r} " |
| 37 | f"would close a cycle" |
| 38 | ) |
| 39 | if node in visited: |
| 40 | continue |
| 41 | visited.add(node) |
| 42 | stack.extend(self._dag.successors(node)) |
File History
1 commit
sha256:da49a05fd62cda46a7d73ec53a8d0adc5835d2070f6f0c51b12233a673c2e109
docs(mwp-1): mark Phase 5 complete, all acceptance criteria…
Sonnet 4.6
27 days ago