PGX 20.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

Category path finding

Algorithm ID pgx_builtin_p3_single_source_all_destinations_bellman_ford

Time Complexity O(V + E) with V = number of vertices, E = number of edges

Space Requirement O(6 * V) with V = number of vertices

Javadoc


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 nodeProp vertex property holding the distance to the source vertex for each vertex in the graph.
prev nodeProp vertex property holding the parent vertex of the each vertex in the shortest path.
prev_edge nodeProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
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);
    }
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

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

  nodeProp<bool> updated;
  nodeProp<bool> updated_nxt;
  nodeProp<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

Category path finding

Algorithm ID pgx_builtin_p3r_single_source_all_destinations_bellman_ford_reverse

Time Complexity O(V + E) with V = number of vertices, E = number of edges

Space Requirement O(6 * V) with V = number of vertices

Javadoc


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 nodeProp vertex property holding the distance to the source vertex for each vertex in the graph.
prev nodeProp vertex property holding the parent vertex of the each vertex in the shortest path.
prev_edge nodeProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
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);
    }
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

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

  nodeProp<bool> updated;
  nodeProp<bool> updated_nxt;
  nodeProp<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};
  }
}