密码查询:查找大图上的最小和最大关系长度 [英] 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)

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

因此，到达两个节点​​的最小跳数为1(即Aplha与查理直接链接)，而到达两个节点​​的最大跳数为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个节点是'from'，而2000个节点是'to'，连接级别为min:5和max:10跳，则此查询的运行时间为 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 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

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