A*

Supported Graph Characteristics

Weighted edges

Homogeneous vertex types

Heterogeneous vertex types

Algorithm link: A*

A* (pronounced "A-star") is a graph traversal and path search algorithm that uses heuristics to estimate the most efficient path.

As it traverses the graph, A* estimates the total cost of a path using each node on the way to the target.

The best path is calculated by minimizing the function \(f(n)=g(n)+h(n)\), where:

\(n\) is the next node on the path
\(g(n)\) is the cost of the path from the source node to \(n\)
\(h(n)\) is a heuristic function that estimates the cost of the cheapest path from \(n\) to the target node.

The algorithm terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended. The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the target, the algorithm is guaranteed to return a least-cost path from source to target.

Notes

The A* algorithm is relatively inefficient in terms of worst-case time and space complexity.

Specifications

CREATE QUERY tg_astar(VERTEX source_vertex, VERTEX target_vertex,  SET<STRING> e_type_set, STRING weight_type,
STRING weight_attribute, BOOL display = False)

Parameters

Parameter Description Default value

Parameter	Description	Default value
`VERTEX source_vertex`	The source vertex to start from. Provide the vertex ID and type as a tuple: `("id","type")`	N/A
`VERTEX target_vertex`	The target vertex to end at.	N/A
`SET<STRING> e_type_set`	Edge types to traverse	(empty set of strings)
`STRING weight_type`	The data type of the edge weights, if applicable. (Must be one of `INT`, `FLOAT`, `DOUBLE` )	(empty string)
`STRING latitude`	One of a pair of attributes used to calculate distance.	(empty string)
`STRING longitude`	One of a pair of attributes used to calculate distance.	(empty string)
`STRING weight_attribute`	The attribute used as edge weight, if applicable	(empty string)
`BOOL display`	Whether to output edges for visualization	True

VERTEX source_vertex

The source vertex to start from. Provide the vertex ID and type as a tuple: ("id","type")

N/A

VERTEX target_vertex

The target vertex to end at.

N/A

SET<STRING> e_type_set

Edge types to traverse

(empty set of strings)

STRING weight_type

The data type of the edge weights, if applicable. (Must be one of INT, FLOAT, DOUBLE )

(empty string)

STRING latitude

One of a pair of attributes used to calculate distance.

(empty string)

STRING longitude

One of a pair of attributes used to calculate distance.

(empty string)

STRING weight_attribute

The attribute used as edge weight, if applicable

(empty string)

BOOL display

Whether to output edges for visualization

True

Output

Computes a shortest distance (in INT format) and shortest path (STRING) from the source to the target vertex.

Time complexity

This algorithm has a time complexity of \(O(V^2)\), where \(V\) is equal to the number of vertices.

Example

We run the tg_astar algorithm to find the shortest path between the source vertex "Kings Cross" and the target vertex "Kentish Town" on a graph which is a transport network of stations.

Each station has its geometric attibutes(i.e.latitude and longitude) and the edge weight represents the distance between stations in kilometers.

The heuristic function used to guide the search is the Haversine Formula, which computes the distance between two points on a sphere given their longitudes and latitudes.

# Use _ for default values
RUN QUERY astar(("Kings Cross","Station"), ("Kentish Town","Station"),["CONNECTION"], "FLOAT", "distance", _)

Below is the visualized result of the query: