Declarative Route Planning With Cypher 25 — Graph Traversal Grows Up

Photo of Pierre Halftermeyer

Pierre Halftermeyer

Field Engineer, Neo4j

12 min read

Create a free graph database instance in Neo4j AuraDB

Cypher 25 represents a major leap forward for graph developers. This blog examines its state-aware pruning, repeatable traversals, and conditional logic, enabling the modeling of complete reasoning processes.

Neo4j allows you to describe what you want from a graph using its Cypher query language, without needing to specify the exact computation steps. With Cypher 5, declarative traversal capabilities were significantly enhanced through quantified path patterns (QPP), reducing reliance on procedural tools like apoc.path or the Traversal API. Now, Cypher 25 advances this further by incorporating state-aware pruning, repeatable traversals, and conditional logic, enabling the modeling of complete reasoning processes — such as electric vehicle (EV) route planning — directly within Cypher. This blog will examine these innovations via a practical example.

From the Cypher 5 Bullet Train to Cypher 25

As outlined in Did You Take the Neo4j 5 Cypher Bullet Train?, Cypher 5 dramatically improved the existing declarative traversal capabilities (variable-length traversal). With an efficient implementation of QPPs, whose syntax is defined by the GQL standard, Neo4j allows precise, declarative control over path exploration, with traversal-local pruning to skip invalid branches early. In Neo4j, the filtering defined in these QPPs is inlined and executed during path expansion rather than as a post-filter, boosting both speed and efficiency. Cypher 5 also integrates seamlessly with Neo4j’s parallel runtime, allowing independent path branches to run concurrently and delivering scalable performance.

Cypher 25 introduces now three major advances:

  • Stateful traversal with allReduce: Aggregate using traversal state (e.g., time, energy, cost), inlined and applied during path expansion for early path pruning.
  • Repeatable elements: A traversal can now revisit nodes or relationships, supporting cyclic traversals like charging loops.
  • Conditional queries: Enable branching logic directly in Cypher, integrating procedural decision-making into declarative queries.

These features transform Cypher into a graph reasoning language, expressing stateful decisions through patterns alone.

Use Case: EV Routing

Imagine a graph where (:Geo) nodes represent intersections, cities, or charging stations. Some (:Geo) nodes are also labeled (:ChargingStation). Connections include:

  • :ROAD relationships between :Geo nodes, with properties like distance_km, speed_limit_kph, and hourly_expected_speed_kph (a list of 24 hourly expected mean speed assuming a 24-hour wrap-around for simplicity)
  • :CHARGE self-loops on :ChargingStation nodes, with power_kw and time_in_minutes. In the examples dataset, a charging station has two loops L15 and L30 of 15 and 30 minutes. To charge 75 minutes at station cs, you need to match (cs:ChargingStation)-[L30]->(cs)-[L30]->(cs)-[L15]->(cs).
  • A (:Car) node with battery_capacity_kwh, efficiency_kwh_per_km, and current_soc_percent.
Simple data model

The goal: Find a route from source to target that respects time and energy constraints, and minimizes energy use — all declaratively.

The Cypher 25 Query

Here’s the query, broken down for clarity:

  • Match a QPP
  • Compute the current state and prune at each traversal hop
  • Score, order and select matches

First, let’s sketch the structure of the query. I encourage you to actually read the pseudo-code!

// MATCH A QUANTIFIED PATH PATTERN

// Until Cypher 25 is set as the database default (which I encourage),
// Cypher version 25 needs to be specified.
CYPHER 25 runtime=parallel

// Match the vehicle
MATCH (c:Car {id: $car_id})
// Define the path with REPEATABLE ELEMENTS
MATCH REPEATABLE ELEMENTS p = (a:Geo {name: $source_geo_name})
  (() -[rels:ROAD|CHARGE]- (x:Geo
     // Reduce result space by finding paths going
     // from source to destination without deviating
     // too much.
     // Tools to use: QPPs, geospatial features.
     // ...
  )){1,12}
  (b:Geo {name: $target_geo_name})

