 PGX 21.1.1
Documentation

# Hop Distance Algorithms

Hop Distance algorithms compute the shortest path from a single source vertex to all other vertices in the graph. But unlike the classic Bellman Ford algorithm, they use the hop distance as path length instead of the edge cost/weight. PGX has two variants of this algorithm: one which traverses the graph forward and a variant which traverses the graph backwards.

## Hop Distance

##### Categorypath findingAlgorithm IDpgx_builtin_p4_single_source_all_destinations_hop_distanceTime ComplexityO(V + E) with V = number of vertices, E = number of edgesSpace RequirementO(3 * V) with V = number of verticesJavadocAnalyst#shortestPathHopDist(PgxGraph graph, PgxVertex src) Analyst#shortestPathHopDist(PgxGraph graph, PgxVertex src, VertexProperty distance, VertexProperty> parent, VertexProperty parentEdge)

The Hop distance of two vertices S and V in a graph is the number of edges that are in a shortest path connecting them. This algorithm will return the distance of each vertex with respect to the given source vertex in the input and will also return the parent vertex and linking edge for each vertex. The returned information allows to trace back shortest paths from any reachable vertex to the source vertex.

### Signature

Input Argument Type Comment
G graph
root node the source vertex from the graph for the path.
Output Argument Type Comment
dist vertexProp vertex property holding the hop 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.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.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class HopDistance {
public void hopDist(PgxGraph g, PgxVertex root, @Out VertexProperty<Double> dist, @Out VertexProperty<PgxVertex> prev,
@Out VertexProperty<PgxEdge> prevEdge) {
if (g.getNumVertices() == 0) {
return;
}

dist.setAll(Double.POSITIVE_INFINITY);
prev.setAll(PgxVertex.NONE);
prevEdge.setAll(PgxEdge.NONE);
dist.set(root, 0d);

inBFS(g, root).forward(n -> {
dist.set(n, (double) currentLevel());
prev.set(n, n.parentVertex());
prevEdge.set(n, n.parentEdge());
});
}
}
```
```/*
*/

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

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

G.dist = +INF;
G.prev = NIL;
G.prev_edge = NIL;
root.dist = 0;
root.prev = NIL;
root.prev_edge = NIL;

inBFS (n: G.nodes from root) {
n.dist = currentBFSLevel();
n.prev = n.BFSParentNode();
n.prev_edge = n.BFSParentEdge();
}

}
```

## Hop Distance (Backwards)

##### Categorypath findingAlgorithm IDpgx_builtin_p4r_single_source_all_destinations_hop_distance_reverseTime ComplexityO(V + E) with V = number of vertices, E = number of edgesSpace RequirementO(3 * V) with V = number of verticesJavadocAnalyst#shortestPathHopDistReverse(PgxGraph graph, PgxVertex src) Analyst#shortestPathHopDistReverse(PgxGraph graph, PgxVertex src, VertexProperty distance, VertexProperty> parent, VertexProperty parentEdge)

The Hop distance of two vertices S and V in a graph is the number of edges that are in a shortest path connecting them. This algorithm will return the distance of each node with respect to the given source node in the input and will also return the parent node and linking edge for each node. The returned information allows to trace back shortest paths from any reachable node to the source node.

### Signature

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

### Code

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

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.Traversal.Direction.IN_EDGES;
import static oracle.pgx.algorithm.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class HopDistanceBackward {
public void hopDistBackward(PgxGraph g, PgxVertex root, @Out VertexProperty<Double> dist,
@Out VertexProperty<PgxVertex> prev, @Out VertexProperty<PgxEdge> prevEdge) {
if (g.getNumVertices() == 0) {
return;
}

dist.setAll(Double.POSITIVE_INFINITY);
prev.setAll(PgxVertex.NONE);
prevEdge.setAll(PgxEdge.NONE);
dist.set(root, 0d);

inBFS(g, root).forward(n -> {
dist.set(n, (double) currentLevel());
prev.set(n, n.parentVertex());
prevEdge.set(n, n.parentEdge());
}).direction(IN_EDGES);
}
}
```
```/*
*/

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

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

G.dist = +INF;
G.prev = NIL;
G.prev_edge = NIL;
root.dist = 0;
root.prev = NIL;
root.prev_edge = NIL;

inBFS (n: G.nodes from root using inEdges) {
n.dist = currentBFSLevel();
n.prev = n.BFSParentNode();
n.prev_edge = n.BFSParentEdge();
}
}
```