PGX 21.1.1
Documentation

Dijkstra Algorithms

Dijkstra's algorithm computes the shortest path between a given source and destination vertex. Besides the classic Dijkstra algorithm, PGX supports a filtered version of Dijkstra's algorithm, which operates on a filtered version of the graph, specified by a PGX filter expression argument.

Classic Dijkstra Algorithm

Category path finding

Algorithm ID pgx_builtin_p1a_single_source_single_destination_dijkstra

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

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

Javadoc

Dijkstra's 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
weight edgeProp edge property holding the (positive) weight of each edge in the graph.
root node the source vertex from the graph for the path.
dest node the destination vertex from the graph for the path.
Output Argument Type Comment
parent vertexProp vertex property holding the parent vertex of the each vertex in the shortest path.
parent_edge vertexProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.
Return Value Type Comment
bool true if there is a path connecting source and destination vertices, false otherwise

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.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class Dijkstra {
  public boolean dijkstra(PgxGraph g, EdgeProperty<Double> weight, PgxVertex root, PgxVertex dest,
      @Out VertexProperty<PgxVertex> parent, @Out VertexProperty<PgxEdge> parentEdge) {
    if (g.getNumVertices() == 0) {
      return false;
    }

    VertexProperty<Boolean> reached = VertexProperty.create();

    // sequentially initialize, otherwise compiler flags this algorithm as
    //parallel in nature
    g.getVertices().forSequential(n -> {
      parent.set(n, PgxVertex.NONE);
      parentEdge.set(n, PgxEdge.NONE);
      reached.set(n, false);
    });

    //-------------------------------
    // look up the vertex
    //-------------------------------
    PgxMap<PgxVertex, Double> reachable = PgxMap.create();
    reachable.set(root, 0d);

    //-------------------------------
    // look up the vertex
    //-------------------------------
    boolean found = false;
    boolean failed = false;

    while (!found && !failed) {
      if (reachable.size() == 0) {
        failed = true;
      } else {
        PgxVertex next = reachable.getKeyForMinValue();
        if (next == dest) {
          found = true;
        } else {
          reached.set(next, true);
          double dist = reachable.get(next);
          reachable.remove(next);
          next.getNeighbors().filter(v -> !reached.get(v)).forSequential(v -> {
            PgxEdge e = v.edge();
            if (!reachable.containsKey(v)) {
              reachable.set(v, dist + weight.get(e));
              parent.set(v, next);
              parentEdge.set(v, e);
            } else if (reachable.get(v) > dist + weight.get(e)) {
              reachable.set(v, dist + weight.get(e));
              parent.set(v, next);
              parentEdge.set(v, e);
            }
          });
        }
      }
    }

    // return false if not reachable
    return !failed;
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure dijkstra(graph G, edgeProp<double> weight, node root, node dest;
    vertexProp<node> parent, vertexProp<edge> parent_edge) : bool {

  if (G.numNodes() == 0) {
    return false;
  }

  vertexProp<bool> reached;

  // sequentially initialize, otherwise compiler flags this algorithm as
  //parallel in nature
  for (n: G.nodes) {
    n.parent = NIL;
    n.parent_edge = NIL;
    n.reached = false;
  }

  //-------------------------------
  // look up the vertex
  //-------------------------------
  map<node, double> reachable;
  reachable[root] = 0.0;            // Add root to reachable set

  //-------------------------------
  // look up the vertex
  //-------------------------------
  bool found = false;
  bool failed = false;
  while (!found && !failed) {

    if (reachable.size() == 0) {
      failed = true;
    }
    else {
      node next = reachable.getMinKey();
      if (next == dest)  {
        found = true;
      }
      else {
        next.reached = true;
        double dist = reachable[next];
        reachable.remove(next);
        for (v: next.nbrs) (!v.reached) {

          edge e = v.edge();
          if (!reachable.hasKey(v)) {
            reachable[v] = dist + e.weight;
            v.parent = next;
            v.parent_edge = e;
          }
          else if (reachable[v] > dist + e.weight) {
            reachable[v] = dist + e.weight;
            v.parent = next;
            v.parent_edge = e;
          }
        }
      }
    }
  }
  // return false if not reachable
  return !failed;
}

Filtered Dijkstra Algorithm

Category path finding

Algorithm ID pgx_builtin_p1b_single_source_single_destination_filtered_dijkstra

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

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

Javadoc

This variant of the Dijkstra's algorithm tries to find the shortest path while also taking into account a filter expression, which will add restrictions over the potential edges when looking for the shortest path between the source and destination vertices.

Signature

Input Argument Type Comment
G graph
weight edgeProp edge property holding the (positive) weight of each edge in the graph.
root node the source vertex from the graph for the path.
dest node the destination vertex from the graph for the path.
filter edgeFilter filter expression with conditions to be satisfied by the shortest path. If the expression is targeted to edges, it will be evaluated straight away. If the expression targets vertices, then it will be automatically translated into an equivalent edge expression by using the sources and/or the destinations of the edges from the current evaluated vertex, with exception of the source and destination vertices.
Output Argument Type Comment
parent vertexProp vertex property holding the parent vertex of the each vertex in the shortest path.
parent_edge vertexProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.
Return Value Type Comment
bool true if there is a path connecting source and destination vertices, false otherwise

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.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import oracle.pgx.algorithm.filter.EdgeFilter;

@GraphAlgorithm
public class DijkstraFiltered {
  public boolean dijkstra(PgxGraph g, EdgeProperty<Double> weight, PgxVertex root, PgxVertex dest, EdgeFilter filter,
      @Out VertexProperty<PgxVertex> parent, @Out VertexProperty<PgxEdge> parentEdge) {
    if (g.getNumVertices() == 0) {
      return false;
    }

    VertexProperty<Boolean> reached = VertexProperty.create();

    // sequentially initialize, otherwise compiler flags this algorithm as
    //parallel in nature
    g.getVertices().forSequential(n -> {
      parent.set(n, PgxVertex.NONE);
      parentEdge.set(n, PgxEdge.NONE);
      reached.set(n, false);
    });

    //-------------------------------
    // look up the vertex
    //-------------------------------
    PgxMap<PgxVertex, Double> reachable = PgxMap.create();
    reachable.set(root, 0d);

    //-------------------------------
    // look up the vertex
    //-------------------------------
    boolean found = false;
    boolean failed = false;

    while (!found && !failed) {
      if (reachable.size() == 0) {
        failed = true;
      } else {
        PgxVertex next = reachable.getKeyForMinValue();
        if (next == dest) {
          found = true;
        } else {
          reached.set(next, true);
          double dist = reachable.get(next);
          reachable.remove(next);

          next.getNeighbors().filter(v -> !reached.get(v)).forSequential(v -> {
            PgxEdge e = v.edge();

            if (filter.evaluate(e)) {
              if (!reachable.containsKey(v)) {
                reachable.set(v, dist + weight.get(e));
                parent.set(v, next);
                parentEdge.set(v, e);
              } else if (reachable.get(v) > dist + weight.get(e)) {
                reachable.set(v, dist + weight.get(e));
                parent.set(v, next);
                parentEdge.set(v, e);
              }
            }
          });
        }
      }
    }

    // return false if not reachable
    return !failed;
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure dijkstra_filter(graph G, edgeProp<double> weight, node root, node dest, edgeFilter filter;
    vertexProp<node> parent, vertexProp<edge> parent_edge) : bool {

  if (G.numNodes() == 0) {
    return false;
  }

  vertexProp<bool> reached;
  // sequentially initialize, otherwise compiler flags this algorithm as
  // parallel in nature
  for (n: G.nodes) {
    n.parent = NIL;
    n.parent_edge = NIL;
    n.reached = false;
  }

  map<node, double> reachable;
  reachable[root] = 0.0;

  bool found = false;
  bool failed = false;

  while (!found && !failed) {
    if (reachable.size() == 0) {
      failed = true;
    } else {
      node next = reachable.getMinKey();
      if (next == dest)  {
        found = true;
      } else {
        next.reached = true;
        double dist = reachable[next];
        reachable.remove(next);

        for (v: next.nbrs) (!v.reached) {
          edge e = v.edge();

          if (filter.evaluate(e)) {
            if (!reachable.hasKey(v)) {
              reachable[v] = dist + e.weight;
              v.parent = next;
              v.parent_edge = e;
            } else if (reachable[v] > dist + e.weight) {
              reachable[v] = dist + e.weight;
              v.parent = next;
              v.parent_edge = e;
            }
          }
        }
      }
    }
  }
  // return false if not reachable
  return !failed;
}