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

How to find all possible routes along with the time travelled? – Postgresql

I have created a few nodes called routes and have given several relationships that are travel times as shown below.

SELECT *
FROM cypher('Map', $$
    CREATE (a:Route {name: 'A'}), 
        (b:Route {name: 'B'}),
        (c:Route {name: 'C'}),
        (d:Route {name: 'D'}),
        (e:Route {name: 'E'}),
        (f:Route {name: 'F'}),
        (a)-[:Connects {time: 4}]->(b),
        (a)-[:Connects {time: 2}]->(c),
        (b)-[:Connects {time: 6}]->(c),
        (b)-[:Connects {time: 9}]->(d),
        (c)-[:Connects {time: 1}]->(d),
        (c)-[:Connects {time: 8}]->(e),
        (c)-[:Connects {time: 3}]->(f),
        (d)-[:Connects {time: 3}]->(a),
        (e)-[:Connects {time: 10}]->(b),
        (f)-[:Connects {time: 2}]->(e)
$$) AS (x agtype);

I am trying to find all possible connections for specified routes along with the total time travelled. For example, if I want the information from Route ‘A’ to Route ‘F’, how would I do so? I am not concerned about the shortest path but just want all the possible routes.

Tags:

2

Answers


  1. 0

    The way I think that you can solve it, is coding a DFS (Depth First Search). Marking all the visited nodes, and doing an if if the destination node has not been visited, and calling the dfs function recursively with this node as the new node parameter.

    You can write your own codes to run on Apache AGE, you just have to save it at:

    age/src/backend/utils/

    I found this code in C language, maybe it can help you!

    Depth First Search(DFS)

    Login or Signup to reply.
  2. 0

    You can use the following query

    SELECT * FROM cypher('stack75718178',$$
    MATCH p=(a:Route {name:'A'})-[:Connects *]->(b:Route {name:'F'})
    WITH p, relationships(p) as edges
    UNWIND edges as edge
    RETURN p, sum(edge.time)
$$) as (path agtype, totalcost agtype);

    Result:

                                                                                                                                                                                                  
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                  path                                        
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                           | totalcost 
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------+-----------
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842626, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "prope
rties": {"time": 2}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842630, "label": "Connects", "end_id": 844424930131973, "start_id
": 844424930131971, "properties": {"time": 8}}::edge, {"id": 844424930131973, "label": "Route", "properties": {"name": "E"}}::vertex, {"id": 1125899906842633, "label": "Connects", "end_id": 
844424930131970, "start_id": 844424930131973, "properties": {"time": 10}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842628, "lab
el": "Connects", "end_id": 844424930131972, "start_id": 844424930131970, "properties": {"time": 9}}::edge, {"id": 844424930131972, "label": "Route", "properties": {"name": "D"}}::vertex, {"i
d": 1125899906842632, "label": "Connects", "end_id": 844424930131969, "start_id": 844424930131972, "properties": {"time": 3}}::edge, {"id": 844424930131969, "label": "Route", "properties": {
"name": "A"}}::vertex, {"id": 1125899906842625, "label": "Connects", "end_id": 844424930131970, "start_id": 844424930131969, "properties": {"time": 4}}::edge, {"id": 844424930131970, "label"
: "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842627, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131970, "properties": {"time": 6}}::edge, {"id"
: 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id": 844424930131971, "properties":
 {"time": 3}}::edge, {"id": 844424930131974, "label": "Route", "properties": {"name": "F"}}::vertex]::path | 45
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842626, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "prope
rties": {"time": 2}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842629, "label": "Connects", "end_id": 844424930131972, "start_id
": 844424930131971, "properties": {"time": 1}}::edge, {"id": 844424930131972, "label": "Route", "properties": {"name": "D"}}::vertex, {"id": 1125899906842632, "label": "Connects", "end_id": 
844424930131969, "start_id": 844424930131972, "properties": {"time": 3}}::edge, {"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842625, "labe
l": "Connects", "end_id": 844424930131970, "start_id": 844424930131969, "properties": {"time": 4}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id
": 1125899906842627, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131970, "properties": {"time": 6}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"
name": "C"}}::vertex, {"id": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id": 844424930131971, "properties": {"time": 3}}::edge, {"id": 844424930131974, "label":
 "Route", "properties": {"name": "F"}}::vertex]::path                                                                                                                                         
                                                                                                                                                                                              
                                                                                                           | 19
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842625, "label": "Connects", "end_id": 844424930131970, "start_id": 844424930131969, "prope
rties": {"time": 4}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842627, "label": "Connects", "end_id": 844424930131971, "start_id
": 844424930131970, "properties": {"time": 6}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842631, "label": "Connects", "end_id": 
844424930131974, "start_id": 844424930131971, "properties": {"time": 3}}::edge, {"id": 844424930131974, "label": "Route", "properties": {"name": "F"}}::vertex]::path                         
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                           | 13
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842626, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "prope
rties": {"time": 2}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id
": 844424930131971, "properties": {"time": 3}}::edge, {"id": 844424930131974, "label": "Route", "properties": {"name": "F"}}::vertex]::path                                                   
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                           | 5
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842625, "label": "Connects", "end_id": 844424930131970, "start_id": 844424930131969, "prope
rties": {"time": 4}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842628, "label": "Connects", "end_id": 844424930131972, "start_id
": 844424930131970, "properties": {"time": 9}}::edge, {"id": 844424930131972, "label": "Route", "properties": {"name": "D"}}::vertex, {"id": 1125899906842632, "label": "Connects", "end_id": 
844424930131969, "start_id": 844424930131972, "properties": {"time": 3}}::edge, {"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842626, "labe
l": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "properties": {"time": 2}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id
": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id": 844424930131971, "properties": {"time": 3}}::edge, {"id": 844424930131974, "label": "Route", "properties": {"
name": "F"}}::vertex]::path                                                                                                                                                                   
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                           | 21
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842626, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "prope
rties": {"time": 2}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842630, "label": "Connects", "end_id": 844424930131973, "start_id
": 844424930131971, "properties": {"time": 8}}::edge, {"id": 844424930131973, "label": "Route", "properties": {"name": "E"}}::vertex, {"id": 1125899906842633, "label": "Connects", "end_id": 
844424930131970, "start_id": 844424930131973, "properties": {"time": 10}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842627, "lab
el": "Connects", "end_id": 844424930131971, "start_id": 844424930131970, "properties": {"time": 6}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"i
d": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id": 844424930131971, "properties": {"time": 3}}::edge, {"id": 844424930131974, "label": "Route", "properties": {
"name": "F"}}::vertex]::path                                                                                                                                                                  
                                                                                                                                                                                              
                                                                                                                                                                                              
                                                                                                           | 29
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842625, "label": "Connects", "end_id": 844424930131970, "start_id": 844424930131969, "prope
rties": {"time": 4}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842627, "label": "Connects", "end_id": 844424930131971, "start_id
": 844424930131970, "properties": {"time": 6}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842629, "label": "Connects", "end_id": 
844424930131972, "start_id": 844424930131971, "properties": {"time": 1}}::edge, {"id": 844424930131972, "label": "Route", "properties": {"name": "D"}}::vertex, {"id": 1125899906842632, "labe
l": "Connects", "end_id": 844424930131969, "start_id": 844424930131972, "properties": {"time": 3}}::edge, {"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id
": 1125899906842626, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "properties": {"time": 2}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"
name": "C"}}::vertex, {"id": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id": 844424930131971, "properties": {"time": 3}}::edge, {"id": 844424930131974, "label":
 "Route", "properties": {"name": "F"}}::vertex]::path                                                                                                                                         
                                                                                                                                                                                              
                                                                                                           | 19
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842625, "label": "Connects", "end_id": 844424930131970, "start_id": 844424930131969, "prope
rties": {"time": 4}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842627, "label": "Connects", "end_id": 844424930131971, "start_id
": 844424930131970, "properties": {"time": 6}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842630, "label": "Connects", "end_id": 
844424930131973, "start_id": 844424930131971, "properties": {"time": 8}}::edge, {"id": 844424930131973, "label": "Route", "properties": {"name": "E"}}::vertex, {"id": 1125899906842633, "labe
l": "Connects", "end_id": 844424930131970, "start_id": 844424930131973, "properties": {"time": 10}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"i
d": 1125899906842628, "label": "Connects", "end_id": 844424930131972, "start_id": 844424930131970, "properties": {"time": 9}}::edge, {"id": 844424930131972, "label": "Route", "properties": {
"name": "D"}}::vertex, {"id": 1125899906842632, "label": "Connects", "end_id": 844424930131969, "start_id": 844424930131972, "properties": {"time": 3}}::edge, {"id": 844424930131969, "label"
: "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842626, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "properties": {"time": 2}}::edge, {"id"
: 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id": 844424930131971, "properties":
 {"time": 3}}::edge, {"id": 844424930131974, "label": "Route", "properties": {"name": "F"}}::vertex]::path | 45
 [{"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842625, "label": "Connects", "end_id": 844424930131970, "start_id": 844424930131969, "prope
rties": {"time": 4}}::edge, {"id": 844424930131970, "label": "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842628, "label": "Connects", "end_id": 844424930131972, "start_id
": 844424930131970, "properties": {"time": 9}}::edge, {"id": 844424930131972, "label": "Route", "properties": {"name": "D"}}::vertex, {"id": 1125899906842632, "label": "Connects", "end_id": 
844424930131969, "start_id": 844424930131972, "properties": {"time": 3}}::edge, {"id": 844424930131969, "label": "Route", "properties": {"name": "A"}}::vertex, {"id": 1125899906842626, "labe
l": "Connects", "end_id": 844424930131971, "start_id": 844424930131969, "properties": {"time": 2}}::edge, {"id": 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id
": 1125899906842630, "label": "Connects", "end_id": 844424930131973, "start_id": 844424930131971, "properties": {"time": 8}}::edge, {"id": 844424930131973, "label": "Route", "properties": {"
name": "E"}}::vertex, {"id": 1125899906842633, "label": "Connects", "end_id": 844424930131970, "start_id": 844424930131973, "properties": {"time": 10}}::edge, {"id": 844424930131970, "label"
: "Route", "properties": {"name": "B"}}::vertex, {"id": 1125899906842627, "label": "Connects", "end_id": 844424930131971, "start_id": 844424930131970, "properties": {"time": 6}}::edge, {"id"
: 844424930131971, "label": "Route", "properties": {"name": "C"}}::vertex, {"id": 1125899906842631, "label": "Connects", "end_id": 844424930131974, "start_id": 844424930131971, "properties":
 {"time": 3}}::edge, {"id": 844424930131974, "label": "Route", "properties": {"name": "F"}}::vertex]::path | 45
(9 rows)
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search