neo4j - 当不再满足 reduce() 上的条件时停止 Cypher 遍历

Question

假设我有一个具有单一节点类型和单一关系类型的 neo4j 数据库，以保持简单。所有关系都有一个“成本”属性（如在经典图问题中），其值为非负数。

假设现在我想找到 ID A 的节点和 ID B 的节点之间的所有可能路径，路径长度的上限（例如 10）使得总路径成本低于或等于给定常数（例如 20） .

完成此操作的 Cypher 代码如下（并且有效）：

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

这个查询的问题是它没有利用成本是非负的这一事实，因此可以修剪通过总成本限制的路径。相反，它列出了节点 A 和 B 之间长度为 0 到 10 的所有可能路径（这可能非常昂贵），计算总成本，然后过滤掉超出限制的路径。及时修剪路径将导致巨大的性能改进。

我知道通过使用 BranchStates 并在相关时防止扩展，这对于遍历框架是可行的，但我想找到一个 Cypher 解决方案（主要是由于这里公开的原因）。

我目前使用的是 2.2.2 版，如果这很重要的话。

Answer 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，使用标签