提问人：Philippe Fanaro 提问时间：11/17/2023 最后编辑：Philippe Fanaro 更新时间：11/18/2023 访问量：72
如何（有效地）通过Cypher在递归树中查找子路径（Graph vs Regex）
How to (Efficiently) Find Subpaths in Recursive Trees through Cypher (Graph vs Regex)
问：
我正在尝试通过 Cypher 在 Neo4j 中重现一个 Go SGF 游戏树，这样我就可以以图形的形式进行模式搜索。这是基于 Sabaki 的 SGF 解析器的 Go 游戏树的形状：
type GameTree = {
id: number;
data: { [key: string]: string[] };
parentId: number | null;
children: GameTree[];
};
您可以在此提交中找到问题的可重现示例。
到目前为止，我已经成功地对它进行了建模，就像它在 Go 编辑器的游戏树中一样：
B和卑鄙的黑白动作。 并且是“添加的黑色或白色石头”，用于编辑棋盘位置时。就此问题而言，只有实际问题，它与 或 具有相同的值。电路板坐标以 2 个字母给出，例如列和行给出字符串。WABAWmoveBWmr'rm'
现在，我想做的是，如果找到指定的子路径（无跳过），则从根返回完整路径（实际上可能根节点就足够了）。到目前为止，我有这个，它确实有效：
MATCH p=(g:GameNode)-[:NEXT_MOVE*]->()
WITH g, p,
[m in TAIL(NODES(p)) | m.move] AS moves
WITH g, p,
REDUCE(path = '', move in moves | path + move) AS joined_moves
WHERE joined_moves CONTAINS "rmro"
RETURN g, p, joined_moves
按照 @cybersam 的回答，我认为这可以使它对 Neo4j 更加明确，因此它使用 - 例如 —:m.moveCREATE INDEX move_node_move_idx FOR (m:MoveNode) ON (m.move)
MATCH p=(g:GameNode)-[:NEXT_MOVE*]->(m1:MoveNode)-[:NEXT_MOVE*]->()
WHERE m1.move = HEAD(['rm', 'ro'])
WITH g, p,
[m in TAIL(NODES(p)) | m.move] AS moves
WITH g, p,
REDUCE(path = '', move in moves | path + move) AS joined_moves
WHERE joined_moves CONTAINS "rmro"
RETURN g, p, joined_moves
但我真的不知道这种类型的模式搜索是否足够有效，通过 Neo4j 或其他图形数据库。我认为可能是因为，尽管大多数游戏都有 200+ 移动分支，但通常没有那么多。并且分析将在顺序很重要的单向分支上进行（没有跳过），因此它可能应该进一步限制搜索空间。
或者，我正在考虑在每个移动节点中放置一个字符串，其中包含它的完整路径。这样我就可以使用正则表达式（我知道正则表达式也可以建模为图形）而不是路径搜索。也就是说，如果它有效，那么我认为使用 SQL 数据库可能就足够了。但是，我可能仍然会坚持使用 Neo4j，因为将其建模为图形可以在未来提供更多有用的功能。
引用
答：
1赞
Finbar Good
11/17/2023
#1
要获取从根目录到移动序列的路径，您可以在 Neo4j 5.9+ 中编写以下内容：pGameNode['rm','ro']
MATCH p = (g:GameNode)-[:NEXT_MOVE]->+(m1:MoveNode)-[:NEXT_MOVE]->(m2:MoveNode)
WHERE m1.move = 'rm' AND m2.move = 'ro'
RETURN p
要获取整个路径，直到序列中的最后一个移动，您需要添加一个检查，以确保没有进一步的移动：
MATCH p = (g:GameNode)-[:NEXT_MOVE]->+(m1:MoveNode)-[:NEXT_MOVE]->
(m2:MoveNode)-[:NEXT_MOVE]->*(lastMove:MoveNode)
WHERE m1.move = 'rm' AND m2.move = 'ro'
AND NOT EXISTS { (lastMove)-[:NEXT_MOVE]->(:MoveNode) }
RETURN p
如果存在性能问题，那将是令人惊讶的：代表每个游戏的小图形上足够具体的模式应该不会很慢。
评论
0赞
Philippe Fanaro
11/17/2023
问题是指定的子路径可能具有任意长度，因此我认为解决方案的编程性不够。WHERE ... AND
0赞
Philippe Fanaro
11/17/2023
你能详细说明一下操作员吗？我不知道它的存在。这是否等同或接近？->+-[:NEXT_MOVE*]->
1赞
Finbar Good
11/17/2023
第二个查询缺少可变长度的尾部。我已经添加了。我相信这解决了您的评论，即它不会匹配任意长度的子路径。
1赞
Finbar Good
11/17/2023
...并且与旧语法相同。它现在等同于克莱恩星，就像正则表达式一样。-[:NEXT_MOVE]->*-[:NEXT_MOVE*0..]->
1赞
cybersam
11/17/2023
#2
下面的查询在返回包含所需移动序列的每个游戏中的移动时应该具有相当的性能。它假设您：
- 有一个索引 ，
MoveNode.move - 在参数中传递所需移动的列表，
$moves - 将第一个变量长度关系的长度调整为小于 的长度 1。例如，如果有 2 个项目，请使用 代替 .诚然，这很丑陋，但Cypher不支持动态边界。
MATCH$moves$moves*1*2
查询
MATCH p1=(m1:MoveNode)-[:NEXT_MOVE*2]->(m2)
WHERE m1.move = HEAD($moves) AND [m IN TAIL(NODES(p1)) | m.move] = TAIL($moves)
MATCH p2 = (m2)-[:NEXT_MOVE*0..]->(end) WHERE NOT (end)-[:NEXT_MOVE]->()
MATCH p3 = (g:GameNode)-[:NEXT_MOVE*]->(m1)
RETURN [a IN NODES(p3)[1..-1] | a.move] + $moves + [b IN NODES(p2)[1..] | b.move]
索引用于通过快速查找节点（与 中的第一项匹配）来限制和锚定搜索，而不是遍历每个 .然后查询：m1MoveNode$movesGameNode
- 通过要求其后跟满足列表其余部分的子路径进行筛选，
m1$moves - 查找每个子路径之后的移动顺序，
- 从幸存的节点向后工作以找到相应的 s。
m1GameNode - 构造并返回每个匹配游戏的移动顺序。
因此，此查询首先使用索引查找第一组相关节点，并不断向已找到的内容添加关系（和结束节点），直到最终获得所需的结果。永远不需要扫描不相关的数据。
评论
0赞
Philippe Fanaro
11/17/2023
谢谢你的回答，@cybersam。事实上，我认为这更明确地解决了使用索引的问题。你认为我的解决方案会让 Neo4j 无法使用索引（就像许多 SQL DBMS 一样）吗？REDUCEm.move
0赞
Philippe Fanaro
11/17/2023
另外，您能否包括您提到的具体索引？是这样的：？moveCREATE INDEX move_node_move_idx FOR (m:MoveNode) ON (m.move)
0赞
Philippe Fanaro
11/17/2023
您是否设法让可重现的示例起作用？我正在 Neo4j Desktop 上尝试您的示例，将其替换为，但它似乎不起作用。$moves['rm', 'ro']
0赞
Philippe Fanaro
11/17/2023
（我已将您的索引想法添加到我的问题代码中。
1赞
cybersam
11/18/2023
我只是修复了我的语句以允许与 .这可能就是它对你不起作用的原因。p2m2end
评论