PGX 21.1.1
Documentation

Bellman-Ford Algorithms

PGX has two variants of this algorithm: the classic one which traverses the graph forward and a variant which traverses the graph backwards.

Classic Bellman-Ford

Categorypath findingAlgorithm IDpgx_builtin_p3_single_source_all_destinations_bellman_fordTime ComplexityO(V + E) with V = number of vertices, E = number of edgesSpace RequirementO(6 * V) with V = number of verticesJavadocAnalyst#shortestPathBellmanFord(PgxGraph graph, PgxVertex src, EdgeProperty cost) Analyst#shortestPathBellmanFord(PgxGraph graph, PgxVertex src, EdgeProperty cost, VertexProperty distance, VertexProperty> parent, VertexProperty parentEdge)

Bellman-Ford algorithm tries to find the shortest path (if there is one) between the given source and destination vertices, while minimizing the distance or cost associated to each edge in the graph.

Signature

Input Argument Type Comment
G graph
len edgeProp edge property holding the weight of each edge in the graph.
root node the source vertex from the graph for the path.
Output Argument Type Comment
dist vertexProp vertex property holding the distance to the source vertex for each vertex in the graph.
prev vertexProp vertex property holding the parent vertex of the each vertex in the shortest path.
prev_edge vertexProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.

Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.PgxVertex.NONE;
import static oracle.pgx.algorithm.Reduction.updateMinValue;
import static java.lang.Double.POSITIVE_INFINITY;

@GraphAlgorithm
public class BellmanFord {
public void bellmanFord(PgxGraph g, EdgeProperty<Double> len, PgxVertex root, @Out VertexProperty<Double> dist,
@Out VertexProperty<PgxVertex> prev, @Out VertexProperty<PgxEdge> prevEdge) {
VertexProperty<Boolean> updated = VertexProperty.create();
VertexProperty<Boolean> updatedNxt = VertexProperty.create();
VertexProperty<Double> distNxt = VertexProperty.create();
boolean done = false;

dist.setAll(v -> v == root ? 0.0 : POSITIVE_INFINITY);
updated.setAll(v -> v == root);
distNxt.setAll(dist::get);
updatedNxt.setAll(updated::get);
prev.setAll(NONE);
prevEdge.setAll(PgxEdge.NONE);

while (!done) {
g.getVertices().filter(updated).forEach(n -> {
n.getNeighbors().forEach(s -> {
PgxEdge e = s.edge(); // the edge to s
// updatedNxt becomes true only if distNxt is actually updated
updateMinValue(s, distNxt, dist.get(n) + len.get(e)).andUpdate(s, updatedNxt, true).andUpdate(s, prev, n)
.andUpdate(s, prevEdge, e);
});
});

dist.setAll(distNxt::get);
updated.setAll(updatedNxt::get);
updatedNxt.setAll(false);

done = !g.getVertices().anyMatch(updated::get);
}
}
}
```
```/*
*/

