test_graph_cycle.py
python
sha256:0997d6250ae6476362f6fe2025af7789f46d03df3e9f34356d5e8ee79b201923
fix(issues): use issue number as pagination cursor, not cre…
Sonnet 4.6
patch
9 days ago
| 1 | """TDD — I1: Acyclicity invariant for the identity DAG. |
| 2 | |
| 3 | Every test here drives one behaviour of CycleDetector. |
| 4 | No implementation exists yet; all tests must fail red before we write code. |
| 5 | """ |
| 6 | from __future__ import annotations |
| 7 | |
| 8 | import pytest |
| 9 | |
| 10 | from musehub.graph.dag import EdgeType, GraphEdge, IdentityDAG, NodeType |
| 11 | from musehub.graph.cycle import CycleDetector, CycleError |
| 12 | |
| 13 | |
| 14 | # ── helpers ────────────────────────────────────────────────────────────────── |
| 15 | |
| 16 | def dag(*edges: tuple[str, str, EdgeType]) -> IdentityDAG: |
| 17 | """Build an IdentityDAG from (from, to, type) triples.""" |
| 18 | return IdentityDAG.from_edges( |
| 19 | [GraphEdge(from_handle=f, to_handle=t, edge_type=e) for f, t, e in edges] |
| 20 | ) |
| 21 | |
| 22 | |
| 23 | S = EdgeType.SPAWNS |
| 24 | M = EdgeType.MEMBER_OF |
| 25 | |
| 26 | |
| 27 | # ── SPAWNS edge — valid cases ───────────────────────────────────────────────── |
| 28 | |
| 29 | class TestSpawnsValid: |
| 30 | def test_empty_graph_accepts_any_spawn(self) -> None: |
| 31 | d = IdentityDAG.empty() |
| 32 | CycleDetector(d).assert_no_cycle("alice", "bot-1", S) |
| 33 | |
| 34 | def test_human_spawns_agent(self) -> None: |
| 35 | d = IdentityDAG.empty() |
| 36 | CycleDetector(d).assert_no_cycle("alice", "bot-1", S) |
| 37 | |
| 38 | def test_agent_spawns_agent(self) -> None: |
| 39 | d = dag(("alice", "bot-1", S)) |
| 40 | CycleDetector(d).assert_no_cycle("bot-1", "bot-2", S) |
| 41 | |
| 42 | def test_org_spawns_agent(self) -> None: |
| 43 | d = dag(("alice", "acme", M)) |
| 44 | CycleDetector(d).assert_no_cycle("acme", "acme-bot", S) |
| 45 | |
| 46 | def test_deep_spawn_chain_valid(self) -> None: |
| 47 | d = dag( |
| 48 | ("alice", "a1", S), |
| 49 | ("a1", "a2", S), |
| 50 | ("a2", "a3", S), |
| 51 | ("a3", "a4", S), |
| 52 | ) |
| 53 | CycleDetector(d).assert_no_cycle("a4", "a5", S) |
| 54 | |
| 55 | def test_diamond_dag_no_cycle(self) -> None: |
| 56 | # alice → a1 and alice → a2, both → a3: valid DAG, no cycle |
| 57 | d = dag( |
| 58 | ("alice", "a1", S), |
| 59 | ("alice", "a2", S), |
| 60 | ("a1", "a3", S), |
| 61 | ("a2", "a3", S), |
| 62 | ) |
| 63 | CycleDetector(d).assert_no_cycle("alice", "a4", S) |
| 64 | |
| 65 | |
| 66 | # ── SPAWNS edge — cycle cases ───────────────────────────────────────────────── |
| 67 | |
| 68 | class TestSpawnsCycle: |
| 69 | def test_self_spawn_rejected(self) -> None: |
| 70 | d = IdentityDAG.empty() |
| 71 | with pytest.raises(CycleError): |
| 72 | CycleDetector(d).assert_no_cycle("bot-1", "bot-1", S) |
| 73 | |
| 74 | def test_direct_spawn_cycle(self) -> None: |
| 75 | # alice → bot-1; bot-1 tries to spawn alice |
| 76 | d = dag(("alice", "bot-1", S)) |
| 77 | with pytest.raises(CycleError): |
| 78 | CycleDetector(d).assert_no_cycle("bot-1", "alice", S) |
| 79 | |
| 80 | def test_indirect_spawn_cycle_three_nodes(self) -> None: |
| 81 | # alice → a1 → a2; a2 tries to spawn alice |
| 82 | d = dag(("alice", "a1", S), ("a1", "a2", S)) |
| 83 | with pytest.raises(CycleError): |
| 84 | CycleDetector(d).assert_no_cycle("a2", "alice", S) |
| 85 | |
| 86 | def test_indirect_spawn_cycle_five_nodes(self) -> None: |
| 87 | d = dag( |
| 88 | ("h", "a1", S), |
| 89 | ("a1", "a2", S), |
| 90 | ("a2", "a3", S), |
| 91 | ("a3", "a4", S), |
| 92 | ) |
| 93 | with pytest.raises(CycleError): |
| 94 | CycleDetector(d).assert_no_cycle("a4", "h", S) |
| 95 | |
| 96 | |
| 97 | # ── MEMBER_OF edge — valid cases ────────────────────────────────────────────── |
| 98 | |
| 99 | class TestMemberOfValid: |
| 100 | def test_human_joins_org(self) -> None: |
| 101 | d = IdentityDAG.empty() |
| 102 | CycleDetector(d).assert_no_cycle("alice", "acme", M) |
| 103 | |
| 104 | def test_agent_joins_org(self) -> None: |
| 105 | d = dag(("alice", "bot-1", S)) |
| 106 | CycleDetector(d).assert_no_cycle("bot-1", "acme", M) |
| 107 | |
| 108 | def test_org_joins_parent_org(self) -> None: |
| 109 | d = dag(("alice", "acme", M)) |
| 110 | CycleDetector(d).assert_no_cycle("acme", "conglomerate", M) |
| 111 | |
| 112 | def test_deep_org_nesting_valid(self) -> None: |
| 113 | d = dag( |
| 114 | ("alice", "org-a", M), |
| 115 | ("org-a", "org-b", M), |
| 116 | ("org-b", "org-c", M), |
| 117 | ) |
| 118 | CycleDetector(d).assert_no_cycle("org-c", "org-d", M) |
| 119 | |
| 120 | def test_multiple_members_in_org_valid(self) -> None: |
| 121 | d = dag( |
| 122 | ("alice", "acme", M), |
| 123 | ("bob", "acme", M), |
| 124 | ("bot-1", "acme", M), |
| 125 | ) |
| 126 | CycleDetector(d).assert_no_cycle("carol", "acme", M) |
| 127 | |
| 128 | |
| 129 | # ── MEMBER_OF edge — cycle cases ────────────────────────────────────────────── |
| 130 | |
| 131 | class TestMemberOfCycle: |
| 132 | def test_self_membership_rejected(self) -> None: |
| 133 | d = IdentityDAG.empty() |
| 134 | with pytest.raises(CycleError): |
| 135 | CycleDetector(d).assert_no_cycle("acme", "acme", M) |
| 136 | |
| 137 | def test_direct_org_cycle(self) -> None: |
| 138 | # acme has sub-org as member; sub-org tries to add acme as member |
| 139 | d = dag(("sub-org", "acme", M)) |
| 140 | with pytest.raises(CycleError): |
| 141 | CycleDetector(d).assert_no_cycle("acme", "sub-org", M) |
| 142 | |
| 143 | def test_indirect_org_cycle_three(self) -> None: |
| 144 | d = dag(("org-a", "org-b", M), ("org-b", "org-c", M)) |
| 145 | with pytest.raises(CycleError): |
| 146 | CycleDetector(d).assert_no_cycle("org-c", "org-a", M) |
| 147 | |
| 148 | def test_indirect_org_cycle_five(self) -> None: |
| 149 | d = dag( |
| 150 | ("org-a", "org-b", M), |
| 151 | ("org-b", "org-c", M), |
| 152 | ("org-c", "org-d", M), |
| 153 | ("org-d", "org-e", M), |
| 154 | ) |
| 155 | with pytest.raises(CycleError): |
| 156 | CycleDetector(d).assert_no_cycle("org-e", "org-a", M) |
| 157 | |
| 158 | |
| 159 | # ── Cross-edge-type cycles ───────────────────────────────────────────────────── |
| 160 | |
| 161 | class TestCrossEdgeCycle: |
| 162 | def test_spawns_then_member_of_cycle(self) -> None: |
| 163 | # alice spawns bot-1; bot-1 is member of acme; acme tries to spawn alice |
| 164 | d = dag(("alice", "bot-1", S), ("bot-1", "acme", M)) |
| 165 | with pytest.raises(CycleError): |
| 166 | CycleDetector(d).assert_no_cycle("acme", "alice", S) |
| 167 | |
| 168 | def test_member_of_then_spawns_cycle(self) -> None: |
| 169 | # alice is member of acme; acme spawns bot-1; bot-1 tries to add alice as spawned |
| 170 | d = dag(("alice", "acme", M), ("acme", "bot-1", S)) |
| 171 | with pytest.raises(CycleError): |
| 172 | CycleDetector(d).assert_no_cycle("bot-1", "alice", S) |
| 173 | |
| 174 | def test_complex_cross_edge_valid(self) -> None: |
| 175 | # Verify a legitimate complex DAG is not falsely rejected |
| 176 | # alice → acme (member), alice spawns bot-1, bot-1 → lab (member) |
| 177 | d = dag( |
| 178 | ("alice", "acme", M), |
| 179 | ("alice", "bot-1", S), |
| 180 | ("bot-1", "lab", M), |
| 181 | ) |
| 182 | CycleDetector(d).assert_no_cycle("bob", "acme", M) |
File History
1 commit
sha256:0997d6250ae6476362f6fe2025af7789f46d03df3e9f34356d5e8ee79b201923
fix(issues): use issue number as pagination cursor, not cre…
Sonnet 4.6
patch
9 days ago