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

##### Categorypath findingAlgorithm IDpgx_builtin_p2_single_source_single_destination_bidirectional_dijkstraTime ComplexityO(E + V log V) with V = number of vertices, E = number of edgesSpace RequirementO(10 * V) with V = number of verticesJavadocAnalyst#shortestPathDijkstraBidirectional(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost) Analyst#shortestPathDijkstraBidirectional(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost, VertexProperty> parent, VertexProperty parentEdge)

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 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.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;
vertexProp<node> parent, vertexProp<edge> parent_edge) : bool {

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

// Temporary data structures
vertexProp<node> r_parent;
vertexProp<edge> r_parent_edge;
vertexProp<bool> f_finalized;
vertexProp<bool> r_finalized;
vertexProp<double> f_cost;
vertexProp<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

##### Categorypath findingAlgorithm IDpgx_builtin_p2b_single_source_single_destination_filtered_bidirectional_dijkstraTime ComplexityO(E + V log V) with V = number of vertices, E = number of edgesSpace RequirementO(10 * V) with V = number of verticesJavadocAnalyst#shortestPathFilteredDijkstraBidirectional(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost, GraphFilter filterExpr) Analyst#shortestPathFilteredDijkstraBidirectional(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost, GraphFilter filterExpr, VertexProperty> parent, VertexProperty parentEdge)

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 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.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; vertexProp<node> parent, vertexProp<edge> parent_edge) : bool {

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

// Temporary data structures
vertexProp<node> r_parent;
vertexProp<edge> r_parent_edge;
vertexProp<bool> f_finalized;
vertexProp<bool> r_finalized;
map<node, double> f_reachable;
map<node, double> r_reachable;
vertexProp<double> f_cost;
vertexProp<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;
}