// COMPUTE CURRENT STATE AND PRUNE

// Evaluate each potential solution by calculating
// the trip state at each step (battery charge and time)
// and filtering out invalid states. At each step, ensure
// sufficient battery and that the trip duration is within
// the maximum allowed. Discard trips as soon as they fail
// to meet these constraints. Tool to use: allReduce()
WHERE allReduce(
  // initial state
  current = // Initialize state (state of charge and time)
  r IN rels |  // Accumulate per relationship at traversal time
    CASE
      WHEN r:ROAD
        THEN // state of charge goes down, time runs (according to expected speed)
          ...
      WHEN r:CHARGE
        THEN // state of charge goes up, time runs
          ...
    END,
    // Prune all paths where state of charge or time are not valid
    // example: SOC drops below min or time exceeds max.
    ..
  )
// Return for next stage
RETURN c, p

NEXT // SCORE, ORDER AND SELECT

// At this point, we have possible solutions that meet
// the requirements. We are interested in the best solution only,
// so we need to score solutions and pick the best ones

// Score and order paths
RETURN c, p, 
// Compute trip duration and energy consumed with reduce()
  ...
  AS final_values
ORDER BY final_values.time_in_min ASC,
         final_values.energy_kwh ASC,
         size(relationships(p)) ASC
LIMIT 1

Now, let’s fill in the blank with the actual implementation:

// MATCH A QUANTIFIED PATH PATTERN

// Specify Cypher version and runtime
CYPHER 25 runtime=parallel
MATCH (c:Car {id: $car_id})
// Define the path with repeatable elements
MATCH REPEATABLE ELEMENTS p = (a:Geo {name: $source_geo_name})
  (() -[rels:ROAD|CHARGE]- (x:Geo
     // Spatial pruning to avoid excessive detours
     WHERE point.distance(x.geo, b.geo) < $detour_ratio * point.distance(a.geo, b.geo)
     AND point.distance(x.geo, a.geo) < $detour_ratio * point.distance(a.geo, b.geo)
  )){1,12}
  (b:Geo {name: $target_geo_name})


// COMPUTE CURRENT STATE AND PRUNE

// Apply stateful pruning with allReduce
WHERE allReduce(
  // initial state
  current = {soc: c.current_soc_percent, time_in_min: 0.0},  // Initialize state
  r IN rels |  // Accumulate per relationship at traversal time
    CASE
      WHEN r:ROAD
        // state of charge goes down, time runs (according to expected speed)
        THEN {soc: current.soc - (r.distance_km*c.efficiency_kwh_per_km*100) / c.battery_capacity_kwh,
            time_in_min: current.time_in_min
                        + 60.0 *(r.distance_km / r.hourly_expected_speed_kph[
                ($departure_datetime+duration({minutes:current.time_in_min})).hour
                                  ]) }

      WHEN r:CHARGE
        // state of charge goes up, time runs
        THEN {soc: current.soc + (r.power_kw*(r.time_in_minutes/60.0)*100) / c.battery_capacity_kwh,
            time_in_min: current.time_in_min + r.time_in_minutes }
    END,
  // Prune if constraints are violated
  $min_soc <= current.soc <= $max_soc
    AND current.time_in_min <= $max_mins
  )
// Return for next stage
RETURN c, p

// SCORE, ORDER AND SELECT

NEXT

// Score and order paths
RETURN c, p, reduce(current = {soc: c.current_soc_percent, time_in_min: 0.0, energy_kwh: 0.0},
  r IN relationships(p) | CASE
    WHEN r:ROAD
      THEN {soc: current.soc - (r.distance_km*c.efficiency_kwh_per_km*100) / c.battery_capacity_kwh,
          time_in_min: current.time_in_min
                        + 60.0 *(r.distance_km / r.hourly_expected_speed_kph[
                ($departure_datetime+duration({minutes:current.time_in_min})).hour
                                  ]),
          energy_kwh: current.energy_kwh + (r.distance_km * c.efficiency_kwh_per_km)}
    WHEN r:CHARGE
      THEN {soc: current.soc + (r.power_kw*(r.time_in_minutes/60.0)*100) / c.battery_capacity_kwh,
          time_in_min: current.time_in_min + r.time_in_minutes,
          energy_kwh: current.energy_kwh}
  END) AS final_values

