Building a Queue Network on Neo4j Cypher and APOC
May 23: Berlin Wall, One Month Graph Challenge
Welcome word
In this series of small posts I do one simple graph daily. Domain model of graph somehow related to day’s history, some historical event, celebration or person. I do this challenge to learn Neo4j Data Modeling and Cypher. Every day. One month. Follow me. Maybe you will be inspired and next month would be yours One Month Graph Challenge. #OMGChallenge
Domain model
May 23, 1949 (70 years ago) Education Day of the Federal Republic of Germany. In 1949, a new state was created in the western occupation zone — the Federal Republic of Germany (Germany), and in the Soviet occupation zone — the German Democratic Republic (GDR).
In todays post, I want to remember about physical and ideological barrier, that divided Berlin from 1961 to 1989 — Berlin Wall.
I plan to play with “business logic” abilities of Cypher. Interesting, is it possible to build a Queue network (system in which queues are connected by a routes) and solve some problem using only Cypher queries. As Queue network model I will use a small graph of Berlin Wall border crossings. Idea is to find how some amount of people can cross the border via several checkpionts from one side of Berlin to another.
Graph
Checkpoints between West and East Berlin. All people starts from same place and goes to same destination place. Between this 2 places we have 7 checkpoints splitted on 2 parts: East part and West part.
I can set a weight of checkpoint represents a current queue occupancy (how much people right now stuck in queue at this checkpoint).
I also need to set a limit to set maximum capacity of possible queue. When queue reaches the limit — it is unavailable for person until it is get free.
Checkpoint can operate 1 person in N minutes, based on property minutePerPerson.
With such structure I want to find faster path to cross on other side using one or another checkpoint in appropriant moment of time for each person. It can be hard in theory, but simple to understand step by step.
MERGE (from:Place { name: "East Berlin" })
MERGE (to:Place { name: "West Berlin" })
MERGE (from)-[:WAY { weight: 1 }]->(c11:Place:East { name: "Bornholmer Straße East" })-[:WAY { weight: 5, limit: 5, minutePerPerson: 2 }]->(c12:Place:West { name: "Bornholmer Straße West" })-[:WAY { weight: 2 }]->(to)
MERGE (from)-[:WAY { weight: 3 }]->(c21:Place:East { name: "Reinickendorfer Straße East" })-[:WAY { weight: 1, limit: 5, minutePerPerson: 2 }]->(c22:Place:West { name: "Reinickendorfer Straße" })-[:WAY { weight: 4 }]->(to)
MERGE (from)-[:WAY { weight: 2 }]->(c31:Place:East { name: "Invalidenstraße East" })-[:WAY { weight: 5, limit: 5, minutePerPerson: 3 }]->(c32:Place:West { name: "Invalidenstraße West" })-[:WAY { weight: 1 }]->(to)
MERGE (from)-[:WAY { weight: 1 }]->(c41:Place:East { name: "Checkpoint Charlie East" })-[:WAY { weight: 6, limit: 10, minutePerPerson: 4 }]->(c42:Place:West { name: "Checkpoint Charlie West" })-[:WAY { weight: 2 }]->(to)
MERGE (from)-[:WAY { weight: 2 }]->(c51:Place:East { name: "Heinrich-Heine-Straße East" })-[:WAY { weight: 2, limit: 5, minutePerPerson: 2 }]->(c52:Place:West { name: "Heinrich-Heine-Straße West" })-[:WAY { weight: 4 }]->(to)
MERGE (from)-[:WAY { weight: 7 }]->(c61:Place:East { name: "Oberbaumbrücke East" })-[:WAY { weight: 1, limit: 5, minutePerPerson: 1 }]->(c62:Place:West { name: "Oberbaumbrücke West" })-[:WAY { weight: 3 }]->(to)
MERGE (from)-[:WAY { weight: 6 }]->(c71:Place:East { name: "Sonnenallee East" })-[:WAY { weight: 2, limit: 10, minutePerPerson: 4 }]->(c72:Place:West { name: "Sonnenallee West" })-[:WAY { weight: 4 }]->(to)
Let’s start with simple scenario for one person located at East side.
MATCH (p:Person) DETACH DELETE p;
MATCH (pl:Place { name: "East Berlin" })
MERGE (p:Person { name: "Klaus" })
MERGE (p)-[:AT]->(pl)
RETURN p, pl;
If wall wouldn’t exist, Klaus can easily travel from East to West, not really matter how much time we give him for this trip:
MATCH (to:Place { name: "West Berlin" })
MATCH (p:Person)-[start:AT]->(from:Place { name: "East Berlin" })
DELETE start
MERGE (p)-[:AT]->(to)Now as you can see, Klaus already at West Berlin:
MATCH (p:Person)-[:AT]->(pl:Place)
RETURN p, pl
Lucky Klaus.
Now Klaus will go using faster way but need to cross one of Berlin Wall checkpoints. Only available checkpoints with weight less than capacity limit. Klaus will follow suggestion of Shortest Path algorithm to reach West side as fast as weights comparsation of queues allowed.
I don’t really need to use spatials, so I will set zeros to this properties, just to be able to use A* algorithm with so necessary to me projection:
MATCH (p:Place) SET p.latitude = 0.0, p.longitude = 0.0The query:
MATCH (to:Place { name: 'West Berlin' })
MATCH (p:Person)-[start:AT]->(from:Place { name: 'East Berlin' })
DELETE start
WITH from, to, p
CALL algo.shortestPath.astar.stream(from, to, 'weight', 'latitude', 'longitude', {
nodeQuery:'MATCH (p:Place)-[w:WAY]-() WHERE w.limit is null OR w.weight < w.limit RETURN id(p) as id',
relationshipQuery:'MATCH (p1:Place)-[w:WAY]->(p2:Place) WHERE w.limit is null OR w.weight < w.limit RETURN id(p1) as source, id(p2) as target, w.weight as weight', graph:'cypher' }) YIELD nodeId, cost
WITH collect(algo.asNode(nodeId).name) as checklist, max(cost) as total, p, to
MERGE (p)-[:AT]->(to)
SET p.total = total, p.checklist = checklist
RETURN p as personRoute
Based, on A-star algorithm we got new result for Klaus. Looks good.
Now I some close to the level of system. Let’s transfer N people to West side.
MATCH (p:Person) DETACH DELETE p;
MATCH (pl:Place { name: "East Berlin" })
UNWIND range(1, 10) as n
MERGE (p:Person { name: "Klaus_" + toString(n) })
MERGE (p)-[:AT]->(pl)
RETURN p, pl;Robot Klaus_1 and his 9 robo-friends ready to travel abroad. Every new iteration, person will be appended into checkpoint queue. Weight will be increased at coming, but not decresed after departure (for now). So next person will decide route based on new knowledge about occupied checkpoints. It is not full solution, but partial: timer not work, but new filled queues start impact on shortest path search for the next person.
CALL apoc.periodic.iterate(
"MATCH (to:Place { name: 'West Berlin' }) MATCH (p:Person)-[:AT]->(from:Place { name: 'East Berlin' }) RETURN p, from, to ORDER BY p.name",
"CALL algo.shortestPath.astar.stream(from, to, 'weight', 'latitude', 'longitude', { nodeQuery:'MATCH (p:Place)-[w:WAY]-() WHERE w.limit is null OR w.weight < w.limit RETURN id(p) as id', relationshipQuery:'MATCH (p1:Place)-[w:WAY]->(p2:Place) WHERE w.limit is null OR w.weight < w.limit RETURN id(p1) as source, id(p2) as target, w.weight as weight', graph:'cypher' }) YIELD nodeId, cost WITH collect(algo.asNode(nodeId).name) as checklist, max(cost) as total, p, to MERGE (p)-[:AT]->(to) SET p.total = total, p.checklist = checklist WITH p MATCH (:East { name: p.checklist[1] })-[w:WAY]->(:West) SET w.weight = w.weight + 1 WITH p MATCH (p)-[start:AT]->(from:Place { name: 'East Berlin' }) DELETE start", { batchSize: 1, parallel: false })Finally, I found a way to commit one by one each person impact. So next person now calculating path based on results from prevous person. Damn! This is amazing!
First part of operation contains only selection, second — all operations.
Here the route for each person by order person cross the Wall:
MATCH (p:Person)
RETURN p.name as name, p.checklist as personRoute, p.total as total
ORDER BY name
By numbers we can see that HHStr. with 8 was best option until Klaus_1 occupied itand it become 9 long. Then shortest path become ReinStr. with 8 points. When both checkpoints reached 10, Charlie checkpoint come into the picture. It is really fun to analyze.
We can try same query for 100 Klauses and see how much of them sucessfully cross the border. You can do it clean up everything and rebuild again with 100 persons. I did that and here the output:
MATCH (e:Place { name: "East Berlin" })<-[:AT]-(pe:Person)
WITH count(pe) as stayHome
MATCH (w:Place { name: "West Berlin" })<-[:AT]-(pw:Person)
RETURN stayHome, count(pw) as crossedTheWall
Only 23 slots left. Without updating per minute we simply stuck in total limits of checkpoint queue capacity. We must clean space with configuration we have.
Let’s assume, that each Person is a stream of minutes, so what we should add into query is just a decresing of the number of weight of each checkpoint when minute match checkpoint minutePerPerson condition. Count starts with first person.
As you can see checkpoint Charlie working very slow 1 person in 4 minutes, while fastest one Oberbaumb — 1 minutePerPerson. I also need to set kind of technical property number to user, to use it like a minute tick. I go easy way.
MATCH (p:Person) DETACH DELETE p;
MATCH (pl:Place { name: "East Berlin" })
UNWIND range(1, 100) as n
MERGE (p:Person { name: "Klaus_" + toString(n), number: n })
MERGE (p)-[:AT]->(pl)
RETURN p, pl;But it is not correct, actually. Because time must goes, even if all queues is stuck. This is only one possible way to expect, that time goes and some checkpoint will be again open to join. But ok, let’s live with this mistake in mind.
CALL apoc.periodic.iterate(
"MATCH (to:Place { name: 'West Berlin' }) MATCH (p:Person)-[:AT]->(from:Place { name: 'East Berlin' }) RETURN p, from, to ORDER BY p.name",
"CALL algo.shortestPath.astar.stream(from, to, 'weight', 'latitude', 'longitude', { nodeQuery:'MATCH (p:Place)-[w:WAY]-() WHERE w.limit is null OR w.weight < w.limit RETURN id(p) as id', relationshipQuery:'MATCH (p1:Place)-[w:WAY]->(p2:Place) WHERE w.limit is null OR w.weight < w.limit RETURN id(p1) as source, id(p2) as target, w.weight as weight', graph:'cypher' }) YIELD nodeId, cost WITH collect(algo.asNode(nodeId).name) as checklist, max(cost) as total, p, to MERGE (p)-[:AT]->(to) SET p.total = total, p.checklist = checklist WITH p MATCH (:East { name: p.checklist[1] })-[w:WAY]->(:West) SET w.weight = w.weight + 1 WITH p MATCH (p)-[start:AT]->(from:Place { name: 'East Berlin' }) DELETE start WITH p MATCH (che:East)-[w:WAY]-(chw) WHERE (p.number % w.minutePerPerson) = 0 SET w.weight = w.weight - 1", { batchSize: 1, parallel: false })
Klauses bothers, welcome to the Federal Republic of Germany!
MATCH (p:Person)
RETURN p.checklist as checkpoint, count(p) as numberOfVisitors
Resume
To be true, I don’t really expected to reach the today’s goal. It was so complex from the first view. I don’t event know is it possible at all. So today I can be proud of what I’ve done. True challenge.
Now I understand more about execution flow of Cypher and hope this lesson helps me in my future topics.
Some work still left, you can finish the system fully and apply timer tick in correct way, for example. If you have any ideas of improvements — please, comment below. If you found mistake — please, comment. I know, I do a lot of mistakes. But this is way how humans learning the things.
