Skip to content

Delta-Stepping Algorithm

Introduction

The Delta-Stepping algorithm finds the same shortest paths as Dijkstra's algorithm, but splits the work across several threads. With a sink, it returns the shortest path to that node. Without one, it returns the shortest path to every node the source can reach.

The program follows edges in their stored direction only. Edge weights must be zero or more. A negative weight fails the run with Negative edge weight not allowed.

Run Delta-Stepping from Cypher with CALL algo.shortestpath.deltaStepping, or from Gremlin with LocalDeltaSteppingShortestPathProgram. See Shortest Paths for how to run it, the output fields, the arguments shared by all shortest path algorithms, and sizing guidance.

Query Example

The shortest paths from marko (person[v1]) to every node he can reach in the Modern example graph. The Gremlin example runs on two threads. Cypher always runs on four:

CALL algo.shortestpath.deltaStepping({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    relationshipWeightProperty: 'weight',
    sourceNode: 'person[v1]',
    delta: 0.5
    }) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
ORDER BY weight

Output:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "weight": 0.4
  },
  {
    "vertexList": ["person[v1]", "person[v2]"],
    "edgeList": ["knows[e7]"],
    "weight": 0.5
  },
  {
    "vertexList": ["person[v1]", "person[v4]"],
    "edgeList": ["knows[e8]"],
    "weight": 1.0
  },
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e8]", "created[e10]"],
    "weight": 2.0
  }
]
graph.program(
  LocalDeltaSteppingShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("person[v1]")
    .delta(0.5)
    .parallelism(2)
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v1]", "person[v4]"],
    "edgeList": ["knows[e8]"],
    "edgeResultList": [{"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"}],
    "weight": 1.0
  },
  {
    "vertexList": ["person[v1]", "person[v2]"],
    "edgeList": ["knows[e7]"],
    "edgeResultList": [{"id": "knows[e7]", "from": "person[v1]", "to": "person[v2]"}],
    "weight": 0.5
  },
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e8]", "created[e10]"],
    "edgeResultList": [
      {"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"},
      {"id": "created[e10]", "from": "person[v4]", "to": "software[v5]"}
    ],
    "weight": 2.0
  },
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
    "weight": 0.4
  }
]

Parameters

Cypher argument Gremlin method Description Required Default Value
sourceNode source(String id) The ID of the node to start from Yes
targetNode sink(String id) The ID of the target node. Without it, the program returns a path to every reachable node No
delta delta(double delta) The width of the weight ranges the algorithm processes in one step. Must be 0 or more. With 0, PuppyGraph picks a value from the edge weights No 0.0
Not available: Cypher uses 4 threads parallelism(int threads) The number of threads to use. Must be greater than 0 No 4
relationshipWeightProperty weightProperty(String name) The edge property to use as the weight Yes

The common arguments also apply.

delta changes only how long the run takes, not the paths it returns. A small delta gives each step little work, and a large one makes the algorithm behave more like Bellman-Ford. The default suits most graphs.