ORDER BY final_values.time_in_min ASC,
         final_values.energy_kwh ASC,
         size(relationships(p)) ASC
LIMIT 1

Let’s run the query on this dataset. Here’s an example of parameters:

A possible list of parameters
:params {
  max_mins: 700,
  car_id: "Car6",
  source_geo_name: "Paris",
  target_geo_name: "Marseille",
  detour_ratio: 1.2,
  min_soc: 1,
  max_soc: 100,
  departure_datetime: datetime("2025-10-15T17:46:16.114000000Z")
}
From Paris to Marseille, with a 5-minute charging stop at the 150 kW charging station
From Le Havre to Nice with Car 7: a 20-minute charging stop at the 150 kW charging station (20=15+5)
From Le Havre to Nice with Car 6: two charging stops

How it Works

1️⃣ QPP — Declarative traversal: The {1,12} QPP bounds depth while pruning infeasible branches early, combined with WHERE clauses and predicates for precise graph exploration.

2️⃣ Spatial pre-pruning with $detour_ratio: This clause, leveraging a POINT index, keeps paths near the direct line (e.g., $detour_ratio = 1.2 allows 20-percent deviation), focusing on relevant chargers.

Spatial pruning to avoid excessive detours

3️⃣ REPEATABLE ELEMENTS for charging loops: Allows node revisits for recharging, enabling declarative loops without procedural code.

4️⃣ allReduce — Stateful filtering: Accumulates state (SOC, time, blacklists) and prunes violations on the fly, enabling the user to specify terminating conditions that could only be done efficiently using the Traversal API.

Writing the same query without allReduce leads to a huge post-filtering workload (10-1000x query time)

5️⃣ Parallel runtime: Independent path segments are processed concurrently, enabling fast execution even for deep traversals.

6️⃣ NEXT — Chaining queries: Chains blocks into one plan: first for pruning, second for scoring. Variables pass seamlessly, optimizing execution without re-traversal.

Why it Matters

Cypher 5 turned traversal declarative with QPP and parallel execution. Cypher 25 adds state-aware pruning, repeatable cycles, and chaining, enabling Cypher to express not just patterns, but full reasoning and simulation.

Optimizing Further: Graph Refactor and Advanced Pruning

To enhance the graph for more efficient querying, especially in directed scenarios, we can refactor the road relationships to ensure explicit bidirectionality. This is done by adding reverse relationships where they don’t exist, copying properties from the original:

MATCH (a)-[r:ROAD]->(b)
MERGE (b)-[rev_r:ROAD]->(a)
SET rev_r += r{.*}

With this refactor, roads are now fully bidirectional (though modeled as directed edges in both directions), allowing for more flexible traversal while maintaining directionality if needed.

This enables an improved query that incorporates advanced heuristic pruning to cut cycles and eliminate 4-hop segments that don’t bring you closer to the target. By tracking the last four distances to the target in the state (previous_dists) and ensuring progress (state.previous_dists[0] ≥ state.previous_dists[-1]), we prune paths that aren’t making headway. Additionally, we track roads_taken to prevent reusing the same road in the same direction, avoiding cycles.

The pruning is so effective that we can set an extremely high upper bound of 1 million hops on the path length without performance issues. Here’s the updated query:

CYPHER 25 runtime=parallel
MATCH (c:Car {id: $car_id})
MATCH (a:Geo {name: $source_geo_name})
MATCH (b:Geo {name: $target_geo_name})
WITH c, a, b, a AS source, b AS target
MATCH REPEATABLE ELEMENTS p = (source)
  (() -[rels:ROAD|CHARGE]-> (x:Geo
     WHERE point.distance(x.geo, b.geo) < $detour_ratio * point.distance(a.geo, b.geo)
     AND point.distance(x.geo, a.geo) < $detour_ratio * point.distance(a.geo, b.geo)
  )){1,1000000}
  (target)
