Cypher Query:在大图中查找最小和最大关系长度 [英] Cypher Query: Find minimum and maximum relationship length over a big graphs

问题描述

目标:找出两种节点类型之间的最小和最大关系长度.

Objective: Find the minimum and maximum relationship lengths between two Node Types.

示例:以下是节点类型T"的虚拟连接

Example: Following are the dummy connections for a Node type 'T'

• (Aplha)-->(Bravo)
• (Bravo)-->(Charlie)

所以到达两个节点​​的最小跳数为1(即Aplha直接链接到Charlie)，到达两个节点​​的最大跳数为2(即(Aplha)--(Beta)--(Charlie)).

So the minimum hops to reach two nodes is 1 (i.e. Aplha is directly linked to Charlie), and the maximum hops to reach two nodes is 2 (i.e. (Aplha)--(Beta)--(Charlie)).

密码查询我有:

MATCH (from:T), (to:T), p=shortestPath((from)-[*]-(to))
RETURN min(length(p)) as min, max(length(p)) as max

这适用于较小的数据集，但对于 2000 个节点是来自"，2000 个节点是到"，连接的级别类似于 min:5 和 max:10 hops，此查询需要 30 分钟才能运行.

Which works fine for smaller data-sets but for 2000 nodes is 'from' and 2000 nodes is 'to' connected with a level like min:5 and max:10 hops, this query takes like 30mins to run.

有没有什么方法可以更快的实现这个操作?

Is there any way to achieve this operations is a faster way?

我无法使用的解决方案:

• 限制关系长度:我必须使用(from)-[*]-(to)，不能限制为3或4级.

• Limit relationship length: I have to use (from)-[*]-(to), cannot limit it to 3 or 4 levels.

推荐答案

Minimum 很容易使用 APOC 的路径扩展程序(仅适用于 3.2.x 或 3.3.x 的 2018 年冬季最新版本).

Minimum is easy enough using APOC's path expander procedures (only the latest winter 2018 release for either 3.2.x or 3.3.x).

您可以使用一组作为起始节点，并使用标签过滤器中的 :T 标签作为终止标签(扩展路径的结尾)并添加一个限制:

You can use one group as your start nodes, and use the :T label in the label filter as the termination label (the end of the path for expansion) and add a limit:

MATCH (start:T)
WITH collect(start) as startNodes
CALL apoc.path.expandConfig(startNodes, {labelFilter:'/T', limit:1, minLevel:1, uniqueness:'NODE_GLOBAL'}) YIELD path
RETURN length(path) as min

我们正在使用 expandConfig() 和 NODE_GLOBAL 唯一性，这在扩展过程中非常有帮助，因为我们可以修剪(不需要考虑)任何以已经存在的节点结束的路径访问过.

We're using expandConfig() and NODE_GLOBAL uniqueness, which drastically helps out during expansion as we can prune (don't need to consider) any paths that end at a node that has already been visited.

路径扩展程序在您寻找具有特定标签的节点的路径时非常有用，请注意我们不需要匹配到末端节点并创建交叉产品，我们将在扩展过程中评估节点的标签，然后停止当到达带有 :T 标签的节点时.

The path expander procedures are great when you're looking for paths to nodes with certain labels, note that we don't need to match to end nodes and create cross products, we will evaluate labels of nodes during expansion, and stop when a node with the :T label is reached.

limit:1会在找到第一个结果时自动停止，并且扩展使用广度优先搜索，所以第一个匹配将是可能的最短路径.

The limit:1 will automatically stop when the first result is found, and the expansion uses breadth-first-search, so the first match will be the shortest path possible.

为了找到所有最短路径中的最长路径(从每个 :T 节点到最近的 :T 节点)，方法是类似的，但我们不会收集结果，因此该过程将对每个路径执行:T节点.

For finding the longest of ALL the shortest paths (from each :T node to just its nearest :T node), the approach will be similar, but we will not collect the results, so the procedure will execute for every single :T node.

MATCH (start:T)
CALL apoc.path.expandConfig(start, {labelFilter:'/T', limit:1, minLevel:1, uniqueness:'NODE_GLOBAL'}) YIELD path
RETURN max(length(path)) as maxShortest

然而，为了找到每两个 :T 节点之间的最长最短路径，性能可能会更差.

For finding the longest shortest-path between every two :T nodes, however, is likely to perform worse.

我们可以使用类似的方法，但我们将删除 LIMIT，并更改标签过滤器以使用 :T 作为结束节点(路径必须以 :T 节点结束，但可以扩展它们以找到通往其他节点的路径):T 节点)

We can use a similar approach, but we'll remove the LIMIT, and change the label filter to use :T as an end node (paths must end at :T nodes, but can expand past them to find paths to other :T nodes)

MATCH (start:T)
CALL apoc.path.expandConfig(start, {labelFilter:'>T', minLevel:1, uniqueness:'NODE_GLOBAL'}) YIELD path
RETURN max(length(path)) as maxShortestOfAllPairs

这篇关于Cypher Query:在大图中查找最小和最大关系长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！