如何通过 Cypher（图与正则表达式）（高效）查找递归树中的子路径

Question

我正在尝试通过 Cypher 在 Neo4j 中重现 Go SGF 游戏树，以便我可以通过图形进行模式搜索。这是围棋游戏树的形状 — 基于 Sabaki 的 SGF 解析器 —:

type GameTree = {
  id: number;
  data: { [key: string]: string[] };
  parentId: number | null;
  children: GameTree[];
};

您可以在此提交中找到问题的可重现示例。

到目前为止，我已经成功地对其进行了建模，就像它出现在 Go 编辑器的游戏树中一样：

B

和

W

表示黑白移动。

AB

和

AW

是“添加黑色或白色棋子”，用于编辑棋盘位置时。就这个问题而言，实际上只有

move

重要，它与

B

或

W

具有相同的值。棋盘坐标以 2 个字母给出，例如列

m

和行

r

给出字符串

'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

但我真的不知道这种类型的模式搜索通过 Neo4j 或其他图形数据库是否足够有效。我认为可能是因为，尽管大多数游戏都有 200 多个移动分支，但通常数量并不多。并且分析将在顺序很重要（不跳过）的单向分支上进行，因此它可能会进一步限制搜索空间。

或者，我正在考虑在每个移动节点中放置一个带有完整路径的字符串。这样我就可以使用正则表达式（我知道正则表达式也可以建模为图形）而不是路径搜索。也就是说，如果它有效，那么我认为使用 SQL 数据库可能就足够了。然而，我可能仍然会坚持使用 Neo4j，因为将其建模为图形可以在将来提供更多有用的功能。

---

参考文献

• Stack Overflow - Neo4j 如何匹配子路径
• Stack Overlflow - 在 Neo4J 中使用 cypher 匹配子树的有效方法？

Answer 1

要获取从根

p

到并包括移动序列

GameNode

的路径

['rm','ro']

，您可以在Neo4j 5.9+中编写以下内容：

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)
WHERE m1.move = 'rm' AND m2.move = 'ro'
  AND NOT EXISTS { (m2)-[:NEXT_MOVE]->(:MoveNode) }
RETURN p

如果存在性能问题，那将是令人惊讶的：代表每个游戏的小图表上足够具体的模式不应该很慢。