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