gabriel / musehub public
test_graph_depth.py python
206 lines 7.4 KB
Raw
sha256:9590cee1e0ccd6c76528f005b95d634d80f5019f0dcb7c371e149adc31d1fb65 refactor: enforce gRPC framing on all MWP wire traffic Sonnet 4.6 minor ⚠ breaking 156 days ago
1 """TDD — I2: Root distance invariant.
2
3 root_distance = minimum hops from a node to any human node via any edge type.
4 Humans are always 0. None means no path to any human exists.
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.depth import RootDistanceIndex
12
13
14 S = EdgeType.SPAWNS
15 M = EdgeType.MEMBER_OF
16
17
18 def build(nodes: dict[str, NodeType], *edges: tuple[str, str, EdgeType]) -> RootDistanceIndex:
19 """Build an index from a node-type map and edge list."""
20 d = IdentityDAG.from_nodes_and_edges(
21 nodes,
22 [GraphEdge(from_handle=f, to_handle=t, edge_type=e) for f, t, e in edges],
23 )
24 return RootDistanceIndex.build(d)
25
26
27 # ── Humans ────────────────────────────────────────────────────────────────────
28
29 class TestHumanDepth:
30 def test_lone_human_is_zero(self):
31 idx = build({"alice": NodeType.HUMAN})
32 assert idx.distance("alice") == 0
33
34 def test_multiple_humans_all_zero(self):
35 idx = build({"alice": NodeType.HUMAN, "bob": NodeType.HUMAN})
36 assert idx.distance("alice") == 0
37 assert idx.distance("bob") == 0
38
39
40 # ── Agents via SPAWNS ─────────────────────────────────────────────────────────
41
42 class TestAgentSpawnDepth:
43 def test_agent_spawned_by_human_is_one(self):
44 idx = build(
45 {"alice": NodeType.HUMAN, "bot-1": NodeType.AGENT},
46 ("alice", "bot-1", S),
47 )
48 assert idx.distance("bot-1") == 1
49
50 def test_agent_spawned_by_agent_is_two(self):
51 idx = build(
52 {"alice": NodeType.HUMAN, "a1": NodeType.AGENT, "a2": NodeType.AGENT},
53 ("alice", "a1", S),
54 ("a1", "a2", S),
55 )
56 assert idx.distance("a2") == 2
57
58 def test_deep_spawn_chain(self):
59 nodes = {"h": NodeType.HUMAN} | {f"a{i}": NodeType.AGENT for i in range(1, 6)}
60 edges = [("h", "a1", S)] + [(f"a{i}", f"a{i+1}", S) for i in range(1, 5)]
61 idx = build(nodes, *edges)
62 for i in range(1, 6):
63 assert idx.distance(f"a{i}") == i
64
65 def test_agent_with_no_spawner_is_none(self):
66 idx = build({"bot-1": NodeType.AGENT})
67 assert idx.distance("bot-1") is None
68
69 def test_agent_chain_with_no_human_root_is_none(self):
70 idx = build(
71 {"a1": NodeType.AGENT, "a2": NodeType.AGENT},
72 ("a1", "a2", S),
73 )
74 assert idx.distance("a1") is None
75 assert idx.distance("a2") is None
76
77
78 # ── Orgs via MEMBER_OF ────────────────────────────────────────────────────────
79
80 class TestOrgMemberDepth:
81 def test_org_with_human_member_is_one(self):
82 idx = build(
83 {"alice": NodeType.HUMAN, "acme": NodeType.ORG},
84 ("alice", "acme", M),
85 )
86 assert idx.distance("acme") == 1
87
88 def test_org_with_agent_member_depth_two(self):
89 idx = build(
90 {"alice": NodeType.HUMAN, "bot": NodeType.AGENT, "acme": NodeType.ORG},
91 ("alice", "bot", S),
92 ("bot", "acme", M),
93 )
94 assert idx.distance("acme") == 2
95
96 def test_nested_orgs(self):
97 idx = build(
98 {"alice": NodeType.HUMAN, "org-a": NodeType.ORG, "org-b": NodeType.ORG},
99 ("alice", "org-a", M),
100 ("org-a", "org-b", M),
101 )
102 assert idx.distance("org-a") == 1
103 assert idx.distance("org-b") == 2
104
105 def test_org_with_no_human_reachable_is_none(self):
106 idx = build(
107 {"bot": NodeType.AGENT, "acme": NodeType.ORG},
108 ("bot", "acme", M),
109 )
110 assert idx.distance("acme") is None
111
112
113 # ── Shortest path wins ────────────────────────────────────────────────────────
114
115 class TestShortestPath:
116 def test_diamond_takes_shorter_path(self):
117 # alice(0) → a1(1) → a3(?); alice(0) → org-x(1) → a3(?)
118 # a3 reachable in 2 hops via either path — should be 2
119 idx = build(
120 {
121 "alice": NodeType.HUMAN,
122 "a1": NodeType.AGENT,
123 "a3": NodeType.AGENT,
124 "org-x": NodeType.ORG,
125 },
126 ("alice", "a1", S),
127 ("alice", "org-x", M),
128 ("a1", "a3", S),
129 ("org-x", "a3", M),
130 )
131 assert idx.distance("a3") == 2
132
133 def test_two_human_paths_takes_shorter(self):
134 # alice(0) → a1(1) → target; bob(0) → target directly
135 # target should be 1 (via bob), not 2 (via alice→a1)
136 idx = build(
137 {
138 "alice": NodeType.HUMAN,
139 "bob": NodeType.HUMAN,
140 "a1": NodeType.AGENT,
141 "target": NodeType.AGENT,
142 },
143 ("alice", "a1", S),
144 ("a1", "target", S),
145 ("bob", "target", S),
146 )
147 assert idx.distance("target") == 1
148
149 def test_deeply_nested_finds_shortest(self):
150 # long path: h→a1→a2→a3→target (depth 4)
151 # short path: h→target directly (depth 1)
152 idx = build(
153 {
154 "h": NodeType.HUMAN,
155 "a1": NodeType.AGENT,
156 "a2": NodeType.AGENT,
157 "a3": NodeType.AGENT,
158 "target": NodeType.AGENT,
159 },
160 ("h", "a1", S),
161 ("a1", "a2", S),
162 ("a2", "a3", S),
163 ("a3", "target", S),
164 ("h", "target", S),
165 )
166 assert idx.distance("target") == 1
167
168
169 # ── Unknown handle ────────────────────────────────────────────────────────────
170
171 class TestUnknownHandle:
172 def test_unknown_handle_raises(self):
173 idx = build({"alice": NodeType.HUMAN})
174 with pytest.raises(KeyError):
175 idx.distance("nobody")
176
177
178 # ── human_ancestors ──────────────────────────────────────────────────────────
179
180 class TestHumanAncestors:
181 def test_human_is_own_ancestor(self):
182 idx = build({"alice": NodeType.HUMAN})
183 assert idx.human_ancestors("alice") == {"alice"}
184
185 def test_agent_inherits_spawners_ancestors(self):
186 idx = build(
187 {"alice": NodeType.HUMAN, "bob": NodeType.HUMAN, "bot": NodeType.AGENT},
188 ("alice", "bot", S),
189 )
190 assert idx.human_ancestors("bot") == {"alice"}
191
192 def test_org_inherits_all_reachable_humans(self):
193 idx = build(
194 {
195 "alice": NodeType.HUMAN,
196 "bob": NodeType.HUMAN,
197 "acme": NodeType.ORG,
198 },
199 ("alice", "acme", M),
200 ("bob", "acme", M),
201 )
202 assert idx.human_ancestors("acme") == {"alice", "bob"}
203
204 def test_no_ancestors_returns_empty(self):
205 idx = build({"bot": NodeType.AGENT})
206 assert idx.human_ancestors("bot") == set()
File History 1 commit
sha256:9590cee1e0ccd6c76528f005b95d634d80f5019f0dcb7c371e149adc31d1fb65 refactor: enforce gRPC framing on all MWP wire traffic Sonnet 4.6 minor ⚠ 156 days ago