gabriel / musehub public
cycle.py python
42 lines 1.4 KB
Raw
sha256:d035733f21ccff27735fddebfbbe0ed24565a32a22db8de5885402262671ecd2 chore: bump version to 0.2.0rc15 for musehub#113 fix release Sonnet 4.6 patch 15 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 11 commits
sha256:d035733f21ccff27735fddebfbbe0ed24565a32a22db8de5885402262671ecd2 chore: bump version to 0.2.0rc15 for musehub#113 fix release Sonnet 4.6 patch 15 days ago
sha256:0032d6cfa33bc3c8367436ad768e7dd0e339b4332153160247da8266cb5fa352 Merge branch 'task/version-tags-phase3-server' into dev Human 17 days ago
sha256:4669620efda9ff41c55bdefd1f7bfe1c239d468428744c84ead9957e5a003a53 merge: rescue snapshot-recovery hardening (c00aa21d) into d… Opus 4.8 minor ⚠ 30 days ago
sha256:a59da49c4611b970fc4b6ae48678ce4943261c213a07ddbd73ce9201df869b4a fix: remove false-positive proposal_comments index drop fro… Sonnet 4.6 patch 34 days ago
sha256:0a240d6dbff234f07d98a28a4a9a68db702f3f9ff9260196f24219bdb1c0b6f3 feat: render markdown mists as HTML with heading anchor links Sonnet 4.6 patch 35 days ago
sha256:24a7d47486ebc4ebd1832830580e177ec6f877b48dced8c000e198cdec4ce9d6 Merge 'task/bump-version-rc12' into 'dev' — proposal: Bump … Human 36 days ago
sha256:b9ff931d147e0114a1f17060f415b89ed551c170a91ff226c70437aa5c85f9ee Merge 'task/bump-version-rc12' into 'dev' — proposal: Bump … Human 36 days ago
sha256:d1122d21e73471879b460037b22c0b50fded7c423444a176f248428f75dac39c Merge 'task/fix-issue-pagination-cursor' into 'dev' — propo… Human 36 days ago
sha256:01e18975e73d2b3cd5b6db7929c895bef9aa6e0d4391dc5b2adfc548b41318dd Merge 'feat/adding-debug-logs-to-staging' into 'dev' — prop… Human 36 days ago
sha256:6b1949fc2797ca4c1936a637a4cbfec828ef56cf52398a2e74ca3c4f494e728f fix: use wire_bytes not mpack_bytes_raw in compute_object_b… Sonnet 4.6 patch 48 days ago
sha256:b99f2455dc346966d040133f5203297e6e3ef5803a93728a2c30568d0a0f7583 rename: delta_add → delta_upsert across wire format, models… Sonnet 4.6 patch 51 days ago