Projected pathfinding

Wiki / Graph data science

Projected pathfinding

Use an existing projection; the source and targets must be selected projected nodes. See modes for write/mutate configuration.

  • gds.shortestPath.dijkstra
  • gds.shortestPath.astar
  • gds.shortestPath.yens
  • gds.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, or latitudeProperty with longitudeProperty) 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 + 1 exceeds 65,536 buckets, the frontiers use a heap instead of a ring; the answer is the same.
  • nodeIds are plain IDs. To get the nodes back, for example to draw the route, use gds.util.asNodes(nodeIds).

Graph projections and catalogue · GDS algorithms and execution modes · GDS resources and cancellation · Graph data science

Planning a deployment? Review compatibility and licence setup for your instance.