PGX 20.1.1
Documentation

Bidirectional Dijkstra Algorithms

PGX has a bidirectional version of Dijkstra's algorithm to compute the shortest path between a given source and destination vertex. Although there is no theoretical difference, the bidirectional version performs better on many real-world graphs. As with the classic Dijkstra algorithm, PGX also has a filtered version of the bidirectional Dijkstra algorithm built in.


Bidirectional Dijkstra Algorithm

Category path finding

Algorithm ID pgx_builtin_p2_single_source_single_destination_bidirectional_dijkstra

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

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

Javadoc


This variant of the Dijkstra's algorithm searches for shortest path in two ways, it does a forward search from the source vertex and a backwards one from the destination vertex. If the path between the vertices exists, both searches will meet each other at an intermediate point.

Signature

Input Argument Type Comment
G graph
weight edgeProp edge property holding the (positive) weight of each edge in the graph.
src node the source vertex from the graph for the path.
dst node the destination vertex from the graph for the path.
Output Argument Type Comment
parent nodeProp vertex property holding the parent vertex of the each vertex in the shortest path.
parent_edge nodeProp 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.Scalar;
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 BidirectionalDijkstra {
  public boolean bidirectionalDijkstra(PgxGraph g, EdgeProperty<Double> weight, PgxVertex src, PgxVertex dst,
      @Out VertexProperty<PgxVertex> parent, @Out VertexProperty<PgxEdge> parentEdge) {
    if (g.getNumVertices() == 0) {
      return false;
    } else if (src == dst) {
      return true;
    }

    // Temporary data structures
    VertexProperty<PgxVertex> rParent = VertexProperty.create();
    VertexProperty<PgxEdge> rParentEdge = VertexProperty.create();
    VertexProperty<Boolean> fFinalized = VertexProperty.create();
    VertexProperty<Boolean> rFinalized = VertexProperty.create();
    VertexProperty<Double> fCost = VertexProperty.create();
    VertexProperty<Double> hCost = VertexProperty.create();
    PgxMap<PgxVertex, Double> fReachable = PgxMap.create();
    PgxMap<PgxVertex, Double> rReachable = PgxMap.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);
      rParent.set(n, PgxVertex.NONE);
      fFinalized.set(n, false);
      rFinalized.set(n, false);
      fCost.set(n, POSITIVE_INFINITY);
      hCost.set(n, POSITIVE_INFINITY);
    });

    fReachable.set(src, 0.0);
    rReachable.set(dst, 0.0);
    fCost.set(src, 0.0);
    hCost.set(dst, 0.0);

    Scalar<Double> curminfCost = Scalar.create(0.0);
    Scalar<Double> curminhCost = Scalar.create(0.0);
    double minCost = POSITIVE_INFINITY;
    double minUnitCost = 0.0; // This value is 1 for int version
    PgxVertex mid = PgxVertex.NONE;
    boolean terminate = false;
    while (!terminate && (fReachable.size() != 0) && (rReachable.size() != 0)) {
      if (fReachable.size() <= rReachable.size()) {
        PgxVertex fnext = fReachable.getKeyForMinValue();
        fReachable.remove(fnext);
        fFinalized.set(fnext, true);
        curminfCost.set(fCost.get(fnext));
        if (curminfCost.get() + curminhCost.get() + minUnitCost >= minCost) {
          terminate = true;
        }

        double fdist = fCost.get(fnext);
        fnext.getNeighbors().filter(v -> !fFinalized.get(v)).forSequential(v -> {
          PgxEdge e = v.edge();
          if (fdist + weight.get(e) + curminhCost.get() <= minCost) {
            if (fCost.get(v) > fdist + weight.get(e)) {
              fCost.set(v, fdist + weight.get(e));
              fReachable.set(v, fCost.get(v));
              parent.set(v, fnext);
              parentEdge.set(v, e);
              if (hCost.get(v) != POSITIVE_INFINITY) {
                double newCost = fCost.get(v) + hCost.get(v);
                updateMinValue(minCost, newCost).andUpdate(mid, v);
              }
            }
          }
        });
      } else {
        PgxVertex rnext = rReachable.getKeyForMinValue();
        rReachable.remove(rnext);
        rFinalized.set(rnext, true);
        curminhCost.set(hCost.get(rnext));
        if (curminfCost.get() + curminhCost.get() + minUnitCost >= minCost) {
          terminate = true;
        }

        double rdist = hCost.get(rnext);
        rnext.getInNeighbors().filter(v -> !rFinalized.get(v)).forSequential(v -> {
          PgxEdge e = v.edge();
          if (rdist + weight.get(e) + curminfCost.get() <= minCost) {
            if (hCost.get(v) > rdist + weight.get(e)) {
              hCost.set(v, rdist + weight.get(e));
              rReachable.set(v, hCost.get(v));
              rParent.set(v, rnext);
              rParentEdge.set(v, e);
              if (fCost.get(v) != POSITIVE_INFINITY) {
                double newCost = fCost.get(v) + hCost.get(v);
                updateMinValue(minCost, newCost).andUpdate(mid, v);
              }
            }
          }
        });
      }
    }

    // if a path was found
    if (mid != PgxVertex.NONE) {
      // Update the 'parent' and 'parentEdge' property of all the vertices in the
      // path from mid to dst
      PgxVertex cur = mid;
      while (cur != dst) {
        PgxVertex prev = rParent.get(cur);
        parent.set(prev, cur);
        parentEdge.set(prev, rParentEdge.get(cur));
        cur = prev;
      }
      return true;
    }
    // No path was found
    return false;
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure bidirectional_dijkstra(graph G, edgeProp<double> weight, node src, node dst;
    nodeProp<node> parent, nodeProp<edge> parent_edge) : bool {

  if (G.numNodes() == 0) {
    return false;
  } else if (src == dst) {
    return true;
  }

  // Temporary data structures
  nodeProp<node> r_parent;
  nodeProp<edge> r_parent_edge;
  nodeProp<bool> f_finalized;
  nodeProp<bool> r_finalized;
  nodeProp<double> f_cost;
  nodeProp<double> h_cost;
  map<node, double> f_reachable;
  map<node, double> r_reachable;

  // sequentially initialize, otherwise compiler flags this algorithm as parallel in nature
  for (n: G.nodes) {
    n.parent = NIL;
    n.parent_edge = NIL;
    n.r_parent = NIL;
    n.f_finalized = false;
    n.r_finalized = false;
    n.f_cost = +INF;
    n.h_cost = +INF;
  }
  f_reachable[src] = 0.0;
  r_reachable[dst] = 0.0;
  src.f_cost = 0.0;
  dst.h_cost = 0.0;

  /*
   *  Perform Dijkstra algorithm starting from src and dst
   *      one step at a time in one of the directions.
   *      Choose the direction with lesser frontier vertices for expansion.
   *  Store the shortest path found so far between src and dst in minCost.
   *  When minCost is < Lf + Lr, stop both the searches
   *      Lf is the min distance discovered in the latest forward search.
   *      Lr is the min distance discovered in the latest reverse search.
   *  After the first path between src and dst has been found, prune the
   *  search space as follows:
   *      Suppose you get vertex u from the Priority Queue in forward search
   *          and you are looking to expand u to a vertex v.
   *          if DistanceFromSrc(u) + weight(u,v) + Lr > minCost,
   *          do no expand to v.
   *      do the same in reverse search too.
   */
  double curMinf_cost = 0.0;
  double curMinh_cost = 0.0;
  double minCost = +INF;
  double minUnitCost = 0.0; // This value is 1 for int version
  node mid = NIL;
  bool terminate = false;
  while ( !terminate && (f_reachable.size() != 0) && (r_reachable.size() != 0) ) {

    if (f_reachable.size() <= r_reachable.size()) {
      node fnext = f_reachable.getMinKey();
      f_reachable.remove(fnext);
      fnext.f_finalized = true;
      curMinf_cost = fnext.f_cost;
      if (curMinf_cost + curMinh_cost + minUnitCost >= minCost) {
        terminate = true;
      }

      double fdist = fnext.f_cost;
      for (v: fnext.nbrs) (!v.f_finalized) {
        edge e = v.edge();
        if (fdist + e.weight + curMinh_cost <= minCost) {
          if (v.f_cost > fdist + e.weight) {
            v.f_cost = fdist + e.weight;
            f_reachable[v] = v.f_cost;
            v.parent = fnext;
            v.parent_edge = e;
            if (v.h_cost != +INF) {
              double newCost = v.f_cost + v.h_cost;
              <minCost; mid> min= <newCost; v>;
            }
          }
        }
      }
    } else {
      node rnext = r_reachable.getMinKey();
      r_reachable.remove(rnext);
      rnext.r_finalized = true;
      curMinh_cost = rnext.h_cost;
      if (curMinf_cost + curMinh_cost + minUnitCost >= minCost) {
        terminate = true;
      }

      double rdist = rnext.h_cost;
      for (v: rnext.inNbrs) (!v.r_finalized) {
        edge e = v.edge();
        if (rdist + e.weight + curMinf_cost <= minCost) {
          if (v.h_cost > rdist + e.weight) {
            v.h_cost = rdist + e.weight;
            r_reachable[v] = v.h_cost;
            v.r_parent = rnext;
            v.r_parent_edge = e;
            if (v.f_cost != +INF) {
              double newCost = v.f_cost + v.h_cost;
              <minCost; mid> min= <newCost; v>;
            }
          }
        }
      }
    }
  }

  // if a path was found
  if (mid != NIL) {
    // Update the 'parent' and 'parent_edge' property of all the vertices in the
    // path from mid to dst
    node cur = mid;
    while (cur != dst) {
      node prev = cur.r_parent;
      prev.parent = cur;
      prev.parent_edge = cur.r_parent_edge;
      cur = prev;
    }
    return true;
  }
  // No path was found
  return false;
}

