Public
Edited
Dec 20, 2022
1 star
class Graph {
constructor(nodes, edges = []) {
if (!nodes) {
this.V = [...new Set(edges.reduce((a, b) => [...a, ...b], []))];
} else {
this.V = nodes;
}
this.E = [...edges];
}
addEdge(edge) {
if (!this.V.includes(edge[0])) this.V.push(edge[0]);
if (!this.V.includes(edge[1])) this.V.push(edge[1]);
this.E.push(edge);
}
getNodeDegrees() {
const counter = new Map(this.V.map((v, i) => [v, 0]));
this.E.forEach(([u, v]) => {
counter[u] += 1;
counter[v] += 1;
});
return counter
}
getMaximumDegree() {
const nodeDegrees = this.getNodeDegrees();
return Math.max(...Array.from(nodeDegrees.values));
}
getNodesByDegree(k) {
const nodeDegrees = this.getNodeDegrees();
return new Set(this.V.filter((v) => nodeDegrees.get(v) === k));
}
}
class UnionFindSet {
constructor(nodes) {
this.parent = new Map(nodes.map((v) => [v, v]))
}
find(x) {
return (this.parent[x] === x) ? x : (this.parent[x] = this.find(this.parent[x]));
}
union(x, y) {
this.parent[this.find(x)] = this.find(y);
}
inSameSet(x, y) {
return this.find(x) === this.find(y);
}
}
function getArbitratySpanningTree(G) {
const disjointSet = new UnionFindSet(G.V);
const E = [...G.E].sort((a, b) => 0.5 - Math.random());
const T = new Graph(G.V);
for (let i = 0; i < E.length; ++i) {
const u = E[i][0];
const v = E[i][1];
if (!disjointSet.inSameSet(u, v)) {
T.addEdge([u, v]);
disjointSet.union(u, v);
}
if (T.E.length >= T.V.length - 1) break;
}
return T;
}
function FindMinimumDegreeSpanningTree(G) {
const T = getArbitratySpanningTree(G);
const done = false;
const _ = {};
while (done) {
const k = T.getMaximumDegree(); // Start a new phase
while (T.getMaximumDegree() == k) {
// Start a new subphase
_["D_k"] = T.getNodesByDegree(k); // Dk: Set<number>
_["D_{k-1}"] = T.getNodesByDegree(k - 1); // DkMinusOne: Set<number>
_["F"] = T.E.filter(([u, v]) => _["D_k"].has(u) || _["D_k"].has(v)); // F: Edge[], Edge: number[]
_["TEdgesMinusF"] = T.E.filter(
(eT) =>
_["F"].indexOf(
(eF) =>
Math.min(...eT) === Math.min(...eF) &&
Math.max(...eT) === Math.max(...eF)
) != -1
);
const TMinusF = new Graph(null, _["TEdgesMinusF"]);
return TMinusF;
}
}
return T;
}
g = new Graph(
[1, 2, 3, 4, 5],
[
[1, 2],
[1, 3],
[2, 3],
[2, 4],
[2, 5],
[3, 4],
[4, 5]
]
)
FindMinimumDegreeSpanningTree(g)
{
function plotGraph(G) {
const myChart = echarts.init(document.getElementById("plot"));
const option = {
series: [
{
type: "graph",
layout: "force",
animation: false,
data: [
{
fixed: true,
x: myChart.getWidth() / 2,
y: myChart.getHeight() / 2,
symbolSize: 20,
id: "-1"
}
],
force: {
// initLayout: 'circular'
// gravity: 0
repulsion: 100,
edgeLength: 5
},
edges: G.E
}
]
};
myChart.setOption(option);
}
plotGraph(g);
}
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.
