PGX 21.1.1
Documentation

Cycle Detection Algorithms

PGX 21.1.1 has two algorithms for finding cycles. A robust version, hence more expensive, that will perform several DFS traversals using different vertices as starting points for the search. And a light-weight version that will perform just one single DFS traversal using the given vertex as starting point for the task.

Find Cycle

Category structure evaluation

Algorithm ID pgx_builtin_s14a_find_cycle

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

Space Requirement O(5 * V + E) with V = number of vertices, E = number of edges

Javadoc

This algorithm tries to find a cycle in a directed graph using DFS traversals and will return the first cycle found, if there is one. In such case, the vertices and edges involved in the cycle will be returned in the order of visit. The algorithm is expensive because it will perform DFS traversals using different vertices as starting points until it explores the whole graph (worst-case scenario), or until it finds a cycle.

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
cycle_nodes nodeSeq vertex sequence holding the vertices in the cycle.
cycle_edges edgeSeq edge sequence holding the edges in the cycle.
Return Value Type Comment
bool true if there is a cycle in the graph, false otherwise.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeSequence;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSequence;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.inDFS;

@GraphAlgorithm
public class FindCycle {
  public boolean findCycle(PgxGraph g, @Out VertexSequence cycleNodes, @Out EdgeSequence cycleEdges) {
    VertexProperty<Boolean> visited = VertexProperty.create();
    VertexProperty<Boolean> inPath = VertexProperty.create();
    VertexProperty<PgxVertex> source = VertexProperty.create();
    VertexProperty<Long> deg = VertexProperty.create();

    visited.setAll(false);
    inPath.setAll(false);
    deg.setAll(PgxVertex::getOutDegree);

    Scalar<Boolean> foundCycle = Scalar.create(false);
    Scalar<PgxVertex> pivotNode = Scalar.create();

    g.getVertices().filter(s -> !visited.get(s) && !foundCycle.get()).forSequential(s ->
        inDFS(g, s)
            .navigator(v -> !foundCycle.get())
            .filter(v -> deg.get(v) > 0)
            .forward(v -> {
              //Adding potential vertices in the cycle path
              inPath.set(v, true);

              v.getNeighbors().forEach(w -> {
                source.set(w, v);
                if (inPath.get(w)) {
                  foundCycle.set(true);
                  pivotNode.set(w);
                }
              });
            })
            .backwardFilter(v -> !foundCycle.get())
            .backward(v -> {
              //Updating paths leading to dead-ends
              v.getInNeighbors().filter(inPath).forEach(w -> {
                if (deg.get(w) > 0) {
                  deg.set(w, deg.get(w) - 1);
                }
              });

              pivotNode.set(source.get(v));
              //Removing from the potential cycle path
              //a vertex that leads to a dead-end
              PgxVertex vertex = pivotNode.get();
              if (deg.get(vertex) == 0) {
                inPath.set(vertex, false);
                visited.set(vertex, true);
              }
            })
    );

    if (foundCycle.get()) {
      //Adding the vertices (in REVERSE order) in the cycle
      PgxVertex firstInCycle = pivotNode.get();
      cycleNodes.pushFront(firstInCycle);
      PgxVertex t = source.get(firstInCycle);
      pivotNode.set(t);

      Scalar<PgxEdge> e = Scalar.create();
      while (pivotNode.get() != firstInCycle) {
        cycleNodes.pushFront(pivotNode.get());

        PgxVertex pivotNodeGet = pivotNode.get();
        pivotNodeGet.getNeighbors().filter(inPath).forSequential(v ->
            e.set(v.edge())
        );

        cycleEdges.pushFront(e.get());

        PgxVertex vertex = pivotNode.get();
        PgxVertex sourceVertex = source.get(vertex);
        pivotNode.set(sourceVertex);
      }
      cycleNodes.pushFront(pivotNode.get());
      PgxVertex pivotNodeGet = pivotNode.get();
      pivotNodeGet.getNeighbors().filter(inPath).forSequential(v ->
          e.set(v.edge())
      );
      cycleEdges.pushFront(e.get());
    }

    return foundCycle.get();
  }
}

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

procedure find_cycle(graph G; nodeSeq cycle_nodes, edgeSeq cycle_edges) : bool {

  vertexProp<bool> visited;
  vertexProp<bool> in_path;
  vertexProp<node> source;
  vertexProp<int> deg;

  G.visited = false;
  G.in_path = false;
  G.deg = _.degree();

  bool found_cycle = false;

  node pivot_node = G.pickRandom();

  for (s: G.nodes) (!s.visited && !found_cycle) {

    inDFS (v: G.nodes from s) (v.deg > 0) [!found_cycle] {
      //Adding potential vertices in the cycle path
      v.in_path = true;

      foreach (w: v.nbrs) {
        w.source = v;
        if (w.in_path ) {
          found_cycle = true;
          pivot_node = w;
        }
      }
    }
    inPost (!found_cycle) {
      //Updating paths leading to dead-ends
      foreach (w: v.inNbrs) {
        if (w.deg > 0) {
          w.deg = w.deg - 1;
        }
      }
      pivot_node = v.source;
      //Removing from the potential cycle path
      //a vertex that leads to a dead-end
      if (pivot_node != NIL && pivot_node.deg == 0 && pivot_node.in_path) {
        pivot_node.in_path = false;
        pivot_node.visited = true;
      }
    }
  }

  if (found_cycle) {
    //Adding the vertices (in REVERSE order) in the cycle
    node first_in_cycle = pivot_node;
    cycle_nodes.pushFront(pivot_node);
    pivot_node = pivot_node.source;
    while (pivot_node != first_in_cycle) {
      cycle_nodes.pushFront(pivot_node);
      for (v: pivot_node.nbrs) (v.in_path) {
        edge e = v.edge();
        cycle_edges.pushFront(e);
      }
      pivot_node = pivot_node.source;
    }
    cycle_nodes.pushFront(pivot_node);
    for (v: pivot_node.nbrs) (v.in_path) {
      edge e = v.edge();
      cycle_edges.pushFront(e);
    }
  }

  return found_cycle;
}