Bidirectional Filtered Dijkstra Algorithm

Category path finding

Algorithm ID pgx_builtin_p2b_single_source_single_destination_filtered_bidirectional_dijkstra

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

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

Javadoc


This variant of the Dijkstra's algorithm searches for shortest path in two ways, it does a forward search from the source vertex and a backwards one from the destination vertex, while also adding the corresponding restrictions on the edges given by the filter expression. If the path between the vertices exists, both searches will meet each other at an intermediate point.

Signature

Input Argument Type Comment
G graph
weight edgeProp edge property holding the (positive) weight of each edge in the graph.
src node the source vertex from the graph for the path.
dst 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 nodeProp vertex property holding the parent vertex of the each vertex in the shortest path.
parent_edge nodeProp 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.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import oracle.pgx.algorithm.filter.EdgeFilter;

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

@GraphAlgorithm
public class BidirectionalDijkstraFilter {
  public boolean bidirectionalDijkstraFilter(PgxGraph g, EdgeProperty<Double> weight, PgxVertex src, PgxVertex dst,
      EdgeFilter filter, @Out VertexProperty<PgxVertex> parent, @Out VertexProperty<PgxEdge> parentEdge) {
    if (g.getNumVertices() == 0) {
      return false;
    }
    if (src == dst) {
      return true;
    }

    // Temporary data structures
    VertexProperty<PgxVertex> rParent = VertexProperty.create();
    VertexProperty<PgxEdge> rParentEdge = VertexProperty.create();
    VertexProperty<Boolean> fFinalized = VertexProperty.create();
    VertexProperty<Boolean> rFinalized = VertexProperty.create();
    VertexProperty<Double> fCost = VertexProperty.create();
    VertexProperty<Double> hCost = VertexProperty.create();
    PgxMap<PgxVertex, Double> fReachable = PgxMap.create();
    PgxMap<PgxVertex, Double> rReachable = PgxMap.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);
      rParent.set(n, PgxVertex.NONE);
      fFinalized.set(n, false);
      rFinalized.set(n, false);
      fCost.set(n, POSITIVE_INFINITY);
      hCost.set(n, POSITIVE_INFINITY);
    });

    fReachable.set(src, 0.0);
    rReachable.set(dst, 0.0);
    fCost.set(src, 0.0);
    hCost.set(dst, 0.0);

    Scalar<Double> curminfCost = Scalar.create(0.0);
    Scalar<Double> curminhCost = Scalar.create(0.0);
    double minCost = POSITIVE_INFINITY;
    double minUnitCost = 0.0; // This value is 1 for int version
    PgxVertex mid = PgxVertex.NONE;
    boolean terminate = false;
    while (!terminate && (fReachable.size() != 0) && (rReachable.size() != 0)) {
      if (fReachable.size() <= rReachable.size()) {
        PgxVertex fnext = fReachable.getKeyForMinValue();
        fReachable.remove(fnext);
        fFinalized.set(fnext, true);
        curminfCost.set(fCost.get(fnext));
        if (curminfCost.get() + curminhCost.get() + minUnitCost >= minCost) {
          terminate = true;
        }

        double fdist = fCost.get(fnext);
        fnext.getNeighbors().filter(v -> !fFinalized.get(v)).forSequential(v -> {
          PgxEdge e = v.edge();

          if (filter.evaluate(e)) {
            if (fdist + weight.get(e) + curminhCost.get() <= minCost) {
              if (fCost.get(v) > fdist + weight.get(e)) {
                fCost.set(v, fdist + weight.get(e));
                fReachable.set(v, fCost.get(v));
                parent.set(v, fnext);
                parentEdge.set(v, e);
                if (hCost.get(v) != POSITIVE_INFINITY) {
                  double newCost = fCost.get(v) + hCost.get(v);
                  updateMinValue(minCost, newCost).andUpdate(mid, v);
                }
              }
            }
          }
        });
      } else {
        PgxVertex rnext = rReachable.getKeyForMinValue();
        rReachable.remove(rnext);
        rFinalized.set(rnext, true);
        curminhCost.set(hCost.get(rnext));
        if (curminfCost.get() + curminhCost.get() + minUnitCost >= minCost) {
          terminate = true;
        }

        double rdist = hCost.get(rnext);
        rnext.getInNeighbors().filter(v -> !rFinalized.get(v)).forSequential(v -> {
          PgxEdge e = v.edge();

          if (filter.evaluate(e)) {
            if (rdist + weight.get(e) + curminfCost.get() <= minCost) {
              if (hCost.get(v) > rdist + weight.get(e)) {
                hCost.set(v, rdist + weight.get(e));
                rReachable.set(v, hCost.get(v));
                rParent.set(v, rnext);
                rParentEdge.set(v, e);
                if (fCost.get(v) != POSITIVE_INFINITY) {
                  double newCost = fCost.get(v) + hCost.get(v);
                  updateMinValue(minCost, newCost).andUpdate(mid, v);
                }
              }
            }
          }
        });
      }
    }

    // if a path was found
    if (mid != PgxVertex.NONE) {
      // Update the 'parent' and 'parentEdge' property of all the vertices in the
      // path from mid to dst
      PgxVertex cur = mid;
      while (cur != dst) {
        PgxVertex prev = rParent.get(cur);
        parent.set(prev, cur);
        parentEdge.set(prev, rParentEdge.get(cur));
        cur = prev;
      }
      return true;
    }
    // No path was found
    return false;
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure bidirectional_dijkstra_filter(graph G, edgeProp<double> weight, node src, node dst,
    edgeFilter filter; nodeProp<node> parent, nodeProp<edge> parent_edge) : bool {

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

  // Temporary data structures
  nodeProp<node> r_parent;
  nodeProp<edge> r_parent_edge;
  nodeProp<bool> f_finalized;
  nodeProp<bool> r_finalized;
  map<node, double> f_reachable;
  map<node, double> r_reachable;
  nodeProp<double> f_cost;
  nodeProp<double> r_cost;

  // Initializations
  G.parent = NIL;
  G.parent_edge = NIL;
  G.r_parent = NIL;
  G.f_finalized = false;
  G.r_finalized = false;
  G.f_cost = +INF;
  G.r_cost = +INF;
  f_reachable[src] = 0.0;
  r_reachable[dst] = 0.0;
  src.f_cost = 0.0;
  dst.r_cost = 0.0;

  // Same as Bidirectional Dijkstra algorithm but using a filter
  double curMinFCost = 0.0;
  double curMinRCost = 0.0;
  double minCost = +INF;
  double minUnitCost = 0.0;
  node mid = NIL;
  bool terminate = false;

  while (!terminate && (f_reachable.size() != 0) && (r_reachable.size() != 0)) {

    if (f_reachable.size() <= r_reachable.size()) {
      node fnext = f_reachable.getMinKey();
      f_reachable.remove(fnext);
      fnext.f_finalized = true;
      curMinFCost = fnext.f_cost;
      if (curMinFCost + curMinRCost + minUnitCost >= minCost) {
        terminate = true;
      }

      double fdist = fnext.f_cost;
      for(v: fnext.nbrs) (!v.f_finalized) {
        edge e = v.edge();

        if (filter.evaluate(e)) {
          if (fdist + e.weight + curMinRCost <= minCost) {
            if (v.f_cost > fdist + e.weight) {
              v.f_cost = fdist + e.weight;
              f_reachable[v] = v.f_cost;
              v.parent = fnext;
              v.parent_edge = e;
              if (v.r_cost != +INF) {
                double newCost = v.f_cost + v.r_cost;
                <minCost; mid> min= <newCost; v>;
              }
            }
          }
        }
      }
    } else {
      node rnext = r_reachable.getMinKey();
      r_reachable.remove(rnext);
      rnext.r_finalized = true;
      curMinRCost = rnext.r_cost;
      if (curMinFCost + curMinRCost + minUnitCost >= minCost) {
        terminate = true;
      }

      double rdist = rnext.r_cost;
      for(v: rnext.inNbrs) (!v.r_finalized) {
        edge e = v.edge();

        if (filter.evaluate(e)) {
          if (rdist + e.weight + curMinFCost <= minCost) {
            if (v.r_cost > rdist + e.weight) {
              v.r_cost = rdist + e.weight;
              r_reachable[v] = v.r_cost;
              v.r_parent = rnext;
              v.r_parent_edge = e;
              if (v.f_cost != +INF) {
                double newCost = v.f_cost + v.r_cost;
                <minCost; mid> min= <newCost; v>;
              }
            }
          }
        }
      }
    }
  }

  // if a path was found
  if (mid != NIL) {
    // Update the 'parent' and 'parent_edge' property of all the vertices in the
    // path from mid to dst
    node cur = mid;
    while (cur != dst) {
      node prev = cur.r_parent;
      prev.parent = cur;
      prev.parent_edge = cur.r_parent_edge;
      cur = prev;
    }
    return true;
  }

  // No path was found
  return false;
}