Home

# network

I really wanted to build a piece of art with a bunch of tangled edges on it. At first I tried to do a Traveling salesperson visualization, but the algorithms for doing so are pretty annoying to write and ship.
So instead I went “simpler” and drew a Minimum spanning tree over a fully-connected graph (each node connects to every other node).
I did this with Kruskal’s algorithm since it’s pretty straightforward. You can find the code in its entirety below or on GitHub. I didn’t really enjoy writing it because it involves lots of Sets and Arrays, so I fell victim to lots of out-of-bounds issues. The results are pretty neat though.
Expand for some messy code
kruskal({ edges, vertices }) {
// https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
//
// F:= ∅
// for each v ∈ G.V do
//     MAKE-SET(v)
// for each (u, v) in G.E ordered by weight(u, v), increasing do
//     if FIND-SET(u) ≠ FIND-SET(v) then
//         F:= F ∪ {(u, v)} ∪ {(v, u)}
//         UNION(FIND-SET(u), FIND-SET(v))
// return F

const F = new Set([]);
const disjointSets = new Set(
vertices.map((v) => new Set([${v[0]},${v[1]}]))
);

const sortedEdges = edges.slice();
sortedEdges.sort((e1, e2) => {
// Oh dear
const d1 =
(e1[0][0] - e1[1][0]) * (e1[0][0] - e1[1][0]) +
(e1[0][1] - e1[1][1]) * (e1[0][1] - e1[1][1]);
const d2 =
(e2[0][0] - e2[1][0]) * (e2[0][0] - e2[1][0]) +
(e2[0][1] - e2[1][1]) * (e2[0][1] - e2[1][1]);
return d1 - d2;
});

console.log(
sortedEdges.map(
([u, v]) =>
(u[1] - u[0]) * (u[1] - u[0]) + (v[1] - v[0]) * (v[1] - v[0])
)
);

sortedEdges.forEach(([u, v]) => {
const uSet = [...disjointSets].find((set) => set.has(${u[0]},${u[1]}));
const vSet = [...disjointSets].find((set) => set.has(${v[0]},${v[1]}));

if (uSet !== vSet) {
}