在按大小排序的密码/遍历 API 中查找所有关系不相交的最长路径 [英] Find all relationship disjoint longest paths in cypher/traversal API ordered by size

问题描述

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

I have an algorithm that I want to implement that finds the longest path/s in a graph. Then finds the next longest path/s that do not have any relationships in common with the previous path/s and so forth until the entire graph is represented as disjoint paths. They are disjoint with respect to the relationships they contain but will have overlapping nodes where they connect. I want each of these relationship disjoint paths ordered from largest to smallest.

我想知道是否有人可以指导我如何使用 Cypher 或 Traversal API 执行此操作.速度会更可取，但如果 Cypher 和 Traversal API 之间没有太大区别，我宁愿使用漂亮的 Cypher 表达式.

I was wondering if anybody could give me pointers at how to do this with Cypher or the Traversal API. Speed would be preferable, but if there is not a big difference between Cypher and the Traversal API I'd rather go with a nice Cypher expression.

我可以想象找到最大的路径/s，删除它/它们，然后搜索下一个最大的路径/s，但这一点都不理想.

I can imagine finding the largest path/s, removing it/them, then searching for the next largest path/s but this is not ideal at all.

推荐答案

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

I think you can do it but i do not necessarily think it is a good idea particularly in a large graph. I think if you were to give it a starting point; limit the number of relationships you matched (i.e. start with known long length ranges); and limit the number of paths you return then it might be doable in chunks. But I think an open ended unconstrained search for the longest paths in a large graph would probably never return successfully.

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

But, it is and interesting question and test of what you can do with cypher so I gave it a shot and this is what I came up with.

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

I created a little test data to work with.

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.

This is what it looked like when loaded. For every property i added a flag called touched that i could test when matching and then change to true if it had been used.

我决定使用图中有向关系的约束进行操作.

I decided to operate with the constraint of directed relationships in the graph.

// 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

这将返回三个路径:

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

这篇关于在按大小排序的密码/遍历 API 中查找所有关系不相交的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！