test_graph_depth.py
python
sha256:34035d72cef530c1ab9d6a6f53be18d803dde705fc3157617d70352a96d0747b
Merge branch 'fix/wire-push-external-parent-manifest' into dev
Human
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
14 commits
sha256:34035d72cef530c1ab9d6a6f53be18d803dde705fc3157617d70352a96d0747b
Merge branch 'fix/wire-push-external-parent-manifest' into dev
Human
8 days ago
sha256:fc04e4cae9e1774d6a21b65c45daeed0e6787eb581d13aa1b03bfe9384a34226
Merge branch 'fix/two-column-scroll-layout' into dev
Human
8 days ago
sha256:408916fc5973ba59c6e4eebaa80ebdcc801c0a63205651e25009d11548f79454
chore: bump version to 0.2.0.dev2 — nightly.2, matching muse
Sonnet 4.6
patch
11 days ago
sha256:d035733f21ccff27735fddebfbbe0ed24565a32a22db8de5885402262671ecd2
chore: bump version to 0.2.0rc15 for musehub#113 fix release
Sonnet 4.6
patch
14 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
⚠
29 days ago
sha256:a59da49c4611b970fc4b6ae48678ce4943261c213a07ddbd73ce9201df869b4a
fix: remove false-positive proposal_comments index drop fro…
Sonnet 4.6
patch
33 days ago
sha256:0a240d6dbff234f07d98a28a4a9a68db702f3f9ff9260196f24219bdb1c0b6f3
feat: render markdown mists as HTML with heading anchor links
Sonnet 4.6
patch
34 days ago
sha256:24a7d47486ebc4ebd1832830580e177ec6f877b48dced8c000e198cdec4ce9d6
Merge 'task/bump-version-rc12' into 'dev' — proposal: Bump …
Human
35 days ago
sha256:b9ff931d147e0114a1f17060f415b89ed551c170a91ff226c70437aa5c85f9ee
Merge 'task/bump-version-rc12' into 'dev' — proposal: Bump …
Human
35 days ago
sha256:d1122d21e73471879b460037b22c0b50fded7c423444a176f248428f75dac39c
Merge 'task/fix-issue-pagination-cursor' into 'dev' — propo…
Human
35 days ago
sha256:01e18975e73d2b3cd5b6db7929c895bef9aa6e0d4391dc5b2adfc548b41318dd
Merge 'feat/adding-debug-logs-to-staging' into 'dev' — prop…
Human
35 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
50 days ago