These algorithms can be regarded as a light-weight connectivity test. The algorithms will return the hop distance between two vertices if there is a path linking them.
This algorithm tries to find if the destination vertex is reachable given the source vertex and the maximum hop distance set by the user. The search can be performed in a directed or undirected way. These options may lead to different hop distances, since an undirected search has less restrictions on the possible paths connecting vertices than the directed option. Hence hop distances from an undirected search can be smaller than the ones from the directed cases.
Input Argument | Type | Comment |
---|---|---|
G | graph | |
source | node | source vertex for the search. |
dest | node | destination vertex for the search. |
maxHops | int | maximum hop distance between the source and destination vertices. |
Return Value | Type | Comment |
---|---|---|
int | the number of hops between the vertices. It will return -1 if the vertices are not connected or are not reachable given the condition of the maximum hop distance allowed. |
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ package oracle.pgx.algorithms; import oracle.pgx.algorithm.PgxGraph; import oracle.pgx.algorithm.PgxVertex; import oracle.pgx.algorithm.Scalar; import oracle.pgx.algorithm.annotations.GraphAlgorithm; import static oracle.pgx.algorithm.ControlFlow.exit; import static oracle.pgx.algorithm.Traversal.currentLevel; import static oracle.pgx.algorithm.Traversal.inBFS; import static oracle.pgx.algorithm.Traversal.stopTraversal; @GraphAlgorithm public class Reachability { public int reachability(PgxGraph g, PgxVertex source, PgxVertex dest, int maxHops) { Scalar<Boolean> giveup = Scalar.create(false); int threshold = 10000000; // 0 hop if (source == dest) { return 0; } else if (maxHops == 0) { return -1; } // 1 hop if (source.hasEdgeTo(dest)) { return 1; } else if (maxHops == 1) { return -1; } Scalar<Integer> s = Scalar.create(0); // 2, 3, 4 hop source.getNeighbors().filter(l1 -> !giveup.get()).forSequential(l1 -> { s.increment(); if (s.get() >= threshold) { giveup.set(true); } l1.getNeighbors().filter(l2 -> !giveup.get()).forSequential(l2 -> { if (l2 == dest) { exit(2); } s.increment(); if (s.get() >= threshold) { giveup.set(true); } if (!giveup.get() && maxHops >= 3) { l2.getNeighbors().filter(l3 -> !giveup.get()).forSequential(l3 -> { if (l3 == dest) { exit(3); } s.increment(); if (s.get() >= threshold) { giveup.set(true); } if (!giveup.get() && maxHops >= 4) { l3.getNeighbors().filter(l4 -> !giveup.get()).forSequential(l4 -> { if (l4 == dest) { exit(4); } s.increment(); if (s.get() >= threshold) { giveup.set(true); } }); } }); } }); }); if (!giveup.get() && maxHops <= 4) { return -1; } Scalar<Integer> found = Scalar.create(-1); inBFS(g, source) // .filter(n -> found.get() == -1) // .navigator(n -> (found.get() == -1) && currentLevel() < maxHops) // .forward(n -> { if (n == dest) { found.set(currentLevel()); stopTraversal(); } }); return found.get(); } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ procedure reachability(graph G, node source, node dest, int maxHops) : int { bool giveup = false; int threshold = 10000000; // 0 hop if (source == dest) { return 0; } else if (maxHops == 0) { return -1; } // 1 hop if (source.hasEdgeTo(dest)) { return 1; } else if (maxHops == 1) { return -1; } int s = 0; // 2, 3, 4 hop for (l1: source.nbrs) (!giveup) { s++; if (s >= threshold) { giveup = true; } for (l2: l1.nbrs) (!giveup) { if (l2 == dest) { return 2; } s++; if (s >= threshold) { giveup = true; } if (!giveup && maxHops >= 3) { for (l3: l2.nbrs) (!giveup) { if (l3 == dest) { return 3; } s++; if (s >= threshold) { giveup = true; } if (!giveup && maxHops >= 4) { for (l4: l3.nbrs) (!giveup) { if (l4 == dest) { return 4; } s++; if (s >= threshold) { giveup = true; } } } } } } } if (!giveup && maxHops <= 4) { return -1; } int found = -1; inBFS (n: G.nodes from source) (found == -1) [(found == -1) && currentBFSLevel() < maxHops] { if (n == dest) { found = currentBFSLevel(); stopBFS(); } } return found; }
This algorithm tries to find if the destination vertex is reachable given the source vertex and the maximum hop distance set by the user. The search can be performed in a directed or undirected way. These options may lead to different hop distances, since an undirected search has less restrictions on the possible paths connecting vertices than the directed option. Hence hop distances from an undirected search can be smaller than the ones from the directed cases.
Input Argument | Type | Comment |
---|---|---|
G | graph | |
source | node | source vertex for the search. |
dest | node | destination vertex for the search. |
maxHops | int | maximum hop distance between the source and destination vertices. |
Return Value | Type | Comment |
---|---|---|
int | the number of hops between the vertices. It will return -1 if the vertices are not connected or are not reachable given the condition of the maximum hop distance allowed. |
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ package oracle.pgx.algorithms; import oracle.pgx.algorithm.ControlFlow; import oracle.pgx.algorithm.PgxGraph; import oracle.pgx.algorithm.PgxVertex; import oracle.pgx.algorithm.Scalar; import oracle.pgx.algorithm.annotations.GraphAlgorithm; import static oracle.pgx.algorithm.Traversal.Direction.IN_OUT_EDGES; import static oracle.pgx.algorithm.Traversal.currentLevel; import static oracle.pgx.algorithm.Traversal.inBFS; import static oracle.pgx.algorithm.Traversal.stopTraversal; @GraphAlgorithm public class ReachabilityUndirected { public int reachabilityUndirected(PgxGraph g, PgxVertex source, PgxVertex dest, int maxHops) { int threshold = 10000000; Scalar<PgxVertex> src = Scalar.create(source); Scalar<PgxVertex> dst = Scalar.create(dest); if (src.get().getInDegree() + src.get().getOutDegree() > dst.get().getInDegree() + dst.get().getOutDegree()) { PgxVertex temp = src.get(); src.set(dst.get()); dst.set(temp); } // Specialized for fast up-to-3-hop finding // Not for general cases // 0 hop if (src == dst) { return 0; } else if (maxHops == 0) { return -1; } // 1 hop if (src.get().hasEdgeTo(dst.get()) || src.get().hasEdgeFrom(dst.get())) { return 1; } else if (maxHops == 1) { return -1; } Scalar<Integer> s = Scalar.create(0); // 2 hop { Scalar<PgxVertex> last1 = Scalar.create(src.get()); src.get().getOutNeighbors().filter(l1 -> (l1 != last1.get() && l1 != src.get())).forSequential(l1 -> { last1.set(l1); s.increment(); if (l1.hasEdgeTo(dst.get()) || l1.hasEdgeFrom(dst.get())) { ControlFlow.exit(2); } }); last1.set(src.get()); src.get().getInNeighbors().filter(l1 -> l1 != last1.get() && l1 != src.get()).forSequential(l1 -> { last1.set(l1); s.increment(); if (l1.hasEdgeTo(dst.get()) || l1.hasEdgeFrom(dst.get())) { ControlFlow.exit(2); } }); } if (maxHops == 2) { return -1; } // 3 hop (L1-OUT) if (s.get() < threshold) { Scalar<PgxVertex> last1 = Scalar.create(src.get()); src.get().getOutNeighbors().filter(l1 -> s.get() < threshold && l1 != last1.get() && l1 != src.get()) .forSequential(l1 -> { last1.set(l1); s.increment(); if (s.get() < threshold) { Scalar<PgxVertex> last2 = Scalar.create(l1); l1.getOutNeighbors().filter(l2 -> s.get() < threshold && l2 != last2.get() && l2 != l1 && l2 != src.get()) .forSequential(l2 -> { last2.set(l2); s.increment(); if (l2.hasEdgeTo(dst.get()) || l2.hasEdgeFrom(dst.get())) { ControlFlow.exit(3); } }); } if (s.get() < threshold) { Scalar<PgxVertex> last2 = Scalar.create(l1); l1.getInNeighbors().filter(l2 -> s.get() < threshold && l2 != last2.get() && l2 != l1 && l2 != src.get()) .forSequential(l2 -> { last2.set(l2); s.increment(); if (l2.hasEdgeTo(dst.get()) || l2.hasEdgeFrom(dst.get())) { ControlFlow.exit(3); } }); } }); } // 3 hop (L1-IN) if (s.get() < threshold) { Scalar<PgxVertex> last1 = Scalar.create(src.get()); src.get().getInNeighbors().filter(l1 -> s.get() < threshold && l1 != last1.get() && l1 != src.get()) .forSequential(l1 -> { last1.set(l1); s.increment(); if (s.get() < threshold) { Scalar<PgxVertex> last2 = Scalar.create(l1); l1.getOutNeighbors().filter(l2 -> s.get() < threshold && l2 != last2.get() && l2 != l1 && l2 != src.get()) .forSequential(l2 -> { last2.set(l2); s.increment(); if (l2.hasEdgeTo(dst.get()) || l2.hasEdgeFrom(dst.get())) { ControlFlow.exit(3); } }); } if (s.get() < threshold) { Scalar<PgxVertex> last2 = Scalar.create(l1); l1.getInNeighbors().filter(l2 -> s.get() < threshold && l2 != last2.get() && l2 != l1 && l2 != src.get()) .forSequential(l2 -> { last2.set(l2); s.increment(); if (l2.hasEdgeTo(dst.get()) || l2.hasEdgeFrom(dst.get())) { ControlFlow.exit(3); } }); } }); } Scalar<Integer> found = Scalar.create(-1); if (!(s.get() < threshold && maxHops == 3)) { Scalar<PgxVertex> dst2 = Scalar.create(dst.get()); // a hack to get away with creating accessor in above code // failed fast path // return correct answer with Big-BFS inBFS(g, src.get()).direction(IN_OUT_EDGES).filter(n -> found.get() == -1) .navigator(n -> found.get() == -1 && currentLevel() < maxHops).forward(n -> { if (n == dst2.get()) { found.set(currentLevel()); stopTraversal(); } }); } return found.get(); } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ procedure reachability_undirected(graph G, node source, node dest, int maxHops) : int { bool giveup = false; int threshold = 10000000; node src = source; node dst = dest; if (src.inDegree() + src.outDegree() > dst.inDegree() + dst.outDegree()) { node temp = src; src = dst; dst = temp; } // Specialized for fast up-to-3-hop finding // Not for general cases // 0 hop if (src == dst) { return 0; } else if (maxHops == 0) { return -1; } // 1 hop if (src.hasEdgeTo(dst) || src.hasEdgeFrom(dst)) { return 1; } else if (maxHops == 1) { return -1; } int s = 0; // 2 hop { node last1 = src; for (l1: src.outNbrs) (l1 != last1 && l1 != src) { last1 = l1; s++; if (l1.hasEdgeTo(dst) || l1.hasEdgeFrom(dst)) { return 2; } } last1 = src; for (l1: src.inNbrs) (l1 != last1 && l1 != src) { last1 = l1; s++; if (l1.hasEdgeTo(dst) || l1.hasEdgeFrom(dst)) { return 2; } } } if (maxHops == 2) { return -1; } // 3 hop (L1-OUT) if (s < threshold) { node last1 = src; for (l1: src.outNbrs) (s < threshold && l1 != last1 && l1!= src) { last1 = l1; s++; if (s < threshold) { node last2 = l1; for (l2: l1.outNbrs) (s < threshold && l2 != last2 && l2 !=l1 && l2!= src) { last2 = l2; s++; if (l2.hasEdgeTo(dst) || l2.hasEdgeFrom(dst)) { return 3; } } } if (s < threshold) { node last2 = l1; for (l2: l1.inNbrs) (s < threshold && l2 != last2 && l2 !=l1 && l2!= src) { last2 = l2; s++; if (l2.hasEdgeTo(dst) || l2.hasEdgeFrom(dst)) { return 3; } } } } } // 3 hop (L1-IN) if (s < threshold) { node last1 = src; for (l1: src.inNbrs) (s < threshold && l1 != last1 && l1 != src) { last1 = l1; s++; if (s < threshold) { node last2 = l1; for (l2: l1.outNbrs) (s < threshold && l2 != last2 && l2 != l1 && l2 != src) { last2 = l2; s++; if (l2.hasEdgeTo(dst) || l2.hasEdgeFrom(dst)) { return 3; } } } if (s < threshold) { node last2 = l1; for (l2: l1.inNbrs) (s < threshold && l2 != last2 && l2 != l1 && l2 != src) { last2 = l2; s++; if (l2.hasEdgeTo(dst) || l2.hasEdgeFrom(dst)) { return 3; } } } } } int found = -1; if (!(s < threshold && maxHops == 3)) { node dst2 = dst; // a hack to get away with creating accessor in above code // failed fast path // return correct answer with Big-BFS inBFS (n: G.nodes from src using inOutEdges) (found == -1) [found == -1 && currentBFSLevel() < maxHops] { if (n == dst2) { found = currentBFSLevel(); stopBFS(); } } } return found; }