procedure bellman_ford(graph G, edgeProp<double> len, node root; vertexProp<double> dist,
vertexProp<node> prev, vertexProp<edge> prev_edge) {

vertexProp<bool> updated;
vertexProp<bool> updated_nxt;
vertexProp<double>  dist_nxt;
bool done = false;

G.dist = (_ == root) ? 0.0 : +INF;
G.updated = (_ == root) ? true : false;
G.dist_nxt = _.dist;
G.updated_nxt = _.updated;
G.prev = NIL;
G.prev_edge = NIL;

while (!done) {
done = true;

foreach (n: G.nodes) (n.updated) {
foreach (s: n.nbrs) {
edge e = s.edge(); // the edge to s
// updated_nxt becomes true only if dist_nxt is actually updated
<s.dist_nxt; s.updated_nxt, s.prev, s.prev_edge> min= <n.dist + e.len; true, n, e>;
}
}

G.dist = _.dist_nxt;
G.updated = _.updated_nxt;
G.updated_nxt = false;
done = !any (n: G.nodes) {n.updated};
}
}
```

(Backwards) Bellman-Ford Algorithm

Categorypath findingAlgorithm IDpgx_builtin_p3r_single_source_all_destinations_bellman_ford_reverseTime ComplexityO(V + E) with V = number of vertices, E = number of edgesSpace RequirementO(6 * V) with V = number of verticesJavadocAnalyst#shortestPathBellmanFordReverse(PgxGraph graph, PgxVertex src, EdgeProperty cost) Analyst#shortestPathBellmanFordReverse(PgxGraph graph, PgxVertex src, EdgeProperty cost, VertexProperty distance, VertexProperty> parent, VertexProperty parentEdge)

This variant of the Bellman-Ford algorithm tries to find the shortest path (if there is one) between the given source and destination vertices in a reversed fashion using the incoming edges instead of the outgoing, while minimizing the distance or cost associated to each edge in the graph.

Signature

Input Argument Type Comment
G graph
len edgeProp edge property holding the weight of each edge in the graph.
root node the source vertex from the graph for the path.
Output Argument Type Comment
dist vertexProp vertex property holding the distance to the source vertex for each vertex in the graph.
prev vertexProp vertex property holding the parent vertex of the each vertex in the shortest path.
prev_edge vertexProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.

Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Reduction.updateMinValue;
import static java.lang.Double.POSITIVE_INFINITY;

@GraphAlgorithm
public class BellmanFordBackward {
public void bellmanFordBackward(PgxGraph g, EdgeProperty<Double> len, PgxVertex root,
@Out VertexProperty<Double> dist, @Out VertexProperty<PgxVertex> prev, @Out VertexProperty<PgxEdge> prevEdge) {
VertexProperty<Boolean> updated = VertexProperty.create();
VertexProperty<Boolean> updatedNxt = VertexProperty.create();
VertexProperty<Double> distNxt = VertexProperty.create();
boolean done = false;

dist.setAll(v -> v == root ? 0.0 : POSITIVE_INFINITY);
updated.setAll(v -> v == root);
distNxt.setAll(dist::get);
updatedNxt.setAll(updated::get);
prev.setAll(PgxVertex.NONE);
prevEdge.setAll(PgxEdge.NONE);

while (!done) {
g.getVertices().filter(updated).forEach(n -> n.getInNeighbors().forEach(s -> {
PgxEdge e = s.edge(); // the edge to s
// updatedNxt becomes true only if distNxt is actually updated
updateMinValue(s, distNxt, dist.get(n) + len.get(e)).andUpdate(s, updatedNxt, true).andUpdate(s, prev, n)
.andUpdate(s, prevEdge, e);
}));

dist.setAll(distNxt::get);
updated.setAll(updatedNxt::get);
updatedNxt.setAll(false);

done = !g.getVertices().anyMatch(updated::get);
}
}
}
```
```/*
*/

procedure bellman_ford_backward(graph G, edgeProp<double> len, node root; vertexProp<double> dist,
vertexProp<node> prev, vertexProp<edge> prev_edge) {

vertexProp<bool> updated;
vertexProp<bool> updated_nxt;
vertexProp<double>  dist_nxt;
bool done = false;

G.dist = (_ == root) ? 0.0 : +INF;
G.updated = (_ == root) ? true: false;
G.dist_nxt = _.dist;
G.updated_nxt = _.updated;
G.prev = NIL;
G.prev_edge = NIL;

while (!done) {
done = true;

foreach (n: G.nodes) (n.updated) {
foreach (s: n.inNbrs) {
edge e = s.edge(); // the edge to s
// updated_nxt becomes true only if dist_nxt is actually updated
<s.dist_nxt; s.updated_nxt, s.prev, s.prev_edge> min= <n.dist + e.len; true, n, e>;
}
}

G.dist = _.dist_nxt;
G.updated = _.updated_nxt;
G.updated_nxt = false;
done = !any (n: G.nodes) {n.updated};
}
}
```