Question 89717 in PostgreSQL Question posted in
The official documentation can be found here.

Making shortest path with Apache AGE – Postgresql

I have been reading Jasper Blues’ blog post : ROCK ’N’ ROLL TRAFFIC ROUTING, WITH NEO4J but I wanted to port it to AGE. He makes a graph with multiple vertices labeled as Metro and each vertex is connected to another one with an edge labeled as HAS_ROUTE and contains a travelTime property. Here are the vertices and edges created:

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)

Then, in the MOST EXPEDIENT ROUT section, there is this query:

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 [metro IN nodes(paths) | metro.name] AS metros,
     collect(rel.travelTime) AS streets,
     sum(rel.travelTime) AS travelTime
  ORDER BY travelTime
RETURN metros, streets, travelTime

But when I run it on AGE, it gives me the following error:

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 [metro IN nodes(paths) | metro.name] AS metros, collect(rel.travelTime) AS streets, sum(rel.travelTime) AS travelTime
        ORDER BY travelTime
        RETURN metros, streets, travelTime
$$) as (metros agtype, streets agtype, travelTime agtype);

-- Syntax error at or near "|"
-- Removing the "|" throws another error : Could not find rte for metro

Another method I tried was running the query below, but it throws ERROR: syntax error at or near "|".

SELECT * FROM cypher('demo', $$
    MATCH (from:Metro {name:'Brooklyn'}), (to:Metro {name:'Phoenix'}), path = (from)-[:HAS_ROUTE]->(to)
    RETURN path AS shortestPath,
    reduce(travelTime = 0, r in relationships(path) | travelTime+r.travelTime; 0) AS totalTravelTime
$$) as (totalTravelTime agtype);

How can I properly execute this query so that I can get the shortest path from one vertex to another?

Tags:

2

Answers


  1. 0

    you can try something like

    MATCH (a:Metro {name: 'Cavite Island'}), (b:Metro {name: 'NYC'})
CALL algo.shortestPath.stream(a, b, 'travelTime') YIELD nodeId, cost
RETURN algo.getNodeById(nodeId).name AS name, cost

    This query first matches the starting and ending vertices, a and b. It then uses the algo.shortestPath.stream function to find the shortest path between a and b, using the travelTime property as the weight for the edges. The YIELD statement returns the nodeId and cost of each node in the shortest path. Finally, the query uses algo.getNodeById to return the name of each node in the shortest path and its cost.

    You can adjust parameters according to your need. Hopefully, this helps. Thanks

    Login or Signup to reply.
  2. 0

    The | symbol is currently not recognized by AGE. You should be able to get a similar result by replacing [metro IN nodes(paths) | metro.name] AS metros with nodes(paths) AS nodes. The only difference is that this will output the entire property of each node instead of only their names.

    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;
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search