PGX 20.1.1
Documentation

Weakly Connected Components (WCC)

Category connected components

Algorithm ID pgx_builtin_g3_weakly_connected_components

Time Complexity O(E * d) with d = diameter of the graph

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

Javadoc

This algorithm finds weakly connected components (WCC) in a directed graph. A WCC is a maximal subset of vertices of the graph with the particular characteristic that for every pair of vertices U and V in the WCC there must be a directed path connecting U to V or viceversa. It is a non-deterministic algorithm because of its parallelized implementation.

Signature

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

Code

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

import java.util.function.Function;

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;

@GraphAlgorithm
public class Wcc {
  public long wcc(PgxGraph g, @Out VertexProperty<Long> compId) {
    VertexProperty<PgxVertex> wcc = VertexProperty.create();

    // Initialize
    wcc.setAll(Function.identity());

    Scalar<Boolean> changed = Scalar.create();
    do {
      changed.set(false);

      // kernel 1 (get 'maximum' value among neighbors)
      g.getVertices().forEach(u -> {
        u.getInNeighbors().forSequential(v -> {
          if (wcc.get(u).lessThan(wcc.get(v))) {
            changed.reduceOr(true);
            wcc.set(u, wcc.get(v));
          }
        });

        u.getOutNeighbors().forSequential(v -> {
          if (wcc.get(u).lessThan(wcc.get(v))) {
            changed.reduceOr(true);
            wcc.set(u, wcc.get(v));
          }
        });
      });

      // kernel 2
      g.getVertices().forEach(u -> {
        if (wcc.get(u) != u) {
          PgxVertex v = wcc.get(u);
          if (wcc.get(v) != v) {
            wcc.set(u, wcc.get(v));
          }
        }
      });
    } while (changed.get());

    // Create output format
    Scalar<Long> numComp = Scalar.create(0L);
    g.getVertices().forSequential(n -> {
      if (wcc.get(n) == n) {
        compId.set(n, numComp.get());
        numComp.increment();
      }
    });

    g.getVertices().filter(n -> wcc.get(n) != n).forEach(n -> {
      PgxVertex v = wcc.get(n);
      compId.set(n, compId.get(v));
    });

    return numComp.get();
  }
}

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

procedure wcc(graph G; nodeProp<long> comp_id) : long {

  nodeProp<node> wcc;

  // Initialize
  foreach (u: G.nodes) {
    u.wcc = u;
  }

  bool changed;
  do {
    changed = false;

    // kernel 1 (get 'maximum' value among neighbors)
    foreach (u: G.nodes) {
      for (v: u.inNbrs) {
        if (u.wcc < v.wcc) {
          changed |= true;
          u.wcc = v.wcc;
        } // allow race
      }
      for (v: u.outNbrs) {
        if (u.wcc < v.wcc) {
          changed |= true;
          u.wcc = v.wcc;
        } //allow race
      }
    }

    // kernel 2
    foreach (u: G.nodes) {
      if (u.wcc != u) {
        node v = u.wcc;
        if (v.wcc != v) {
          u.wcc = v.wcc;
        }
      }
    }
  } while (changed);

  // Create output format
  long num_comp = 0;
  for (n: G.nodes) {
    if (n.wcc == n) {
      n.comp_id = num_comp;
      num_comp++;
    }
  }

  foreach (n: G.nodes) (n.wcc != n) {
    node v = n.wcc;
    n.comp_id = v.comp_id;
  }

  return num_comp;
}