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.