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 can implement a graph search algorithm and create your own since AGE does nbt provide a built-in shortest path function. Dijkstra's Algorithm is considerably the best choice as it is the most efficient to find the shortest path. NetworkX, igraph, or PyGraphviz are also pre-built functions for finding shortest paths.

Answer 2

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")

Answer 3

At this point, there is no Pre-defined function in Apache-age to find the shortest path between two nodes, But you can define a Python function that finds the shortest path between the nodes,

Something like this:

def dijkstra(age, start_node, end_node):
      // function logic here
      return path_list

Or you can use the already defined functions defined by libraries such as NetworkX, igraph or PyGraphviz

Answer 4

To find shortest path between nodes in a graph you can rely on using graph search algorithm. One such algorithm is Dijkstra's Algorithm thats works at starting at initial node and finding the shortest path to all other nodes in a graph.

We can have Breadth First Algorithm

def bfs(age, start_node, end_node):
//logic here
return

startNode = node_a
endNode = node_d
shortestPath = bfs(start_node, end_node)

Answer 5

To find the shortest path between two nodes you have to implement a general graph shortest path finding algorithm. Some of the popular algorithms:

• Dijkstra's Algorithm
• Bellman Ford Algorithm
• Floyd Warshall Algorithm

Now by following any particular algorithm, the graph traversal and computation can be written inside a function:

    def find_shortest_path(graph_name,start_node,end_node):
      //algo here

Now the function can return both the shortest distance and the path by backtracking.

Answer 6

Since AGE models after a relational database, to find the shortest path you can choose an algorithm that works on a graph model. The most popular algorithms are:

1. Dijkstra's Algorithm
2. Bellman Ford
3. Floyd Warshall Algorithm
4. A* Algorithm

In my opinion, for such a graph you should use the A* algorithm. It will follow the same coding structure as the above and will use the distance value as the heuristic. A pseudocode of this approach can look something like this:

def a_star(source, dest, heuristic):
    open_set = []
    closed_set = []
    g_score = [source, 0] #Of the starting heuristic node
    parents = None
    
    while open_set:
      current = min(open_set)[1]
      open_set.remove() #The distance of the current node from our destination node
      if current == dest:
        path = []
        while current:
           path.append(current)
           current = parents[current]
        return path[::-1] #Return in reverse order
      closed_set[current_node] = True

      #Add further logic here for how to treat neighbours

Answer 7

You should try implementing Dijkstra's algorithm to cater to your requirement of finding the shortest path between nodes.

def dijkstra(age, node_a, node_d):
  //logic here
  return path

You can refer here for Dijkstra's Algo in Python

There are several other algorithms that you could also explore.

Answer 8

you can use dijikstra algo or bell manford.

def dijikstra(start_node,end_node,age)
logic
return path

def bellman_ford(age,start,end)

Answer 9

First step would be picking which shortest path algorithm you would like to use. A couple of popular ones are Dijkstra, Bellman-Ford, A*. You can find the algorithms using a quick google search and proceed to simply define them using simple python.

def dijkstra(graph, node_start, node_end):
  # algorithm here
  return shortest_path

Answer 10

Bell Manford or the Dijikstra algorithm are options.

Code:

def dijikstra(start_node,end_node,age)
" logic " 
return path
def bellman_ford(age,start,end)

Answer 11

To find the shortest path between nodes in Apache AGE, you can implement a graph search algorithm and create your own since AGE doesn't provide a built-in shortest path function.
Dijkstra's Algorithm will be best choice as it the most popular algorithm to find shortest path.

Alternatively you can utilize existing graph libraries like NetworkX, igraph, or PyGraphviz, which offer pre-built functions for finding shortest paths.

Answer 12

There are two solutions to your problem either you can implemet your own algorithm such as Dijkstra Algorithm Bellman Ford Algorithm Floyd Warshall Algorithm Or you can use the apache AGE dijkstra algorithm package in python. This is the solution I prefer. You can access it easily by installing it through PIP

https://pypi.org/project/apache-age-dijkstra/

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

For further reference you can read the official documentation of the package.

Answer 13

Because Apache AGE does not include a built-in function for determining the shortest path, you can develop a custom graph search algorithm.

Dijkstra's Algorithm is a good option among the alternatives since it is effective in this situation. As an alternative, you can use pre-built functions for calculating the shortest path from libraries like NetworkX, igraph, or PyGraphviz.

By using these libraries, you may speed up the process and avoid having to recreate the algorithm from start.

Answer 14

You can use Dijikstra Algorithm to find shortest path between the nodes

def dijikstra(start_node,end_node,age)
logic
return path

Answer 15

Implementing dijkstra algorithm in the apache age can be a a bit tricky.

You can follow this article See here for more information related to the dijkstra in Apache age using Python. The article follows:

1. Installation of required components.
2. Then importing necessary files.
3. Making a connection to postgreSQL.
4. Obtaining all the edges and vertices.
5. Creating adjacent matrices using obtained edges.
6. Initializing the graphs and then applying the dijkstra.