Geek Answers Handbook

Stop the intersection of Cypher when the condition on reduce () can no longer be satisfied

Suppose I have a neo4j database with one node type and one relationship type so that everything is simple. All relations have the property of "value" (as in the classical problems of the graph), the values ​​of which are non-negative.

Suppose now that I want to find all possible paths between a node with identifier A and node with identifier B with an upper bound on the path length (for example, 10), so that the total cost of the path is lower or equal to a given constant (for example, 20).

The Cypher code for this is as follows (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 request is that you should not take into account the fact that the costs are non-negative and, therefore, the ways in which the total cost limit is passed can be cut off. Instead, it lists all possible paths of lengths from 0 to 10 between nodes A and B (which can be ridiculously expensive), calculates the total costs, and then filters out paths that exceed the limit. Reducing time will result in significant performance improvements.

I know that this can be accomplished with a workaround scheme using BranchStates and preventing expansion when necessary, but I would like to find a solution to Cypher (mainly because of the reasons that have been exposed here ).

I am currently using version 2.2.2 if that matters.

+4
1

?

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

, , !

, , Cypher ,

0

More articles:


All Articles