Stop Cypher traversal when where condition on reduce() can no longer be satisfied

Question

Suppose I have a neo4j database with a single node type and a single relationship type to keep things simple. All relationships have a "cost" property (as in classical graph problems), whose values are non-negative.

Suppose now I want to find all the possible paths between node with ID A and node with ID B, with an upper bound on path length (e.g. 10) such that the total path cost is below or equal to a given constant (e.g. 20).

The Cypher code to accomplish this is the following (and it works):

START a = node(A), b = node(B)
MATCH (a) -[r*0..10]-> (b)
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
WHERE totalcost < 20
RETURN costs, totalcost

The problem with this query is that it doesn't take advange of the fact that costs are non-negative and thus paths where the total cost limit is passed can be pruned. Instead, it lists all possible paths of length 0 to 10 between nodes A and B (which can be ridiculously expensive), calculates total costs and then filters out paths that fall above the limit. Pruning paths in time would lead to massive performance improvements.

I know this is doable with the traversal framework by using BranchStates and preventing expansion when relevant, but I would like to find a Cypher solution (mainly due to the reasons exposed here).

I am currently using version 2.2.2, if that matters.

Answer 1

Would a sum of relationships costs before the extract be sufficient ?

START a = node(A), b = node(B)
MATCH (a)-[r*0..10]->(b)
WHERE sum(r.cost) < 20
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
RETURN costs, totalcost

By the way, wanting to prune is meaning you want imperative way !

Also, please help Cypher a bit, use labels