Feature Request: Implement Efficient Shortest Path / Deep Traversal Algorithms in Apache AGE (BFS, Dijkstra, A*, k-Shortest Paths) #1

Background

Apache AGE currently supports flexible variable-length path patterns such as:

SELECT * 
FROM cypher('graph_name', $$
  MATCH p = (a:Table {name:'Contact'})-[*1..6]-(b:Table {name:'Account'})
  WHERE a <> b
  RETURN p
  ORDER BY length(p) ASC
  LIMIT 5
$$) AS (path agtype);

While this syntax is powerful, it forces AGE to enumerate all possible paths within the specified hop range before sorting and limiting results.

In large graphs or even moderately connected graphs, especially with *..6 depth, this leads to:

• Excessive search space (combinatorial explosion).
• Very high execution times (seconds to minutes).
• High memory and CPU usage.
• Poor scalability when multiple such queries run concurrently.

AGE currently lacks an early-stop shortest path search mechanism like that found in other graph engines (Neo4j’s shortestPath, Memgraph’s all_shortest_paths, etc.).

The Problem in Practice

Example scenario from a real AGE deployment:

• Graph structure:
  Tables connected via Columns and REFERS_TO edges.
  A real logical “Table-to-Table” hop is 3 underlying edges.

• Business requirement:
  Find paths up to 6 edges deep (≈ 2 table hops) between two known tables.

• Query pattern:
  [*1..6] with ORDER BY length(path) ASC LIMIT 5.

• Observed issue:
  AGE enumerates 100,000+ candidate paths just to return 5 shortest ones.

• Performance:

  • Local Docker AGE (1 graph): fast.
  • K8s AGE (10–15 graphs, NFS storage): slow (20–60s or more).
  • Resource scaling helps little—algorithmic bottleneck dominates.

What’s Needed

We need built-in path-finding algorithms that:

1. Avoid enumerating all paths when only the shortest (or k shortest) are required.

2. Use efficient traversal strategies like:

   • Breadth-First Search (BFS) for unweighted graphs.
   • Dijkstra’s algorithm for weighted shortest paths.
   • A* for heuristic-guided searches.
   • k-Shortest Paths (Yen’s algorithm, Eppstein’s algorithm) when multiple shortest paths are needed.

3. Support hop limits (max depth) and cost limits (max total weight).

4. Return results ordered by path length or cost without post-hoc sorting of the entire search space.

5. Work directly inside the cypher() function with native Cypher syntax.

Proposed Syntax Extensions

1) Single Shortest Path

SELECT * 
FROM cypher('graph_name', $$
  MATCH p = shortestPath(
    (a:Table {name:'Contact'})-[*1..6]-(b:Table {name:'Account'})
  )
  RETURN p
$$) AS (path agtype);

2) k Shortest Paths

SELECT * 
FROM cypher('graph_name', $$
  MATCH p = kShortestPaths(
    (a:Table {name:'Contact'})-[*1..6]-(b:Table {name:'Account'}),
    5
  )
  RETURN p
$$) AS (path agtype);

3) Weighted Shortest Path

SELECT * 
FROM cypher('graph_name', $$
  MATCH p = weightedShortestPath(
    (a)-[e*1..6]-(b),
    e.cost
  )
  RETURN p
$$) AS (path agtype);

Implementation Considerations

• Traversal engine changes:
  Implement BFS/Dijkstra/A* in AGE’s traversal executor to stop expanding once the shortest/k-shortest paths are found.

• Index utilization:
  Leverage vertex/edge property indexes for faster start node matching.

• Early termination:
  Stop search when:

  • All k shortest paths are found.
  • Path length/cost exceeds specified limit.

• Weighted support:
  Accept edge property as weight; default to unweighted if omitted.

• Parallelism:
  Optionally run multi-source BFS/Dijkstra in parallel worker threads.

Example Performance Impact

Current (brute-force with ORDER BY):

• Graph: ~2k nodes, ~10k edges.
• Depth: *1..6.
• Result: 5 shortest paths.
• Execution time: 20–30 seconds (due to enumerating 100k+ paths).

Proposed (BFS early stop):

• Same graph & depth.
• Execution time: <100 ms (stop after first k shortest paths found).

Benefits

• Massive speed improvements for shortest path scenarios.
• Reduced memory usage (no storing all candidate paths).
• Better concurrency (fewer long-running queries blocking others).
• Makes AGE competitive with Neo4j, Memgraph, and other production-ready graph engines for traversal-heavy workloads.