/*
* Copyright (C) 2013 - 2021 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();
}
}