DEV Community

Cover image for Exploring Shortest Path Algorithms with Apache AGE
Matheus Farias de Oliveira Matsumoto
Matheus Farias de Oliveira Matsumoto

Posted on

Exploring Shortest Path Algorithms with Apache AGE

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);
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

Saxeburg

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) 
Enter fullscreen mode Exit fullscreen mode
     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)
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

                                                                                                                        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)
Enter fullscreen mode Exit fullscreen mode

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)