How to implement shortest path algorithm in Apache Age using Python and Cypher?

Question

I'm working on a Python project that uses Apache age as the graph database, and I need to find the shortest path between two possible nodes. How do I implement this using Python? The code for node creation and the graph structure is as follows:

# Python code to create nodes and relationships
from age import Age

age = Age()
node_a = age.create_node("City", {"name": "New York"})
node_b = age.create_node("City", {"name": "Los Angeles"})
node_c = age.create_node("City", {"name": "Chicago"})
node_d = age.create_node("City", {"name": "Houston"})

edge_ab = age.create_edge(node_a, node_b, "CONNECTED", {"distance": 2451})
edge_ac = age.create_edge(node_a, node_c, "CONNECTED", {"distance": 713})
edge_cd = age.create_edge(node_c, node_d, "CONNECTED", {"distance": 940})
edge_bd = age.create_edge(node_b, node_d, "CONNECTED", {"distance": 1375})

# Sample graph structure:
# New York --(2451)-- Los Angeles
#     |                |
#   (713)            (1375)
#     |                |
#   Chicago --(940)-- Houston

How can I find the shortest path from New York to Houston?

Answer 1

You have a couple of options from using algorithms such as Bellmen-Ford to Dijkstra's algorithm. You can use the python package called apache-age-dijkstra which is an implementation of djikstra's algorithm as an implementation of the shortest path problem.

You can install it via PIP

pip install apache-age-dijkstra
pip install antlr4-python3-runtime==4.9.3

import the package

from age_dijkstra import Age_Dijkstra

Connect to postgresql

con = Age_Dijkstra()
con.connect(
    host="localhost",       # default is "172.17.0.2" 
    port="5430",            # default is "5432"
    dbname="postgresDB",    # default is "postgres"
    user="postgresUser",    # default is "postgres"
    password="postgresPW",  # default is "agens"
    printMessage = True     # default is False
)

Get all the vertices

nodes = []
for x in con.get_all_vertices():
    nodes.append(x['property_name'])

Create adjacent matrices using the edges

init_graph = {}
for node in nodes:
    init_graph[node] = {}
for edge in edges :
    v1 = edge['v1']['vertices_property_name']
    v2 = edge['v2']['vertices_property_name']
    dist = int(edge['e']['edge_property_name'])
    init_graph
    init_graph[v1][v2] = dist

Initialize the graph and then use the djikstra algorithm and print it

#init graph
from age_dijkstra import  Graph
graph = Graph(nodes, init_graph)

#use djikstras algo
previous_nodes, shortest_path = Graph.dijkstra_algorithm(graph=graph, start_node="vertices_property_name")

#print shortest path
Graph.print_shortest_path(previous_nodes, shortest_path, start_node="vertices_property_name", target_node="vertices_property_name")