Find Cycle from Node

Category structure evaluation

Algorithm ID pgx_builtin_s14b_find_cycle_from_node

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

Space Requirement O(4 * V + E) with V = number of vertices, E = number of edges

Javadoc

This implementation tries to find a cycle in a directed graph using the given vertex as starting point for the DFS traversal and will return the first cycle found, if there is one. In such case, the vertices and edges involved in the cycle will be returned in the order of visit. Restricting the DFS traversal to a single starting point means that some parts of the graph may not get explored.

Signature

Input Argument Type Comment
G graph
s node source vertex for the search.
Output Argument Type Comment
cycle_nodes nodeSeq vertex sequence holding the vertices in the cycle.
cycle_edges edgeSeq edge sequence holding the edges in the cycle.
Return Value Type Comment
bool true if there is a cycle in the graph, false otherwise.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeSequence;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSequence;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.inDFS;

@GraphAlgorithm
public class FindCycleFromNode {
  public boolean findCycle(PgxGraph g, PgxVertex s, @Out VertexSequence cycleNodes, @Out EdgeSequence cycleEdges) {
    VertexProperty<PgxVertex> source = VertexProperty.create();
    VertexProperty<Long> deg = VertexProperty.create();
    VertexProperty<Boolean> inPath = VertexProperty.create();

    deg.setAll(PgxVertex::getOutDegree);
    inPath.setAll(false);
    Scalar<Boolean> foundCycle = Scalar.create(false);
    Scalar<PgxVertex> pivotNode = Scalar.create();

    inDFS(g, s).navigator(v -> !foundCycle.get()).filter(v -> v.getDegree() > 0).forward(v -> {
      inPath.set(v, true);

      v.getNeighbors().forEach(w -> {
        source.set(w, v);
        if (inPath.get(w)) {
          foundCycle.set(true);
          pivotNode.set(w);
        }
      });
    }).backwardFilter(v -> !foundCycle.get()).backward(v -> {
      v.getInNeighbors().forEach(w -> {
        if (deg.get(w) > 0) {
          deg.set(w, deg.get(w) - 1);
        }
      });
      pivotNode.set(source.get(v));
      if (deg.get(pivotNode.get()) == 0) {
        inPath.set(pivotNode.get(), false);
      }
    });

    if (foundCycle.get()) {
      PgxVertex firstInCycle = pivotNode.get();
      cycleNodes.pushFront(pivotNode.get());
      pivotNode.set(source.get(pivotNode.get()));

      Scalar<PgxEdge> e = Scalar.create();
      while (pivotNode.get() != firstInCycle) {
        cycleNodes.pushFront(pivotNode.get());

        pivotNode.get().getOutNeighbors().filter(inPath).forSequential(v -> e.set(v.edge()));
        cycleEdges.pushFront(e.get());

        pivotNode.set(source.get(pivotNode.get()));
      }
      cycleNodes.pushFront(pivotNode.get());
      pivotNode.get().getOutNeighbors().filter(inPath).forSequential(v -> e.set(v.edge()));

      cycleEdges.pushFront(e.get());
    }

    return foundCycle.get();
  }
}

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

procedure find_cycle(graph G, node s; nodeSeq cycle_nodes, edgeSeq cycle_edges) : bool {

  vertexProp<node> source;
  vertexProp<int> deg;
  vertexProp<bool> in_path;

  G.deg = _.degree();
  G.in_path = false;
  bool found_cycle = false;
  node pivot_node = G.pickRandom();

  inDFS (v: G.nodes from s) (v.deg > 0) [!found_cycle] {
    v.in_path = true;

    foreach (w: v.nbrs) {
      w.source = v;
      if (w.in_path) {
        found_cycle = true;
        pivot_node = w;
      }
    }
  }
  inPost (!found_cycle) {

    foreach (w: v.inNbrs) {
      if (w.deg > 0) {
        w.deg = w.deg - 1;
      }
    }
    pivot_node = v.source;
    if (pivot_node != NIL && pivot_node.deg == 0) {
      pivot_node.in_path = false;
    }
  }

  if (found_cycle) {
    node first_in_cycle = pivot_node;
    cycle_nodes.pushFront(pivot_node);
    pivot_node = pivot_node.source;

    while (pivot_node != first_in_cycle) {
      cycle_nodes.pushFront(pivot_node);

      for (v: pivot_node.nbrs) (v.in_path) {
        edge e = v.edge();
        cycle_edges.pushFront(e);
      }
      pivot_node = pivot_node.source;
    }
    cycle_nodes.pushFront(pivot_node);
    for (v: pivot_node.nbrs) (v.in_path) {
      edge e = v.edge();
      cycle_edges.pushFront(e);
    }
  }

  return found_cycle;
}