Note: This article is based on another written by Jasper Blues on https://medium.com/neo4j/rock-n-roll-traffic-routing-with-neo4j-3a4b863c6030 In his article, he shows how to use Neo4J to create and visualize the graph to calculate the most expedient route between the graph's nodes. Here I'll be demonstrating how to do the same thing but with Apache AGE, which allows us to create graphs on top of PostgreSQL.
Introduction
Lets imagine a fictional city called Saxeburg, where every neighbourhood has a stage and auditorium for an elemental metal, with standing area for thousands. There will be a show in town featuring Moongirl and the Bullhorns. The Bullhorns are the best supporting band in the business, and Moongirl is the show's nubile lead singer. The only problem is that the traffic in Saxeburg is terrible. Moongirl has been spending the day at the beach, with her boys. Meanwhile she is head-lining at the Grand Théâtre de Rabat in NYC tonight.\
Saxeburg's Graph
Open AGE Viewer on the browser of your choice, connect to your local database and create the graph and edges of our city (the vertices are the metro stations and the edges are the routes from one vertex to another).
-- Creating the graph.
SELECT create_graph('Saxeburg');
-- Inserting the data.
SELECT * FROM cypher('Saxeburg', $$
CREATE (cavite:Metro {name: 'Cavite Island'})
CREATE (stGermain:Metro {name: 'St Germain'})
CREATE (pigalle:Metro {name: 'Pigalle'})
CREATE (montreal:Metro {name: 'Montreal'})
CREATE (quebec:Metro {name: 'Quebec'})
CREATE (fortTilden:Metro {name: 'Fort Tilden'})
CREATE (intramuros:Metro {name: 'Intramuros'})
CREATE (chinaTown:Metro {name: 'China Town'})
CREATE (stDomingo:Metro {name: 'St Domingo'})
CREATE (coneyIsland:Metro {name: 'Coney Island'})
CREATE (brooklyn:Metro {name: 'Brooklyn'})
CREATE (uptown:Metro {name: 'Uptown'})
CREATE (cardShark:Metro {name: 'Card Shark'})
CREATE (divisoria:Metro {name: 'Divisoria'})
CREATE (ermita:Metro {name: 'Ermita'})
CREATE (nyc:Metro {name: 'NYC'})
CREATE (staIsabel:Metro {name: 'Sta Isabel'})
CREATE (theRuins:Metro {name: 'The Ruins'})
CREATE (phoenix:Metro {name: 'Phoenix'})
CREATE (bastille:Metro {name: 'Bastille'})
CREATE (puertoDelPostigo:Metro {name: 'Puerto del Postigo'})
CREATE (redLight:Metro {name: 'Red Light'})
CREATE (hotelStPaul:Metro {name: 'Hotel St Paul'})
CREATE (cavite)-[:HAS_ROUTE {travelTime: 2.5}]->(intramuros)
CREATE (cavite)-[:HAS_ROUTE {travelTime: 3}]->(fortTilden)
CREATE (stGermain)-[:HAS_ROUTE {travelTime: 9}]->(intramuros)
CREATE (stGermain)-[:HAS_ROUTE {travelTime: 5.6}]->(chinaTown)
CREATE (pigalle)-[:HAS_ROUTE {travelTime: 6}]->(chinaTown)
CREATE (pigalle)-[:HAS_ROUTE {travelTime: 4}]->(montreal)
CREATE (pigalle)-[:HAS_ROUTE {travelTime: 8.5}]->(nyc)
CREATE (montreal)-[:HAS_ROUTE {travelTime: 3}]->(quebec)
CREATE (fortTilden)-[:HAS_ROUTE {travelTime: 13}]->(brooklyn)
CREATE (coneyIsland)-[:HAS_ROUTE {travelTime: 1.5}]->(brooklyn)
CREATE (brooklyn)-[:HAS_ROUTE {travelTime: 2.5}]->(uptown)
CREATE (brooklyn)-[:HAS_ROUTE {travelTime: 5}]->(theRuins)
CREATE (uptown)-[:HAS_ROUTE {travelTime: 5}]->(intramuros)
CREATE (intramuros)-[:HAS_ROUTE {travelTime: 11}]->(chinaTown)
CREATE (intramuros)-[:HAS_ROUTE {travelTime: 16.5}]->(bastille)
CREATE (chinaTown)-[:HAS_ROUTE {travelTime: 7.5}]->(divisoria)
CREATE (chinaTown)-[:HAS_ROUTE {travelTime: 4.5}]->(ermita)
CREATE (chinaTown)-[:HAS_ROUTE {travelTime: 12.5}]->(nyc)
CREATE (theRuins)-[:HAS_ROUTE {travelTime: 4}]->(cardShark)
CREATE (theRuins)-[:HAS_ROUTE {travelTime: 5.5}]->(phoenix)
CREATE (theRuins)-[:HAS_ROUTE {travelTime: 2.5}]->(redLight)
CREATE (cardShark)-[:HAS_ROUTE {travelTime: 4.5}]->(phoenix)
CREATE (divisoria)-[:HAS_ROUTE {travelTime: 6.5}]->(bastille)
CREATE (ermita)-[:HAS_ROUTE {travelTime: 9}]->(puertoDelPostigo)
CREATE (nyc)-[:HAS_ROUTE {travelTime: 10.5}]->(puertoDelPostigo)
CREATE (nyc)-[:HAS_ROUTE {travelTime: 5}]->(stDomingo)
CREATE (nyc)-[:HAS_ROUTE {travelTime: 2}]->(staIsabel)
CREATE (phoenix)-[:HAS_ROUTE {travelTime: 3.5}]->(redLight)
CREATE (phoenix)-[:HAS_ROUTE {travelTime: 10}]->(bastille)
CREATE (bastille)-[:HAS_ROUTE {travelTime: 6.5}]->(hotelStPaul)
CREATE (bastille)-[:HAS_ROUTE {travelTime: 6}]->(puertoDelPostigo)
CREATE (puertoDelPostigo)-[:HAS_ROUTE {travelTime: 3}]->(staIsabel)
$$) AS (a agtype);
AGE Viewer allows us to visualize our graph. With the following query, we can see all of the vertices, edges and how they connect with one another:
SELECT * from cypher('Saxeburg', $$
MATCH (V)-[R]-(V2)
RETURN V,R,V2
$$) as (V agtype, R agtype, V2 agtype);
Graph Theory
The foundation of graph databases is a subfield of combinatorics known as graph theory. In reality, Euler's solution to the Königsberg bridge issue is regarded as the first theorem of graph theory and the first true proof in the area of networks. Graph theory was born out of a path-finding exercise. Euler also understood that rather than their precise locations, the number of bridges and a list of their ends was the most significant data.
We can explore the routes between vertices in more detail with the following query:
SELECT * FROM cypher('Saxeburg', $$
MATCH (n:Metro)-[r:HAS_ROUTE]-(m:Metro)
RETURN n.name, r.travelTime, m.name
LIMIT 5
$$) AS (n_name agtype, travel_time agtype, m_name agtype)
n_name | travel_time | m_name
-----------------+-------------+---------------
"Cavite Island" | 3 | "Fort Tilden"
"Cavite Island" | 2.5 | "Intramuros"
"St Germain" | 9 | "Intramuros"
"St Germain" | 5.6 | "China Town"
"Pigalle" | 4 | "Montreal"
(5 rows)
We can see that each Metro has a route to various other metros, and that the average travel time has been recorded.
Shortest Path
Using the information at hand, we can now easily find the most expedient route from Cavite Island to NYC:
SELECT * FROM cypher('Saxeburg', $$
MATCH paths = (a:Metro {name: 'Cavite Island'})-[:HAS_ROUTE*1..6]-(b:Metro {name: 'NYC'})
WITH paths, relationships(paths) AS rels
UNWIND rels AS rel
WITH nodes(paths) AS nodes,
collect(rel.travelTime) AS streets,
sum(rel.travelTime) AS travelTime
RETURN nodes, streets, travelTime
$$) AS (metros agtype, streets agtype, travelTime agtype)
ORDER BY travelTime;
metros
| streets | traveltime
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------+-------------------------------+------------
[{"id": 844424930131969, "label": "Metro", "properties": {"name": "Cavite Island"}}::vertex, {"id": 844424930131975, "label": "Metro", "properties": {"name": "Intramuros"}}::vertex, {"id":
844424930131976, "label": "Metro", "properties": {"name": "China Town"}}::vertex, {"id": 844424930131984, "label": "Metro", "properties": {"name": "NYC"}}::vertex]
| [2.5, 11, 12.5] | 26.0
[{"id": 844424930131969, "label": "Metro", "properties": {"name": "Cavite Island"}}::vertex, {"id": 844424930131975, "label": "Metro", "properties": {"name": "Intramuros"}}::vertex, {"id":
844424930131976, "label": "Metro", "properties": {"name": "China Town"}}::vertex, {"id": 844424930131971, "label": "Metro", "properties": {"name": "Pigalle"}}::vertex, {"id": 844424930131984
, "label": "Metro", "properties": {"name": "NYC"}}::vertex]
| [2.5, 11, 6, 8.5] | 28.0
[{"id": 844424930131969, "label": "Metro", "properties": {"name": "Cavite Island"}}::vertex, {"id": 844424930131975, "label": "Metro", "properties": {"name": "Intramuros"}}::vertex, {"id":
844424930131970, "label": "Metro", "properties": {"name": "St Germain"}}::vertex, {"id": 844424930131976, "label": "Metro", "properties": {"name": "China Town"}}::vertex, {"id": 844424930131
984, "label": "Metro", "properties": {"name": "NYC"}}::vertex]
| [2.5, 9, 5.6, 12.5] | 29.6
[{"id": 844424930131969, "label": "Metro", "properties": {"name": "Cavite Island"}}::vertex, {"id": 844424930131975, "label": "Metro", "properties": {"name": "Intramuros"}}::vertex, {"id":
844424930131988, "label": "Metro", "properties": {"name": "Bastille"}}::vertex, {"id": 844424930131989, "label": "Metro", "properties": {"name": "Puerto del Postigo"}}::vertex, {"id": 844424
930131985, "label": "Metro", "properties": {"name": "Sta Isabel"}}::vertex, {"id": 844424930131984, "label": "Metro", "properties": {"name": "NYC"}}::vertex]
| [2.5, 16.5, 6, 3, 2] | 30.0
[{"id": 844424930131969, "label": "Metro", "properties": {"name": "Cavite Island"}}::vertex, {"id": 844424930131975, "label": "Metro", "properties": {"name": "Intramuros"}}::vertex, {"id":
844424930131970, "label": "Metro", "properties": {"name": "St Germain"}}::vertex, {"id": 844424930131976, "label": "Metro", "properties": {"name": "China Town"}}::vertex, {"id": 844424930131
971, "label": "Metro", "properties": {"name": "Pigalle"}}::vertex, {"id": 844424930131984, "label": "Metro", "properties": {"name": "NYC"}}::vertex]
| [2.5, 9, 5.6, 6, 8.5] | 31.6
[{"id": 844424930131969, "label": "Metro", "properties": {"name": "Cavite Island"}}::vertex, {"id": 844424930131975, "label": "Metro", "properties": {"name": "Intramuros"}}::vertex, {"id":
844424930131976, "label": "Metro", "properties": {"name": "China Town"}}::vertex, {"id": 844424930131983, "label": "Metro", "properties": {"name": "Ermita"}}::vertex, {"id": 844424930131989,
"label": "Metro", "properties": {"name": "Puerto del Postigo"}}::vertex, {"id": 844424930131985, "label": "Metro", "properties": {"name": "Sta Isabel"}}::vertex, {"id": 844424930131984, "la
bel": "Metro", "properties": {"name": "NYC"}}::vertex] | [2.5, 11, 4.5, 9, 3, 2] | 32.0
[{"id": 844424930131969, "label": "Metro", "properties": {"name": "Cavite Island"}}::vertex, {"id": 844424930131975, "label": "Metro", "properties": {"name": "Intramuros"}}::vertex, {"id":
844424930131988, "label": "Metro", "properties": {"name": "Bastille"}}::vertex, {"id": 844424930131989, "label": "Metro", "properties": {"name": "Puerto del Postigo"}}::vertex, {"id": 844424
930131984, "label": "Metro", "properties": {"name": "NYC"}}::vertex]
...
(16 rows)
With this, we now know that Moongirl will get to her show on time, reaching NYC in 26 minutes.
Conclusion
Today, we learned how to use Apache AGE and its accessibility for traffic routing. We don't always need to be experts in graph theory or combinatorics to analyze network architectures and find solutions to practical challenges. We might improve our querying even more so that it can adjust to different situations. For example, if a road is closed, it would just look for active roads and provide the results based on those.
For more information about Apache AGE, checkout the links bellow:
Top comments (0)