gabriel / muse public
feat BREAKING graph task/walk-dag-phase1 #3 / 3
AI Agent gabriel · 125 days ago · May 9, 2026 · Diff

feat(graph): add walk_dag generic DAG walker, rewire iter_ancestors

- Introduce walk_dag() in muse/core/graph.py: generic BFS/DFS iterator parameterised on node type T and an adjacency function. Supports order=bfs|dfs, exclude, prune predicate, and max_nodes cap. - Rewire iter_ancestors() as a thin wrapper over walk_dag with a caching adjacency closure (one read_commit() call per node, no double reads). - Update test_core_graph.py structural deque check to target walk_dag. - Add tests/test_walk_dag.py: 33 tests covering the full walk_dag contract (BFS/DFS order, diamond deduplication, prune, exclude, max_nodes, generic types, multi-source starts, iter_ancestors routes through walk_dag).

sha256:c65ab692776f3962fa99fad05a206247cf433637c3474047d2726a9adb585cac sha
sha256:e340785b297660da7a2dc5617a5676ebb8f855d7dbad81652a3a7aaecf6b9110 parent
+57 ~6 symbols
sha256:94b3dd3a6efeb7f8161f0439dca69de8eb1e2983e40520f3a6afc18ec2475306 snapshot
+57
symbols added
~6
symbols modified
0
dead code introduced
Semantic Changes 63 symbols
~ tests/test_walk_dag.py .py 52 symbols added
+ TestIterAncestorsRoutesThroughWalkDag class class TestIterAncestorsRoutesThroughWalkDag L363–372
+ test_iter_ancestors_calls_walk_dag method method test_iter_ancestors_calls_walk_dag L364–372
+ TestWalkDagBasic class class TestWalkDagBasic L88–126
+ test_empty_starts_yields_nothing method method test_empty_starts_yields_nothing L89–91
+ test_invalid_order_raises method method test_invalid_order_raises L124–126
+ test_leaf_node_as_start method method test_leaf_node_as_start L119–122
+ test_linear_chain_bfs_all_visited method method test_linear_chain_bfs_all_visited L103–105
+ test_linear_chain_bfs_start_first method method test_linear_chain_bfs_start_first L111–113
+ test_linear_chain_dfs_all_visited method method test_linear_chain_dfs_all_visited L107–109
+ test_linear_chain_dfs_start_first method method test_linear_chain_dfs_start_first L115–117
+ test_single_node_iterable_start method method test_single_node_iterable_start L98–101
+ test_single_node_no_neighbours method method test_single_node_no_neighbours L93–96
+ TestWalkDagDiamond class class TestWalkDagDiamond L193–202
+ test_diamond_bfs_visits_shared_once method method test_diamond_bfs_visits_shared_once L194–197
+ test_diamond_dfs_visits_shared_once method method test_diamond_dfs_visits_shared_once L199–202
+ TestWalkDagExclude class class TestWalkDagExclude L249–272
+ test_exclude_does_not_mutate_input method method test_exclude_does_not_mutate_input L268–272
+ test_exclude_leaf method method test_exclude_leaf L263–266
+ test_exclude_pre_seeds_visited method method test_exclude_pre_seeds_visited L250–256
+ test_exclude_start_node_yields_nothing method method test_exclude_start_node_yields_nothing L258–261
+ TestWalkDagGenericType class class TestWalkDagGenericType L304–320
+ test_works_with_integers method method test_works_with_integers L305–310
+ test_works_with_tuples method method test_works_with_tuples L312–320
+ TestWalkDagMaxNodes class class TestWalkDagMaxNodes L280–296
+ test_max_nodes_caps_count method method test_max_nodes_caps_count L289–291
+ test_max_nodes_larger_than_graph method method test_max_nodes_larger_than_graph L293–296
+ test_max_nodes_one_yields_start method method test_max_nodes_one_yields_start L285–287
+ test_max_nodes_zero_yields_nothing method method test_max_nodes_zero_yields_nothing L281–283
+ TestWalkDagMultiSource class class TestWalkDagMultiSource L328–355
+ test_multi_source_exclude_applies_to_all method method test_multi_source_exclude_applies_to_all L347–355
+ test_multi_source_shared_ancestor_once method method test_multi_source_shared_ancestor_once L338–345
+ test_multi_source_visits_all_reachable method method test_multi_source_visits_all_reachable L329–336
+ TestWalkDagOrder class class TestWalkDagOrder L134–185
+ test_bfs_is_level_order method method test_bfs_is_level_order L135–150
+ test_bfs_vs_dfs_different_on_tree method method test_bfs_vs_dfs_different_on_tree L180–185
+ test_dfs_is_depth_first method method test_dfs_is_depth_first L152–178
+ TestWalkDagPrune class class TestWalkDagPrune L210–241
+ test_prune_at_leaf_no_effect method method test_prune_at_leaf_no_effect L224–227
+ test_prune_at_root_yields_nothing method method test_prune_at_root_yields_nothing L219–222
+ test_prune_both_branches_of_diamond method method test_prune_both_branches_of_diamond L238–241
+ test_prune_one_branch_of_diamond method method test_prune_one_branch_of_diamond L229–236
+ test_prune_stops_at_matched_node method method test_prune_stops_at_matched_node L211–217
+ _DIAMOND variable variable _DIAMOND L57–62
+ _LINEAR variable variable _LINEAR L48–53
+ _TREE variable variable _TREE L67–75
+ _adj function function _adj L78–80
+ Callable import import Callable L36–36
+ Iterable import import Iterable L35–35
+ Iterator import import Iterator L35–35
+ annotations import import annotations L33–33
+ pytest import import pytest L38–38
+ walk_dag import import walk_dag L40–40
~ muse/core/graph.py .py 5 symbols added, 4 symbols modified
+ T variable variable T L50–50
+ Callable import import Callable L45–45
+ Literal import import Literal L46–46
+ TypeVar import import TypeVar L46–46
+ walk_dag function function walk_dag L57–134
~ AbstractSet
~ Iterable
~ Iterator
~ iter_ancestors
~ tests/test_core_graph.py .py 2 symbols modified
~ TestIterAncestors
~ test_uses_deque_not_list
← Older Oldest on task/walk-dag-phase1
All commits Newer feat(graph): Phase 2 — migrate 7 inline BFS/DFS sites to iter_an… sha256:6f56135116d5b7b40455fa039c5ba2967a8f07832f3ffe7204585dc598755c89

0 comments

No comments yet. Be the first to start the discussion.

To add a comment, use the Muse CLI: muse hub commit comment sha256:c65ab692776f3962fa99fad05a206247cf433637c3474047d2726a9adb585cac --body "your comment"