Projected pathfinding
Projected pathfinding
Use an existing projection; the source and targets must be selected projected nodes. See modes for write/mutate configuration.
gds.shortestPath.dijkstragds.shortestPath.astargds.shortestPath.yensgds.allShortestPaths.dijkstra(single-source distances/paths)gdb.shortestPath.hourglass(Galactus; see Hourglass)
Each has stream, stats, write and mutate entry points. Specify
sourceNode, targetNode or targetNodes, and optionally
relationshipWeightProperty. The single-source procedure visits every reachable
target using a single Dijkstra tree, also reused for multi-target Dijkstra.
Dijkstra with a single targetNode stops as soon as it reaches the target, and
each projection keeps the weighted adjacency it builds for later calls (from
version 2.1.8).
Returned paths still require memory proportional to their total length.
Yen additionally takes positive k and enumerates distinct simple node
paths in cost order. Parallel edges with the same endpoints are not treated as
separate Yen paths. A* needs a location for every projected node: either numeric
latitudeProperty and longitudeProperty, or pointProperty naming a
Point, Geometry or Geography POINT property (one or the other, not both;
all geographic or all cartesian; pointProperty from version 1.6.2). Its
straight-line heuristic is scaled to the
cheapest cost per unit of distance over all edges, so weights in any unit
cannot invalidate shortest-path correctness.
Stream columns are index, sourceNode, targetNode, totalCost, nodeIds, costs, path. Paths use virtual PATH relationships with per-step costs. Unreachable
targets return no row. A source equal to its target returns a zero-cost path.
Write/mutate create source-to-target summary relationships, with the property
defaulting to totalCost; they do not rewrite the traversed relationships.
Hourglass
gdb.shortestPath.hourglass is Ian Knowles's exact point-to-point algorithm
(paper and reference code, MIT).
It searches from both ends at once, leans both searches towards each other
with whole-number potentials built from the straight-line distance, and keeps
its frontiers in bucket rings instead of a sorted heap. It has the same
stream, stats, write and mutate modes, configuration and columns as A*. From
version 1.6.2.
MATCH (a:City {name:'Exeter'}), (b:City {name:'Newcastle'})
CALL gdb.shortestPath.hourglass.stream('roads', {
sourceNode: a, targetNode: b,
relationshipWeightProperty: 'km', pointProperty: 'loc'
})
YIELD totalCost, nodeIds
RETURN totalCost, nodeIds;
- Relationship weights must be whole numbers from 0 to 2^40. Use Dijkstra or A* for fractional weights.
- A location (
pointProperty, orlatitudePropertywithlongitudeProperty) is optional. Without one it is a bidirectional bucket search, still exact. - Directed projections are supported: the backward search follows the relationships in reverse.
- When
4 × max weight + 1exceeds 65,536 buckets, the frontiers use a heap instead of a ring; the answer is the same. nodeIdsare plain IDs. To get the nodes back, for example to draw the route, usegds.util.asNodes(nodeIds).
Related articles
Graph projections and catalogue · GDS algorithms and execution modes · GDS resources and cancellation · Graph data science