PGX 21.2.2
Documentation

## Weakly Connected Components (WCC)

##### Categoryconnected componentsAlgorithm IDpgx_builtin_g3_weakly_connected_componentsTime ComplexityO(E * d) with d = diameter of the graphSpace RequirementO(2 * V) with V = number of verticesJavadocAnalyst#wcc(PgxGraph graph) Analyst#wcc(PgxGraph graph, VertexProperty partitionDistribution)

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 path connecting U to V, ignoring the direction of edges. It is a non-deterministic algorithm because of its parallelized implementation.

## Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
comp_id vertexProp 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

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

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

vertexProp<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;
}
```