recursiongraphneo4jtreecypher

How to Recursively Create a Tree with Cypher (Neo4j)


I'm trying to replicate an SGF game tree on Neo4j with Cypher. The tree is of this shape:

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

This is the creation query I'm trying to work out:

UNWIND $moves AS move

MATCH (parent)

WHERE ((parent:GameNode) OR (parent:MoveNode))
  AND parent.game_id = $gameId
  AND parent.id = move.parentId

CREATE   (parent)
        -[:NEXT_MOVE]
       ->(:MoveNode{
           game_id: $gameId,
           id:      move.id
         })

Initially, the root of the tree is a GameNode, which I create separately, because it holds interesting metadata. Anyways, this won't work like this because, at the time of the UNWIND and MATCH clauses, there exists only one parent, the rest of them will/should be created recursively.

Is there a way of doing this recursive creation in Cypher? Maybe there's some recursive keyword I can't seem to find (this seems like such a common kind of problem...)? Maybe there's a useful APOC procedure somewhere?

As a workaround, I'm thinking about creating all the MoveNodes first, and then using the query above to string them back together. It would look like this:

// 1. Create All The Move Nodes

UNWIND $moveNodes AS move

CREATE (:MoveNode{
         game_id: move.game_id,
         id:      move.id
       })

// 2. Tie them to their Parents

WITH move

MATCH (parent{
        game_id: move.game_id,
        id:      move.parentId
      }),
      (m:MoveNode{
        game_id: move.game_id,
        id:      move.id
      })

WHERE parent:GameNode
   OR parent:MoveNode
  
CREATE (parent)-[:NEXT_MOVE]->(m)

Solution

  • If each query execution is for a single chain of moves that are in order of play, and the parent GameNode already exists, then you can use the following:

    UNWIND $moveNodes AS move
    CALL {
        WITH move
        MATCH (parent:GameNode|MoveNode {game_id: $gameId, id: move.parentId})
        CREATE (parent)-[:NEXT_MOVE]->(m:MoveNode {game_id: $gameId, id: move.id})
    }