Reachability API: path witnesses between a source and a sink

[rahlk]

Part of #170 (source↔sink reachability API).

Goal

Given a (source, sink) pair that are connected, return the actual path(s) through the call graph that connect them — the witness/trace that explains why they match. Forward/reverse reachability (#171, #172) answer whether; this answers how, which is what makes a match auditable and triageable.

Proposed API

def get_reachability_paths(
    source: str,
    sink: str,
    *,
    shortest_only: bool = True,    # one/all shortest paths vs. enumerate simple paths
    max_paths: int | None = None,  # cap when enumerating
    max_depth: int | None = None,  # path-length bound (cutoff)
) -> List[List[str]]:              # each path = ordered list of signatures source..sink
    ...

Each path is the ordered list of node signatures from source to sink; an optional richer return could include the per-edge metadata (provenance, dispatch tag) so a trace is fully explainable.

Semantics

Directed paths source -CALLS*-> sink. shortest_only=True returns the shortest path(s); otherwise enumerate simple (acyclic) paths up to max_depth / max_paths.

Backing implementations

• Neo4j:
  • shortest: MATCH p = shortestPath((s {signature:$src})-[:CALLS*..$depth]->(t {signature:$sink})) RETURN [n IN nodes(p) | n.signature]
  • all shortest: allShortestPaths(...)
  • bounded simple paths / k-paths: APOC (apoc.path.expandConfig, apoc.algo.allSimplePaths)
• In-memory (NetworkX): nx.shortest_path, nx.all_shortest_paths, nx.all_simple_paths(G, source, sink, cutoff=max_depth).

Notes

• Simple-path enumeration can explode combinatorially; default to shortest, require explicit opt-in for exhaustive enumeration, and always surface when results were truncated by max_paths / max_depth.
• Returning [] cleanly distinguishes "not reachable" from a single empty path.

Acceptance criteria

• Method on the backend contract + façade, implemented for the Neo4j and in-memory backends with matching semantics.
• Shortest-only and bounded-enumeration modes both work; max_paths / max_depth honored and truncation observable.
• On a known fixture, the returned path is a valid call-graph walk from source to sink (every consecutive pair is a real CALLS edge) and matches the in-memory backend's result.
• Unreachable (source, sink) returns [].