如何计算跳数在 (1,5) (neo4j) 范围内的两个节点之间的路径？

Question

我试图找到两个节点之间的所有可能路径。我使用了很少的密码查询来完成所需的工作，但是如果跃点增加，它会花费很多时间。这是查询

match p = (n{name:"Node1"})-[:Route*1..5]-(b{name:"Node2"}) return p

此外，如果我使用 shortestpath，如果找到具有最小跳数的路径，它会限制结果。因此，如果在节点之间发现直接连接（1 跳），我不会获得 2 跳或多于 2 跳的结果。

match p = shortestpath((n{name:"Node1"})-[:Route*1..5]-(b{name:"Node2"})) return p

如果我将跳数增加到 2 或更多，它会抛出异常。

shortestPath(...) does not support a minimal length different from 0 or 1

是否有任何其他替代框架或算法以最短时间获取所有路径？

P.S。我正在寻找 ms 顺序的东西。目前，所有跳数大于 3 的查询都需要几秒钟才能完成。

Answer 1

根据您的描述，我假设您希望根据某些权重获得最短路径，例如 :Route 关系上的 duration 属性。

如果这是真的，在 cypher 中使用 shortestPath 没有帮助，因为它只考虑了跳数。 Cypher 中尚未以有效的方式提供加权最短路径。

Java API 通过 dijekstra 或 astar 通过 GraphAlgoFactory class. For the simple case that your cost function is just the value of a relationship property (as mentioned above) you can also use an existing REST endpoint 支持加权最短路径。

Answer 2

我了解到您正在尝试加快涉及可变长度路径的原始查询。 shortestpath 函数不适合您的查询，因为它确实试图找到最短路径——而不是 all 路径一定长度。

您的原始查询（使用示例数据）的执行计划如下所示：

+-----------------------+----------------+------+---------+-------------------+---------------------------------------------+
| Operator              | Estimated Rows | Rows | DB Hits | Identifiers       | Other                                       |
+-----------------------+----------------+------+---------+-------------------+---------------------------------------------+
| +ProduceResults       |              0 |    1 |       0 | p                 | p                                           |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +Projection           |              0 |    1 |       0 | anon[30], b, n, p | ProjectedPath(Set(anon[30], n),) |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +Filter               |              0 |    1 |       2 | anon[30], b, n    | n.name == {  AUTOSTRING0}                   |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +VarLengthExpand(All) |              0 |    2 |       7 | anon[30], b, n    | (b)<-[:Route*]-(n)                          |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +Filter               |              0 |    1 |       3 | b                 | b.name == {  AUTOSTRING1}                   |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +AllNodesScan         |              3 |    3 |       4 | b                 |                                             |
+-----------------------+----------------+------+---------+-------------------+---------------------------------------------+

因此，您的原始查询正在扫描 每个节点 以查找与 b 模式匹配的节点。然后，它扩展 all 个从 b 开始的可变长度路径。然后它过滤这些路径以找到以与 n.

的模式匹配的节点结尾的路径

这里有一些可以加快查询速度的建议，但您必须在数据上对其进行测试以查看速度：

给每个节点一个标签。例如，Foo.
创建一个索引可以加快搜索您的端节点。例如：
```
CREATE INDEX ON :Foo(name);
```

修改您的查询以强制在两端节点上使用索引。例如：

MATCH p =(n:Foo { name:"Node1" })-[:Route*1..5]-(b:Foo { name:"Node2" })
USING INDEX n:Foo(name)
USING INDEX b:Foo(name)
RETURN p;

经过以上改动后，执行计划为：

+-----------------+------+---------+-----------------------------+-----------------------------+
| Operator        | Rows | DB Hits | Identifiers                 | Other                       |
+-----------------+------+---------+-----------------------------+-----------------------------+
| +ColumnFilter   |    1 |       0 | p                           | keep columns p              |
| |               +------+---------+-----------------------------+-----------------------------+
| +ExtractPath    |    1 |       0 | anon[33], anon[34], b, n, p |                             |
| |               +------+---------+-----------------------------+-----------------------------+
| +PatternMatcher |    1 |       3 | anon[33], anon[34], b, n    |                             |
| |               +------+---------+-----------------------------+-----------------------------+
| +SchemaIndex    |    1 |       2 | b, n                        | {  AUTOSTRING1}; :Foo(name) |
| |               +------+---------+-----------------------------+-----------------------------+
| +SchemaIndex    |    1 |       2 | n                           | {  AUTOSTRING0}; :Foo(name) |
+-----------------+------+---------+-----------------------------+-----------------------------+

此查询计划使用索引直接获取 b 和 n 节点 -- 无需扫描。这本身应该可以提高速度。然后该计划使用 "PatternMatcher" 来查找这些端节点之间的可变长度路径。您将不得不尝试此查询以查看 "PatternMatcher" 执行此操作的效率。

如何计算跳数在 (1,5) (neo4j) 范围内的两个节点之间的路径？

How can I calculate the path between two nodes with hops in range (1,5) (neo4j) ?

shortest-path

neo4j

cypher