// https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
/*
Kruskal(G) :
1 A := ø
2 pour chaque sommet v de G :
3 créerEnsemble(v)
4 trier les arêtes de G par poids croissant
5 pour chaque arête (u, v) de G prise par poids croissant :
6 si find(u) ≠ find(v) :
7 ajouter l'arête (u, v) à l'ensemble A
8 union(u, v)
9 retourner A
*/
md`${check(v1)}`
viewof v1 = htl.html`<input type=text>`
check = s => {
assert(s.length > 0);
let xs = s.split(' ');
let [a,, b,, c] = xs.map(Number);
return showChecking(s, a + b === c);
}
checkString = [" is correct ✔️", " is not correct ❌"]
showChecking = (s, checked) => {
return checked ? `${s}${checkString[0]}` : `${s}${checkString[1]}`
}
Graph = class Graph {
constructor(edges = []) {
this.edges = edges;
}
checkType() {
assert(Array.isArray(this.edges));
for (let edge of this.edges) {
assert(Array.isArray(edge));
asserteq(edge.length, 3);
for (let elem of edge) {
asserteq(typeof elem, "number");
// Edge id's and Weights must be positive.
assert(elem >= 0);
}
}
}
get size() {
return this.edges.length;
}
add(edges) {
this.edges.push(...edges);
}
remove(edge) {
for (let i = this.edges.length; i >= 0; --i) {
if (edge[0] === this.edges[i][0] &&
edge[1] === this.edges[i][1] &&
edge[2] === this.edges[i][2]) {
// Remove edge
this.edges.splice(i, 1);
}
// Continue finding other edge
}
throw Error(`Element ${edge} don't exist in the Graph`);
}
getVertices() {
let vertices = new Set();
for (let edge of this.edges) {
vertices.add(edge[0]);
vertices.add(edge[1]);
}
return vertices.size;
}
getDiameter() {
let adjacencyList = this.buildAdjacencyList();
let diameter = 0;
for (let vertex in adjacencyList) {
let distances = this.bfs(adjacencyList, vertex);
let maxDistance = Math.max(...Object.values(distances));
diameter = Math.max(diameter, maxDistance);
}
return diameter;
}
buildAdjacencyList() {
let adjacencyList = {};
for (let edge of this.edges) {
let [source, destination] = edge.slice(0, 2);
if (adjacencyList[source]) {
adjacencyList[source].add(destination);
} else {
adjacencyList[source] = new Set([destination]);
}
if (adjacencyList[destination]) {
adjacencyList[destination].add(source);
} else {
adjacencyList[destination] = new Set([source]);
}
}
return adjacencyList;
}
getEdgeWeight(v1, v2) {
for (let edge of this.edges)
if (v1 == edge[0] && v2 == edge[1] || v1 == edge[1] && v2 == edge[0])
return edge[2];
return null;
}
bfs(adjacencyList, start) {
let queue = [start];
let distances = {};
distances[start] = 0;
while (queue.length > 0) {
let current = queue.shift();
let neighbors = adjacencyList[current];
for (let neighbor of neighbors) {
if (!distances.hasOwnProperty(neighbor)) {
distances[neighbor] =
distances[current] + 1;
queue.push(neighbor);
}
}
}
return distances;
}
}
{
let s = new Set([1, 2, 3]);
for (let n of s) {
yield n;
}
}
{
let g = new Graph();
assert(g.edges.length == 0);
g.add([[0, 1, 0], [1, 2, 0], [1, 0, 1]]);
return g.buildAdjacencyList(0);
assert(g.edges.length == 3);
return "Test Graph 1 ✔️";
}
{
let g = new Graph([[0, 1, 1], [2, 3, 2]]);
g.checkType();
asserteq(g.size, 2);
asserteq(g.getVertices(), 4);
let [A, B, C, D, E, F] = [0, 1, 2, 3, 4, 5]; //[C, D, 3]
// g = new Graph([[A, B, 2], [B, C, 1], [A, C, 1], [B, D, 4], [C, E, 5], [D, E, 1], [D, F, 3], [E, F, 2]]); // 0 2 1 6 6 9
g = new Graph([[A, B, 2], [B, C, 1], [A, C, 1], [B, D, 4], [C, E, 5], [D, E, 1], [D, F, 3], [E, F, 2], [C, D, 2]]);
return g.bfs(g.buildAdjacencyList(), A);
return "Test Graph 2 ✔️";
}
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.
