PGX 20.1.1
Documentation

Graph Traversal Algorithms

PGX 20.1.1 has customizable versions of the BFS and DFS traversal algorithms, allowing the use these on tailored use cases.

Filtered BFS (Breadth-First Search)

Category other

Algorithm ID pgx_builtin_o1_filtered_bfs

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

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

Javadoc

This filtered version of the BFS algorithm allows to use a filter and a navigator expression to be evaluated over the vertices during the traversal and discriminate them according to the desired criteria. It will return the distance to the source vertex and the corresponding parent vertex for all the filtered vertices.

Signature

Input Argument Type Comment
G graph
root node the source vertex from the graph for the path.
init_with_inf bool boolean flag to set the initial distance values of the vertices. If set to true, it will initialize the distances as INF, and -1 otherwise.
filter vertexFilter (deprecated) filter expression to be evaluated on the vertices during the graph traversal. The filter expression has no effect; use the navigator instead to filter out vertices.
navigator vertexFilter navigator expression to be evaluated on the vertices during the graph traversal.
max_depth int maximum depth limit for the BFS traversal.
Output Argument Type Comment
dist nodeProp vertex property holding the hop distance for each reachable vertex in the graph.
parent nodeProp vertex property holding the parent vertex of the each reachable 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.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import oracle.pgx.algorithm.filter.VertexFilter;

import static oracle.pgx.algorithm.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;
import static java.lang.Integer.MAX_VALUE;

@GraphAlgorithm
public class FilteredBfs {
  public void filteredBfs(PgxGraph g, PgxVertex root, boolean initWithInf, VertexFilter filter, VertexFilter navigator,
      int maxDepth, @Out VertexProperty<Integer> dist, @Out VertexProperty<PgxVertex> parent) {
    if (g.getNumVertices() == 0) {
      return;
    }

    dist.setAll(initWithInf ? MAX_VALUE : -1);
    parent.setAll(PgxVertex.NONE);

    dist.set(root, 0);

    inBFS(g, root).navigator(n -> navigator.evaluate(n) && currentLevel() < maxDepth)
        .filter(n -> navigator.evaluate(n) || filter.evaluate(n)).forward(n -> {
          dist.set(n, currentLevel());
          parent.set(n, n.parentVertex());
        });
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure filtered_bfs(graph G, node root, bool init_with_inf, nodeFilter filter, nodeFilter navigator,
    int max_depth; nodeProp<int> dist, nodeProp<node> parent) {

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

  G.dist = init_with_inf ? +INF : -1;
  G.parent = NIL;

  root.dist = 0;

  inBFS (n: G.nodes from root) (navigator.evaluate(n) || filter.evaluate(n))
      [navigator.evaluate(n) && currentBFSLevel() < max_depth] {

    n.dist = currentBFSLevel();
    n.parent = n.BFSParentNode();
  }
}

Filtered DFS (Depth-First Search)

Category other

Algorithm ID pgx_builtin_o2_filtered_dfs

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

This filtered version of the DFS algorithm allows to use a filter and a navigator expression to be evaluated over the vertices during the traversal and discriminate them according to the desired criteria. It will return the distance to the source vertex and the corresponding parent vertex for all the filtered vertices.

Signature

Input Argument Type Comment
G graph
root node the source vertex from the graph for the path.
init_with_inf bool boolean flag to set the initial distance values of the vertices. If set to true, it will initialize the distances as INF, and -1 otherwise.
filter vertexFilter (deprecated) filter expression to be evaluated on the vertices during the graph traversal. The filter expression has no effect; use the navigator instead to filter out vertices.
navigator vertexFilter navigator expression to be evaluated on the vertices during the graph traversal.
max_depth int maximum depth limit for the BFS traversal.
Output Argument Type Comment
dist nodeProp vertex property holding the hop distance for each reachable vertex in the graph.
parent nodeProp vertex property holding the parent vertex of the each reachable 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.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import oracle.pgx.algorithm.filter.VertexFilter;

import static oracle.pgx.algorithm.Traversal.inDFS;
import static java.lang.Integer.MAX_VALUE;

@GraphAlgorithm
public class FilteredDfs {
  public void filteredDfs(PgxGraph g, PgxVertex root, boolean initWithInf, VertexFilter filter, VertexFilter navigator,
      int maxDepth, @Out VertexProperty<Integer> dist, @Out VertexProperty<PgxVertex> parent) {
    if (g.getNumVertices() == 0) {
      return;
    }

    VertexProperty<Boolean> visited = VertexProperty.create(false);

    dist.setAll(initWithInf ? MAX_VALUE : -1);
    parent.setAll(PgxVertex.NONE);

    dist.set(root, 0);
    Scalar<Integer> depth = Scalar.create(0);

    inDFS(g, root).navigator(n -> navigator.evaluate(n) && depth.get() <= maxDepth)
        .filter(n -> navigator.evaluate(n) || filter.evaluate(n)).forward(n -> {
          if (n != root) {
            n.getInNeighbors().forSequential(m -> {
              if (visited.get(m) && dist.get(m) < maxDepth && dist.get(m) >= depth.get() - 1) {
                parent.set(n, m);
              }
            });
          }
          if (parent.get(n) != PgxVertex.NONE) {
            PgxVertex p = parent.get(n);
            dist.set(n, dist.get(p) + 1);
          }

          depth.increment();
          visited.set(n, true);
        }).backward(n -> depth.decrement());
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure filtered_dfs(graph G, node root, bool init_with_inf, nodeFilter filter, nodeFilter navigator,
    int max_depth; nodeProp<int> dist, nodeProp<node> parent) {

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

  nodeProperty<bool> visited;

  G.dist = init_with_inf ? +INF : -1;
  G.parent = NIL;
  G.visited = false;

  root.dist = 0;
  int depth = 0;

  inDFS (n: G.nodes from root) (navigator.evaluate(n) || filter.evaluate(n))
      [navigator.evaluate(n) && depth <= max_depth] {

    if (n != root) {
      for (m: n.inNbrs) (m.visited && m.dist < max_depth && m.dist >= depth - 1) {
        n.parent = m;
      }
    }
    if (n.parent != NIL) {
      node p = n.parent;
      n.dist = p.dist + 1;
    }

    depth++;
    n.visited = true;

  } inPost {
    depth--;
  }

}