Path-finding algorithms in Neptune Analytics - Neptune Analytics
BFS algorithmsSSSP algorithms

Path-finding algorithms in Neptune Analytics

Path-finding algorithms are a category of graph algorithms that focus on finding a path, a connected set of nodes and edges, between two or more sets of nodes within a graph. They are often used to find available or optimized paths based on the existence, quantity, or quality of the paths and the values of properties along those paths.

By efficiently determining the best route between two nodes, path-finding algorithms enable you to model real-world systems like roads or social networks as interconnected nodes and edges. Finding the shortest paths between various points is crucial in applications like route planning for GPS systems, logistics optimization, and even in solving complex problems in fields like biology or engineering.

Breadth-first search (BFS) path finding algorithms

Breadth-first search (BFS) path-finding algorithms search for nodes in breadth-first order, starting from a single vertex. They can also, in the multi-source case, start from more than one vertex.

They can systematically explore and evaluates all neighboring nodes from a starting point before moving on to the neighbors of those nodes, which ensures that the algorithm searches the shallowest levels of the graph first.

Breadth-first-search is used in computer networking to find the shortest path between two devices, and in social networks to understand how information spreads through connections, and in games to explore possible moves and strategies.

Time complexity   –   The time complexity of breadth-first search algorithms is O(|V|+|E|), where |V| is the number of vertices in the graph and |E| is the number of edges in the graph.

A breadth-first algorithm can be invoked as a standalone operation whose inputs are explicitly defined, or as a query-algorithm integration which takes as its input the output of an immediately preceding MATCH clause.

Neptune Analytics supports these BFS algorithms:

  • .bfs   –   This standard breadth-first search algorithm starts from the source vertex of the graph and returns a column of visited vertices.

  • .bfs.parents   –   This variant of BFS starts from a source vertex or vertices and finds the parent of each vertex during the search. It returns a key column of the vertices and a value column of the parents of the key vertices.

  • .bfs.levels   –   This variant of BFS starts from a source vertex or vertices and finds the levels of each vertex during the search. It returns a key column of the vertices and a value column of integers that are the level values of the key vertices.

    Note that the level of a source vertex is 0.

Single-source shortest-path algorithms

A single-source-shortest-path algorithm finds the shortest paths (or the distance of the shortest paths) between a given vertex and all reachable vertices in the graph (including itself).

By determining the most efficient routes from a single starting node to all other nodes in the graph, single-source-shortest-path can be used calculate the shortest distances or lowest cost required to reach each destination. This is applicable in GPS systems to find the fastest routes between a starting point and differeent destinations, and in logistics to optimize delivery routes, and in transportation planning for efficient navigation through road networks.

Neptune Analytics supports the following single-source-shortest-path (SSSP) algorithms:

  • .sssp.bellmanFord   –   Computes the shortest path distances from a source vertex to all other vertices in the graph using the Bellman-Ford algorithm. Positive edge weights must be provided using the edgeWeightProperty, and the traversal direction must not be set to both.

  • .sssp.bellmanFord.parents   –   Identifies the parent vertices along the shortest paths from the source vertex to all other vertices in the graph using the Bellman-Ford algorithm. Positive edge weights must be provided using the edgeWeightProperty, and the traversal direction must not be set to both.

  • .sssp.bellmanFord.path   –   Finds the shortest path between a given source vertex and a target vertex in the graph using the Bellman-Ford algorithm. To compute all shortest paths from a given source vertex, the regular SSSP algorithm can be used. Positive edge weights must be provided using the edgeWeightProperty, and the traversal direction must not be set to both.

  • .sssp.deltaStepping   –   Computes the shortest path distances from a source vertex to all other vertices in the graph using a delta-stepping algorithm. Positive edge weights must be provided using the edgeWeightProperty, and the traversal direction must not be set to both.

  • .sssp.deltaStepping.parents   –   Identifies the parent vertices along the shortest paths from the source vertex to all other vertices in the graph using a delta-stepping algorithm. Positive edge weights must be provided using the edgeWeightProperty, and the traversal direction must not be set to both.

  • .sssp.deltaStepping.path   –   Finds the shortest path between a given source vertex and a target vertex in the graph using the delta-stepping algorithm. To compute all shortest paths from a given source vertex, the regular SSSP algorithm can be used. Positive edge weights must be provided using the edgeWeightProperty, and the traversal direction must not be set to both.

  • .topksssp   –   The TopK hop-limited single source shortest path algorithm finds the single-source weighted shortest paths starting from a source vertex to all its maxDepth neighbors. The distance or cost from the source vertex to each target vertex is accumulated on the edge weights of the path. The topK distances of the paths are sorted in descending or ascending order.

    The algorithm can be run unweighted as well as weighted. When you run it unweighted, it's equivalent to .bfs.levels.