RoomDoorKey.adoc

Maze with locked doors

Imagine a maze with rooms (nodes) and doors (relationships) between the rooms. The doors to some rooms are locked and their keys are held in other rooms (as properties).

In this gist model of the maze, you can reach room D by following the path A→B→C→A, picking up the key for room D in room B. However it is not possible to reach room F, since the key to room F is in room E, and the key to room E is in room D, and there is no way back from room D to room A, so room E is inaccessible. (Finding the HIDDEN door from room D to room C would make this possible.)

Is it possible to create queries which take into account the keys that can be picked up on the way? For example:

• Is it possible to get from room X to room Y?

• What are all the paths that lead from room A to room Z?

• I’m in room N with these keys. Have I come to a dead end?

• What keys do I need to get from the Library to the Conservatory?

CREATE INDEX ON :Room(name);
CREATE (a:Room {name:'A'})
     , (b:Room {name:'B', key:'D'})
     , (c:Room {name:'C'})
     , (d:Room {name:'D', key:'E'})
     , (e:Room {name:'E', key:'F'})
     , (f:Room {name:'F'})
     , (a)-[ab:DOOR]->(b)
     , (a)-[ad:DOOR {lock: 'D'}]->(d)
     , (a)-[ae:DOOR {lock: 'E'}]->(e)
     , (b)-[bc:DOOR]->(c)
     , (c)-[ca:DOOR]->(a)
     , (e)-[ed:DOOR]->(d)
     , (d)-[df:DOOR {lock: 'F'}]->(f)
     , (d)-[dc:HIDDEN]->(c)
RETURN a,b,c,d,e,f;

Which paths of rooms, keys and locks can we take from A to D

MATCH path =(:Room { name:"A" })-[:DOOR*0..]->(:Room { name:"D" })
RETURn EXTRACT(room IN nodes(path)| COALESCE(room.key,'_')) AS keys,
       EXTRACT(room IN nodes(path)| COALESCE(room.name,'_')) AS rooms,
       EXTRACT(door IN rels(path)| COALESCE(door.lock,'_')) AS locks;

Which door-locks are unlocked by the keys

// find the two rooms and all paths between them
MATCH path = (:Room {name:"A"})-[:DOOR*0..]->(:Room {name:"D"})
// take path, keys and doors as collections
WITH path,
     EXTRACT(room IN nodes(path) | COALESCE(room.key,'_')) AS keys,
     rels(path) AS doors
// condition for all doors
// either no lock or the lock-number is in the collection of keys collected so far
WHERE ALL(idx IN RANGE(0,size(doors)-1) WHERE (doors[idx]).lock IS NULL OR (doors[idx]).lock IN (keys[0..idx]))
// return the path(s)
RETURN path;

Let’s try to get to room F

// find the two rooms and all paths between them
MATCH path = (:Room {name:"A"})-[:DOOR*0..]->(:Room {name:"F"})
// take path, keys and doors as collections
WITH path,
     EXTRACT(room IN nodes(path) | COALESCE(room.key,'_')) AS keys,
     rels(path) AS doors
// condition for all doors
// either no lock or the lock-number is in the collection of keys collected so far
WHERE ALL(idx IN RANGE(0,size(doors)-1) WHERE (doors[idx]).lock IS NULL OR (doors[idx]).lock IN (keys[0..idx]))
// return the path(s)
RETURN path;

Not possible!

But we can if we find the hidden door!

MATCH path = (:Room {name:"A"})-[:DOOR|:HIDDEN*0..]->(:Room {name:"F"})
WITH path,
     EXTRACT(room IN nodes(path) | COALESCE(room.key,'_')) AS keys,
     rels(path) AS doors
WHERE ALL(idx IN RANGE(0,size(doors)-1) WHERE (doors[idx]).lock IS NULL OR (doors[idx]).lock IN (keys[0..idx]))
RETURN path;

Only if Cypher would allow us to follow a path (C)-->(A) twice!