Try, fail, learn, improve. Then repeat.
Public
Edited
Oct 24, 2021
cliqueNumber = d3.max(maximalCliques, x =>x.length)
// use the basic recursive backtracking Bron–Kerbosch algorithm,
// with the minor degeneracy ordering (improvement...)
maximalCliques = {
const { matrix } = dataset;
const N = matrix.length - 1 ;
const R = new BitSet().setRange(0, N, 0);
const P = new BitSet().setRange(0, N, 1)
const X = new BitSet().setRange(0, N, 0);
let maximals = [];
const BronKerboschWitherOrdering = (R, P, X) => {
if (P.cardinality() === 0 && X.cardinality() == 0) {
return R;
}
const degeneracyOrdering = P.toArray().sort((a,b) => {
return d3.ascending(matrix[a].cardinality(),matrix[b].cardinality())
})
P.toArray().forEach((v) => {
// v is added to R
const R_p = R.clone().set(v, 1);
// restrict P and X to the neighbors of v
const neigbors = matrix[v].toArray();
const P_p = P.and(neigbors);
const X_p = X.and(neigbors);
let found = BronKerboschWitherOrdering(R_p, P_p, X_p);
if (found) {
maximals.push(found);
}
// move v from P into X
P_p.set(v, 0);
X_p.set(v, 1);
});
return null;
};
const getMaximals = (maximals) => {
const dedupedMaximals = new Set(
maximals.map((bs) => bs.toArray()).map((arr) => arr.join(","))
).values();
return Array.from(dedupedMaximals)
.map((s) => s.split(",").map((x) => +x))
.sort((a, b) => d3.descending(a.length, b.length));
};
BronKerboschWitherOrdering(R, P, X);
return getMaximals(maximals)
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
