PGX 20.1.1
Documentation

Reachability Algorithms

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.

Reachability

Category structure evaluation

Algorithm ID pgx_builtin_s15a_reachability

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

Space Requirement O(1)

Javadoc

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.

Signature

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.

Code

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

Reachability (undirected)

Category structure evaluation

Algorithm ID pgx_builtin_s15b_reachability_undirected

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

Space Requirement O(1)

Javadoc

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.

Signature

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.

Code

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