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},${v}]))
);

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

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

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

if (uSet !== vSet) {
}
Enjoy 