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) {
      F.add([u, v]);
      disjointSets.delete(uSet);
      disjointSets.delete(vSet);
      disjointSets.add(new Set([...uSet, ...vSet]));
    }
  });

  return [...F];
}

Enjoy

seed

values