在 cypher/traversal API 中查找所有关系不相交的最长路径（按大小排序）

Question

我有一个要实现的算法，它可以找到图中最长的 path/s。然后找到下一个最长的 path/s 与前一个 path/s 没有任何共同关系，依此类推，直到整个图表示为不相交的路径。它们在它们包含的关系方面是不相交的，但在它们连接的地方会有重叠的节点。我希望这些关系不相交的路径中的每一个都从最大到最小排序。

我想知道是否有人可以指导我如何使用 Cypher 或 Traversal API 来完成此操作。速度会更好，但如果 Cypher 和遍历之间没有太大区别 API 我宁愿使用一个漂亮的 Cypher 表达式。

我可以想象找到最大的 path/s，移除 it/them，然后搜索下一个最大的 path/s，但这根本不理想。

Answer 1

我认为你可以做到，但我认为这不一定是个好主意，尤其是在大图中。我想如果你要给它一个起点；限制您匹配的关系数量（即从已知的长长度范围开始）；并限制你 return 的路径数量，然后它可能可以分块进行。但我认为在大图中对最长路径的开放式无约束搜索可能永远不会 return 成功。

但是，这是一个有趣的问题和测试，你可以用 cypher 做什么，所以我试了一下，这就是我想出的。

我创建了一些测试数据来使用。

create (n1:Node {name: 'A'})
create (n2:Node {name: 'B'})
create (n3:Node {name: 'C'})
create (n4:Node {name: 'D'})
create (n5:Node {name: 'E'})
create (n6:Node {name: 'F'})
create (n7:Node {name: 'G'})
create (n1)-[:NEXT {touched: false}]->(n2)
create (n2)-[:NEXT {touched: false}]->(n3)
create (n3)-[:NEXT {touched: false}]->(n4)
create (n5)-[:NEXT {touched: false}]->(n3)
create (n4)-[:NEXT {touched: false}]->(n6)
create (n7)-[:NEXT {touched: false}]->(n4)
return *

这是加载时的样子。对于每个属性，我都添加了一个名为 touched 的标志，我可以在匹配时对其进行测试，如果它已被使用，则更改为 true。

我决定在图中有向关系的约束下进行操作。

// start by matching all of the directed paths in the graph
// where all the relationships in the path have a touched
// property of 'false'
// order those paths by length in descending order 
// and stick them in a collection
match p=(:Node)-[:NEXT* {touched: false}]->(:Node)
with p
order by length(p) desc
with collect(p) as all_paths
with all_paths

// unwind the collection of paths
// that are organized longest to shortest
// isolate the first node and end node of each path 
unwind all_paths as curr_path
with curr_path
, nodes(curr_path)[0] as a
, nodes(curr_path)[length(curr_path)] as b

// re-match the path from a to b to see if it is still good
// and a realtioship has not been used in an earlier matched
// path
optional match test_path=(a)-[:NEXT* {touched: false}]->(b)
with curr_path
, test_path

// if the first node and last node are the same and all
// of the nodes in one are in the other then i am assuming they
// are the same. to be safe, i could have added a length comparison
// too or done the reverse lookup of test_path in curr_path 
, case 
    when all(n in nodes(curr_path) 
      where n in nodes(test_path)) then [1]
    else []
  end as equal

// if the original path match, curr_path, matches 
// test_path then set all of the flags ont he relationships to
// 'true' so these relationships will not be used again
foreach (n in equal |
  foreach (r in relationships(curr_path) |
    set r.touched = true))

// filter out the paths that do not match
// on the subsequent test and return only those that do
with curr_path, test_path, equal
, case when length(equal) = 1 then curr_path
  end as path
with collect (path) as disparate_paths
return disparate_paths

这return的三个路径：

A-->B-->C-->D-->F
E-->C
G-->D

在 cypher/traversal API 中查找所有关系不相交的最长路径（按大小排序）

Find all relationship disjoint longest paths in cypher/traversal API ordered by size

neo4j

cypher