Skip to content

Shortest Paths

PuppyGraph provides six shortest path algorithms. Each one runs from Cypher as a CALL algo.shortestpath.* procedure, and from Gremlin as a program that you run with graph.program(...):

Algorithm Cypher procedure Gremlin program Finds Edge weights
Dijkstra's Algorithm algo.shortestpath.dijkstra LocalDijkstraShortestPathProgram The shortest path from one node to one target, or to every reachable node Zero or more
Yen's K-Shortest Paths algo.shortestpath.yenK LocalYenKShortestPathProgram Up to k shortest paths between two nodes Zero or more
Bellman-Ford Algorithm algo.shortestpath.bellmanFord LocalBellmanFordShortestPathProgram The shortest path from one node to one target, or to every reachable node Any, including negative
Delta-Stepping Algorithm algo.shortestpath.deltaStepping LocalDeltaSteppingShortestPathProgram The same as Dijkstra, using several threads Zero or more
Johnson's Algorithm algo.shortestpath.johnson LocalJohnsonShortestPathsProgram The shortest path between every pair of nodes Any, including negative (1.20.0 and later)
Breadth First Search algo.shortestpath.bfs LocalBFSShortestPathProgram The path with the fewest edges from one node to one target, or to every reachable node Not used

In Cypher, the shortestPath() and allShortestPaths() pattern functions also find the paths with the fewest edges between two nodes, inside a MATCH. See Path functions.

Running a shortest path algorithm

The examples on these pages use the Modern example graph. To load it, follow Explore the Example Graph.

From Cypher

Version requirement

Calling the shortest path algorithms from Cypher is available in PuppyGraph 1.20.0 and later.

Call the procedure with one map of arguments, then YIELD the output fields you need:

CALL algo.shortestpath.dijkstra({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    relationshipWeightProperty: 'weight',
    sourceNode: 'person[v1]',
    targetNode: 'software[v5]'
    }) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight

Run it on the Query page of the Web UI, or from any Cypher client (see Querying using openCypher).

  • labels and relationshipTypes are required, so a call loads only the part of the graph it needs.
  • An argument the procedure does not take fails the query with unknown argument(s) and the list of valid arguments, even when its value is null.
  • Arguments must be literal values or query parameters, such as sourceNode: $source. They cannot refer to variables from an earlier MATCH.

A Cypher call returns at most 2,000 paths. A call that finds more fails with algo.shortestpath.<name> found more than 2000 paths, the most a Cypher call returns. The rest of the message lists the arguments that narrow that procedure. Every procedure takes labels, relationshipTypes, excludeNodeIds and excludeRelationshipIds. Dijkstra, Bellman-Ford, Delta-Stepping and BFS also take targetNode, BFS takes maxHop, and Yen's takes a smaller k. Johnson's returns every reachable pair, so narrow it with the first four. To get more paths, run the algorithm from Gremlin.

vertexList and edgeList hold node and edge IDs. To read the nodes' properties, match each ID. step keeps the nodes in path order:

CALL algo.shortestpath.dijkstra({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    relationshipWeightProperty: 'weight',
    sourceNode: 'person[v1]',
    targetNode: 'software[v5]'
    }) YIELD vertexList
UNWIND range(0, size(vertexList) - 1) AS step
WITH step, vertexList[step] AS nodeId
MATCH (n) WHERE id(n) = nodeId
RETURN step, n.name AS name
ORDER BY step

Output:

[
  {"step": 0, "name": "marko"},
  {"step": 1, "name": "josh"},
  {"step": 2, "name": "ripple"}
]

From Gremlin

Build the program, then run it with submitAndGetLocal().getMapResult():

graph.program(
  LocalDijkstraShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("person[v1]")
    .sink("software[v5]")
    .create()
).submitAndGetLocal().getMapResult()

Run it on the Query page of the Web UI, or from any Gremlin client (see Querying using Gremlin).

A program reads the nodes and edges it needs from your data sources and returns its results to the client. It does not write to the graph or to your data sources. Two calls that work with other graph algorithms do not work here:

  • submitAndGet() fails with use submitAndGetLocal to get result of local program.
  • submitAndSave(...) fails with saving result of local program is not supported, so the results cannot be exported to object storage.

Node and edge IDs

sourceNode, targetNode, excludeNodeIds and excludeRelationshipIds in Cypher, and source(...), sink(...), excludeVertexIds(...) and excludeEdgeIds(...) in Gremlin, take IDs in the form label[id], the same form that id() returns in Cypher and Gremlin. In the Modern example graph, marko is person[v1] and the edge from marko to josh is knows[e8]. To look up an ID:

MATCH (n:person {name: 'marko'}) RETURN id(n)
// person[v1]
g.V().has("person", "name", "marko").id()
// person[v1]

Output

