Summary
When using min_hops to filter paths, hop labels still use "first seen" (minimum hop) semantics. This causes nodes reachable via multiple path lengths to be labeled with the shortest path's hop distance, even when that shorter path is filtered out by min_hops.
Reproduction
nodes = [{"id": x} for x in ["a", "b", "c", "d", "x"]]
edges = [
{"edge_id": "e1", "src": "a", "dst": "b"},
{"edge_id": "e2", "src": "b", "dst": "c"},
{"edge_id": "e3", "src": "c", "dst": "d"},
{"edge_id": "short1", "src": "a", "dst": "x"},
{"edge_id": "short2", "src": "x", "dst": "d"},
]
# Graph has two paths from a to d:
# - Long path: a→b→c→d (3 hops)
# - Short path: a→x→d (2 hops)
ops = [
n({"id": "a"}),
e_forward(min_hops=3, max_hops=3, label_node_hops="hop"),
n(),
]
# With min_hops=3, only the long path is valid
# Expected: node d labeled with hop=3
# Actual: node d labeled with hop=2 (from filtered-out short path)Root Cause
The hop labeling logic in hop.py tracks minimum hop distance per node (groupby().min() pattern). This is correct for display purposes when all paths are valid, but incorrect when min_hops filters out shorter paths.
The Yannakakis semijoin pruning correctly excludes edges not on valid paths, but the hop labels are computed before/independently of this filtering.
Impact
- Hop labels may show incorrect distances when
min_hops > 1
- This is a display/labeling issue only - path validity and edge filtering are correct
Failing Test
tests/gfql/ref/test_enumerator_parity.py::TestTrickyHopBounds::test_branching_path_lengths
Related
🤖 Generated with Claude Code
Summary
When using
min_hopsto filter paths, hop labels still use "first seen" (minimum hop) semantics. This causes nodes reachable via multiple path lengths to be labeled with the shortest path's hop distance, even when that shorter path is filtered out bymin_hops.Reproduction
Root Cause
The hop labeling logic in
hop.pytracks minimum hop distance per node (groupby().min()pattern). This is correct for display purposes when all paths are valid, but incorrect whenmin_hopsfilters out shorter paths.The Yannakakis semijoin pruning correctly excludes edges not on valid paths, but the hop labels are computed before/independently of this filtering.
Impact
min_hops > 1Failing Test
tests/gfql/ref/test_enumerator_parity.py::TestTrickyHopBounds::test_branching_path_lengthsRelated
🤖 Generated with Claude Code