PGX 20.1.1
Documentation

Strongly Connected Components

PGX 20.1.1 has two algorithms for finding Strongly Connected Components (SCC).


Strongly Connected Components (SCC) via Kosaraju's algorithm

Category connected components

Algorithm ID pgx_builtin_g2a_strongly_connected_components_kosaraju

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


Kosaraju's algorithm works on directed graphs for finding strongly connected components (SCC). A SCC is a maximal subset of vertices of the graph with the particular characteristic that every vertex in the SCC can be reachable from any other other vertex in the SCC.

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
scc nodeProp vertex property holding the label of the SCC assigned to each vertex.
Return Value Type Comment
long the total number of SCC found in the graph.

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.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.Direction.IN_EDGES;
import static oracle.pgx.algorithm.Traversal.inBFS;
import static oracle.pgx.algorithm.Traversal.inDFS;

@GraphAlgorithm
public class Kosaraju {
  public long kosaraju(PgxGraph g, @Out VertexProperty<Long> scc) {
    scc.setAll(-1L);

    VertexProperty<Boolean> checked = VertexProperty.create();
    checked.setAll(false);

    // [Phase 1]
    // Obtain reverse-post-DFS-order of node sequence.
    // nodeOrder can be also used here but nodeSeq is faster
    VertexSequence queue = VertexSequence.create();
    g.getVertices().filter(t -> !checked.get(t)).forSequential(t ->
        inDFS(g, t)
            .navigator(n -> !checked.get(n))
            .backward(n -> {
              checked.set(n, true);
              queue.pushFront(n);
            })
    );

    // [Phase 2]
    // Starting from each vertex in the sequence
    // do BFS on the transposed graph g^.
    // and every vertices that are (newly) visited compose one SCC.
    Scalar<Long> compId = Scalar.create(0L);
    queue.filter(t -> scc.get(t) == -1).forSequential(t -> {
      inBFS(g, t)
          .navigator(n -> scc.get(n) == -1)
          .forward(n -> scc.set(n, compId.get()))
          .direction(IN_EDGES);

      compId.increment();
    });

    return compId.get();
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure kosaraju(graph G; nodeProp<long> scc) : long {

  G.scc = -1;

  nodeProp<bool> checked;
  G.checked = false;

  // [Phase 1]
  // Obtain reverse-post-DFS-order of node sequence.
  // nodeOrder can be also used here but nodeSeq is faster
  nodeSeq queue;
  for (t: G.nodes) (!t.checked) {
    inDFS (n: G.nodes from t) [!n.checked] {
      // do nothing at pre-visit
    }
    inPost { // check at post-visit
      n.checked = true;
      queue.pushFront(n);
    }
  }

  // [Phase 2]
  // Starting from each vertex in the sequence
  // do BFS on the transposed graph G^.
  // and every vertices that are (newly) visited compose one SCC.
  long compId = 0;
  for (t: queue.items) (t.scc == -1) {
    inBFS (n: G.nodes from t using inEdges) [n.scc == -1] {
      n.scc = compId;
    }
    compId++;
  }

  return compId;
}

Strongly Connected Components (SCC) via Tarjan's algorithm

Category connected components

Algorithm ID pgx_builtin_g2b_strongly_connected_components_tarjan

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

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

Javadoc


Tarjan's algorithm works on directed graphs for finding strongly connected components (SCC). A SCC is a maximal subset of vertices of the graph with the particular characteristic that every vertex in the SCC can be reachable from any other other vertex in the SCC.

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
scc nodeProp vertex property holding the label of the SCC assigned to each vertex.
Return Value Type Comment
long the total number of SCC found in the graph.

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.VertexSequence;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

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

@GraphAlgorithm
public class Tarjan {
  public long tarjan(PgxGraph g, @Out VertexProperty<Long> scc) {
    VertexProperty<Boolean> inStack = VertexProperty.create();
    VertexProperty<Long> lowLink = VertexProperty.create();
    VertexProperty<Long> index = VertexProperty.create();
    VertexSequence stack = VertexSequence.create();

    // sequentially initialize, otherwise compiler flags this algorithm as parallel in nature
    g.getVertices().forSequential(n -> {
      scc.set(n, -1L);
      inStack.set(n, false);
      index.set(n, -1L);
    });

    Scalar<Long> numScc = Scalar.create(0L);

    // DFS
    g.getVertices().filter(n -> scc.get(n) == -1).forSequential(n -> {
      Scalar<Long> dfsIndex = Scalar.create(0L);

      inDFS(g, n)
          .navigator(t -> index.get(t) == -1)
          .forward(t -> {
            stack.pushBack(t);
            inStack.set(t, true);
            lowLink.set(t, dfsIndex.get());
            index.set(t, dfsIndex.get());
            dfsIndex.increment();
          })
          .backward(t -> {
            t.getNeighbors().filter(k -> scc.get(k) == -1).forSequential(k -> {
              lowLink.reduceMin(t, lowLink.get(k));
            });

            if (lowLink.get(t) == index.get(t)) {
              PgxVertex w = stack.popBack();
              while (w != t) {
                inStack.set(w, false);
                scc.set(w, numScc.get());
                w = stack.popBack();
              }
              inStack.set(w, false);
              scc.set(w, numScc.get());
              numScc.increment();
            }
          });
    });

    return numScc.get();
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure tarjan(graph G; nodeProp<long> scc) : long {

  nodeProp<bool> in_stack;
  nodeProp<long> low_link;
  nodeProp<long> index;
  nodeSeq stack;

  // sequentially initialize, otherwise compiler flags this algorithm as
  // parallel in nature
  for (n: G.nodes) {
    n.scc = -1;
    n.in_stack = false;
    n.index = -1;
  }

  long num_scc = 0;

  // DFS
  for (n: G.nodes) (n.scc == -1) {
    long dfs_index = 0;

    inDFS (t: G.nodes from n) [t.index == -1] {
      // previsit
      stack.pushBack(t);
      t.in_stack = true;
      t.low_link = dfs_index;
      t.index = dfs_index;
      dfs_index++;
    }

    inPost {
      // post visit
      for (k: t.nbrs) (k.scc == -1) {
        t.low_link min= k.low_link;
      }
      // identified an SCC
      if (t.low_link == t.index) {
        node w = stack.popBack();
        while (w != t) {
          w.in_stack = false;
          w.scc = num_scc;
          w = stack.popBack();
        }
        w.in_stack = false;
        w.scc = num_scc;
        num_scc++;
      }
    }
  }

  return num_scc;
}