计算密码中的总路径成本,考虑关系方向性

Question

在neo4j上使用cypher查询,在有向循环图中,我需要BFS查询和每个深度级别的目标节点排序.

对于深度排序,应使用自定义的"总路径成本函数",基于此计算

• r.followrank开始和结束节点之间的所有关系属性.
• 关系方向性(如果它指向终点节点,则为followrank,否则为0)

在任何搜索深度级别n,连接到高级别节点的节点的级别n-m, m>0应该高于连接到级别低级别节点的节点n-m.反向方向性应该导致0级(这意味着节点及其子树仍然是排名的一部分).

我正在使用neo4j社区-19.9.M01.到目前为止,我采用的方法是为每个终端节点的最短路径提取一系列followranks

我认为我已经为这个查询提出了一个很好的第一个想法,但它似乎在多个点上分解.

我的查询是:

START strt=node(7)
MATCH p=strt-[*1..]-tgt
WHERE not(tgt=strt)
RETURN ID(tgt), extract(r in rels(p): r.followrank*length(strt-[*0..]-()-[r]->() )) as rank, extract(n in nodes(p): ID(n));

哪个输出

==> +-----------------------------------------------------------------+
==> | ID(tgt) | rank                  | extract(n in nodes(p): ID(n)) |
==> +-----------------------------------------------------------------+
==> | 14      | [1.0]                 | [7,14]                        |
==> | 15      | [1.0,1.0]             | [7,14,15]                     |
==> | 11      | [1.0,1.0,1.0]         | [7,14,15,11]                  |
==> | 8       | [1.0,1.0,1.0,1.0,0.0] | [7,14,15,11,7,8]              |
==> | 9       | [1.0,1.0,1.0,1.0,0.0] | [7,14,15,11,7,9]              |
==> | 10      | [1.0,1.0,1.0,1.0,0.0] | [7,14,15,11,7,10]             |
==> | 12      | [1.0,1.0,1.0,0.0]     | [7,14,15,11,12]               |
==> | 8       | [0.0]                 | [7,8]                         |
==> | 9       | [0.0]                 | [7,9]                         |
==> | 10      | [0.0]                 | [7,10]                        |
==> | 11      | [1.0]                 | [7,11]                        |
==> | 15      | [1.0,1.0]             | [7,11,15]                     |
==> | 14      | [1.0,1.0,1.0]         | [7,11,15,14]                  |
==> | 8       | [1.0,1.0,1.0,1.0,0.0] | [7,11,15,14,7,8]              |
==> | 9       | [1.0,1.0,1.0,1.0,0.0] | [7,11,15,14,7,9]              |
==> | 10      | [1.0,1.0,1.0,1.0,0.0] | [7,11,15,14,7,10]             |
==> | 12      | [1.0,0.0]             | [7,11,12]                     |
==> +-----------------------------------------------------------------+
==> 17 rows
==> 38 ms

它看起来与我需要的类似,但问题是

1. 节点8,9,10,11具有与7相同的关系方向!反向查询结果...*length(strt-[*0..]-()-[r]->() )...看起来更奇怪 - 请参阅下面的查询.
2. 我不知道如何将length()表达式的结果标准化为1.

方向性:

START strt=node(7)
MATCH strt<-[r]-m
RETURN ID(m), r.followrank;
==> +----------------------+
==> | ID(m) | r.followrank |
==> +----------------------+
==> | 8     | 1            |
==> | 9     | 1            |
==> | 10    | 1            |
==> | 11    | 1            |
==> +----------------------+
==> 4 rows
==> 0 ms
START strt=node(7)
MATCH strt-[r]->m
RETURN ID(m), r.followrank;
==> +----------------------+
==> | ID(m) | r.followrank |
==> +----------------------+
==> | 14    | 1            |
==> +----------------------+
==> 1 row
==> 0 ms

反向查询:

START strt=node(7)
MATCH p=strt-[*1..]-tgt
WHERE not(tgt=strt)
RETURN ID(tgt), extract(rr in rels(p): rr.followrank*length(strt-[*0..]-()<-[rr]-() )) as rank, extract(n in nodes(p): ID(n));
==> +-----------------------------------------------------------------+
==> | ID(tgt) | rank                  | extract(n in nodes(p): ID(n)) |
==> +-----------------------------------------------------------------+
==> | 14      | [1.0]                 | [7,14]                        |
==> | 15      | [1.0,1.0]             | [7,14,15]                     |
==> | 11      | [1.0,1.0,1.0]         | [7,14,15,11]                  |
==> | 8       | [1.0,1.0,1.0,1.0,3.0] | [7,14,15,11,7,8]              |
==> | 9       | [1.0,1.0,1.0,1.0,3.0] | [7,14,15,11,7,9]              |
==> | 10      | [1.0,1.0,1.0,1.0,3.0] | [7,14,15,11,7,10]             |
==> | 12      | [1.0,1.0,1.0,2.0]     | [7,14,15,11,12]               |
==> | 8       | [3.0]                 | [7,8]                         |
==> | 9       | [3.0]                 | [7,9]                         |
==> | 10      | [3.0]                 | [7,10]                        |
==> | 11      | [1.0]                 | [7,11]                        |
==> | 15      | [1.0,1.0]             | [7,11,15]                     |
==> | 14      | [1.0,1.0,1.0]         | [7,11,15,14]                  |
==> | 8       | [1.0,1.0,1.0,1.0,3.0] | [7,11,15,14,7,8]              |
==> | 9       | [1.0,1.0,1.0,1.0,3.0] | [7,11,15,14,7,9]              |
==> | 10      | [1.0,1.0,1.0,1.0,3.0] | [7,11,15,14,7,10]             |
==> | 12      | [1.0,2.0]             | [7,11,12]                     |
==> +-----------------------------------------------------------------+
==> 17 rows
==> 30 ms

所以我的问题是:

1. 这个查询发生了什么？
2. 有工作方法吗？

有关其他详细信息,我知道min(长度(路径))聚合器,但在这种情况下它不起作用,我正在尝试提取有关最佳命中的信息 - 我返回的关于最佳命中的附加信息将会分解结果再次 - 我认为这是一个密码限制.

Answer 1

基本上，您只想考虑“与路径流”的关系来进行排名。不幸的是，要测试“路径流”，您需要检查每个关系的起始/结束节点的路径索引，而这目前只能通过 APOC 来完成。

// allshortestpaths to get all non-cyclic paths
MATCH path=allshortestpaths((a{id:"1"})-[*]-(b{id:"2"}))

// Find rank worthy relationships
WITH path, filter(rl in relationships(path) WHERE apoc.coll.indexOf(path, startnode(rl))<apoc.coll.indexOf(path, endnode(rl)))) as comply

// Filter results
RETURN path, REDUCE(rk = 0, rl in comply | rk+rl.followrank) as rank
ORDER BY rank DESC

（我无法测试 APOC 部分，因此您可能必须传递 NODES(path) 而不是 APOC 过程的路径）