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

Category path finding

Algorithm ID pgx_builtin_p4_single_source_all_destinations_hop_distance

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

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

Javadoc

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

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

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

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)

Category path finding

Algorithm ID pgx_builtin_p4r_single_source_all_destinations_hop_distance_reverse

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

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

Javadoc

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

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

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

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();
  }
}