我试图通过Cypher在Neo4j中重现一个围棋SGF博弈树,这样我就可以通过模式搜索,作为一个图。这是一个围棋博弈树的形状-基于Sabaki's SGF Parser-:
type GameTree = {
id: number;
data: { [key: string]: string[] };
parentId: number | null;
children: GameTree[];
};
字符串
您可以找到问题in this commit的可重现示例。
到目前为止,我已经成功地对它进行了建模,就像它出现在Go编辑器的游戏树中一样:
x1c 0d1x的数据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
型
根据@cybersam的回答,我认为这可以使Neo4j更明确,因此它使用m.move
上的索引-例如CREATE 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多个移动分支,但通常不会有那么多分支。而且分析将在单向分支上进行,顺序很重要(没有跳过),所以它可能会限制搜索空间。
或者,我正在考虑在每个移动节点中放置一个字符串,其中包含它的完整路径。这样我就可以使用Regex(我知道Regex也可以建模为图)而不是路径搜索。也就是说,如果它有效,那么我认为使用SQL数据库可能就足够了。然而,我可能会坚持使用Neo4j,因为将其建模为图可以在未来提供更多有用的功能。
2条答案
按热度按时间s3fp2yjn1#
要获取从根
GameNode
到['rm','ro']
的路径p
,您可以在Neo4j 5.9+中编写以下内容:字符串
要获得整个路径,直到序列中的最后一步,您需要添加一个检查,以确保没有进一步的移动:
型
如果存在性能问题,那将是令人惊讶的:在代表每个游戏的小图上的足够具体的模式不应该很慢。
mspsb9vt2#
下面的查询在返回每个包含所需移动序列的游戏中的移动时应该是相当高性能的。它假设您:
MoveNode.move
上有一个index,$moves
参数中传递所需移动的列表,MATCH
中的可变长度关系的长度调整为比$moves
的长度小1。例如,如果$moves
有2个项目,则使用*1
而不是*2
。* 这确实很难看,但Cypher不支持动态边界。*查询
字符串
索引用于限制和锚搜索,通过快速查找
m1
节点(MoveNode
匹配$moves
中的第一个项目),而不是从每个GameNode
开始遍历所有路径。然后查询:m1
后面跟随满足$moves
列表其余部分的子路径来过滤m1
,m1
节点向后查找相应的GameNode
s。因此,这个查询从使用索引查找第一组相关节点开始,并不断向已经找到的节点添加关系(和结束节点),直到最终获得所需的结果。