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