WHERE allReduce(
   state = {
              soc: c.current_soc_percent,
              time_in_min: 0.0,
              // ⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎
              previous_dists: [ 3_000_000_000,
                              2_000_000_000,
                              1_000_000_000,
                              point.distance(a.geo, b.geo)],
              roads_taken: []
              // ⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎
            },
   r IN rels|
    CASE
      WHEN r:ROAD
        THEN {
                soc: state.soc - (r.distance_km*c.efficiency_kwh_per_km*100) / c.battery_capacity_kwh,
                time_in_min: state.time_in_min
                + 60.0 *(r.distance_km / r.hourly_expected_speed_kph[
        ($departure_datetime+duration({minutes:state.time_in_min})).hour
                          ]),
                // ⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎
                previous_dists: state.previous_dists[1..]+[point.distance(endNode(r).geo, b.geo)],
                roads_taken: state.roads_taken + [elementId(r)]
                // ⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎
              }

      WHEN r:CHARGE
        THEN {
                soc: state.soc + (r.power_kw*(r.time_in_minutes/60.0)*100) / c.battery_capacity_kwh,
                time_in_min: state.time_in_min + r.time_in_minutes,
                // ⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎
                previous_dists: state.previous_dists,
                roads_taken: state.roads_taken
                // ⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎
              }
    END,
    $min_soc <= state.soc <= $max_soc
    AND state.time_in_min <= $max_mins
    // ⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎⬇︎
    AND state.previous_dists[0] >= state.previous_dists[-1]
    AND NOT state.roads_taken[-1] IN state.roads_taken[..-1]
    // ⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎⬆︎
  )
RETURN c, p
NEXT
RETURN c, p, reduce(state = {soc: c.current_soc_percent, time_in_min: 0.0, energy_kwh: 0.0},
  r IN relationships(p) | CASE
    WHEN r:ROAD
      THEN {soc: state.soc - (r.distance_km*c.efficiency_kwh_per_km*100) / c.battery_capacity_kwh,
          time_in_min: state.time_in_min
                        + 60.0 *(r.distance_km / r.hourly_expected_speed_kph[
                ($departure_datetime+duration({minutes:state.time_in_min})).hour
                                  ]),
          energy_kwh: state.energy_kwh + (r.distance_km * c.efficiency_kwh_per_km)}
    WHEN r:CHARGE
      THEN {soc: state.soc + (r.power_kw*(r.time_in_minutes/60.0)*100) / c.battery_capacity_kwh,
          time_in_min: state.time_in_min + r.time_in_minutes,
          energy_kwh: state.energy_kwh}
  END) AS final_values
ORDER BY final_values.time_in_min ASC,
         final_values.energy_kwh ASC,
         size(relationships(p)) ASC
LIMIT 1

This version yields even better performance: for the Le Havre to Nice route with Car 6, the query executes in a stunning 79 ms on a 24CPU/128GB RAM Neo4j Aura Business Critical instance, showcasing the power of Cypher 25’s stateful pruning in handling complex, real-world graph traversals declaratively.

Pruning leads to 79 ms on a 24CPU/128GB RAM

Summary

Cypher 25 extends Neo4j’s declarative graph model into the domain of reasoning and optimization. With QPP for bounded traversal, allReduce for state-driven pruning, REPEATABLE ELEMENTS for round trips, conditional subqueries for logic, and parallel runtime for speed, you can handle route planning, logistics, dynamic simulations, and much more entirely in Cypher.

It’s time to go Cypher-first — refactor old APOC or Java traversals, set Cypher 25 as your default, and experiment in Neo4j Aura.

Resources

⚡ Declarative Route Planning with Cypher 25 — Graph Traversal Grows Up was originally published in Neo4j Developer Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Share Article

Explore

Solve Hard Graph Problems With Cypher 25


7 min read