Each result is one path, with these fields:

Field Description
vertexList The IDs of the nodes on the path, in order from the source
edgeList The IDs of the edges on the path, in order from the source
edgeResultList Gremlin only. One entry per edge, with its id and its from and to nodes
weight The path length: the sum of the edge weights, or the number of edges for breadth-first search

from and to always show the edge's stored direction. When an algorithm treats edges as undirected (undirected: true or asUndirected(true)), a path can walk an edge backwards, so vertexList can show to before from.

A program that searches from one source to every node returns one path for each node it can reach, and leaves out the source and the nodes it cannot reach. These paths are not sorted, and their order can differ between runs. When no path exists to a sink, the result is an empty list.

Common arguments

Every shortest path algorithm accepts these arguments, along with the ones on its own page. Breadth-first search counts edges instead of adding weights, so it takes none of relationshipWeightProperty, fixedPenalty and penaltyProperty. In Cypher, passing one to algo.shortestpath.bfs fails as an unknown argument.

Cypher argument Gremlin method Description Default
labels vertices(String... labels) The node labels to load Required in Cypher. All node labels in Gremlin
relationshipTypes edges(String... labels) The edge labels to load. An edge is loaded only when both of its nodes are loaded Required in Cypher. All edge labels in Gremlin
relationshipWeightProperty weightProperty(String name) The numeric edge property to use as the weight. Required by every algorithm except breadth-first search, which does not take it None
excludeNodeIds excludeVertexIds(String... ids) Node IDs to leave out, together with their edges None
excludeRelationshipIds excludeEdgeIds(String... ids) Edge IDs to leave out None
fixedPenalty fixedPenalty(double penalty) A number added to the weight of every edge. Not for breadth-first search 0.0
penaltyProperty penaltyProperty(String name) A numeric edge property added to each edge's weight. An edge without the property gets no penalty. Not for breadth-first search None
create() Checks the settings and returns the program

In Gremlin, fixedPenalty and penaltyProperty replace each other: the one called last applies. In Cypher, a call can set only one of them.

If the weight property is not set, the run fails with Edge weight property is required. in Gremlin, or algo.shortestpath.<name>: `relationshipWeightProperty` is required in Cypher. If an edge in the loaded labels has no value for the property, or a value that is not a number, the run fails with Edge weight property type is not compatible with double. If the source or target node is not among the loaded nodes, the run fails with Graph must contain the source vertex! or Graph must contain the sink vertex!.

Sizing for large graphs

Each run loads the selected nodes and edges into memory on the PuppyGraph server that receives the query, then runs the algorithm there. Memory use and run time grow with the number of nodes and edges loaded, and with the number of paths returned.

  • Name only the labels the path can use, in labels and relationshipTypes (Cypher) or vertices(...) and edges(...) (Gremlin). Without them, a Gremlin program loads every node and edge in the graph.
  • Set a target (targetNode or sink) when you need one path. Without one, Dijkstra, Bellman-Ford, Delta-Stepping and breadth-first search return a path to every node they can reach.
  • Use maxHop on breadth-first search to stop the search after a number of edges.
  • Avoid Johnson's algorithm on large graphs. It returns a path for every pair of connected nodes, so a graph with N nodes can return close to N × N paths. To find paths from a few sources, run Dijkstra once per source, or Bellman-Ford if weights can be negative.

Reusing the loaded graph

By default, PuppyGraph keeps the nodes and edges a run loaded and reuses them for later runs that load the same labels with the same weight property, penalty and direction. A later run then skips reading the data sources.

A reused graph does not show changes made to your data after it was loaded. It is replaced when the graph schema or a catalog changes, and expires 24 hours after it was loaded. To change this, set these options in the GRAPH_FEATURES environment variable when you start PuppyGraph, separated by commas:

Option Description Default
feature.engine.enableGraphCache Set to false to read the data sources on every run true
feature.engine.graphCacheExpireMinutes Minutes until a reused graph expires 1440

For example, with Docker:

docker run ... -e GRAPH_FEATURES=feature.engine.enableGraphCache:false puppygraph/puppygraph:latest

A graph is never reused, whatever these options say, when row-level security filters any of its tables, or when it reads from a catalog that runs queries as the signed-in user (for example, Snowflake with SSO impersonation). Each run then reads the data the caller is allowed to see.

Row-level security

Version requirement

Running graph algorithms on a graph with row-level security is available in PuppyGraph 1.15.0 and later.

A shortest path algorithm runs as the user who submits it, from Cypher or Gremlin. When row-level security is on, it loads only the rows that user is entitled to, so its paths never pass through a node or edge the user cannot see. A service account that impersonates a user gets that user's results.

A source or target node the user cannot see fails in the same way as one that does not exist: Graph must contain the source vertex! or Graph must contain the sink vertex!.