perf(adjacency): pre-cache MST edge costs

thi-ng · Feb 19, 2021 · 290f3a6 · 290f3a6
1 parent cfe3ed5
commit 290f3a6
Showing 1 changed file with 18 additions and 13 deletions.
diff --git a/packages/adjacency/src/mst.ts b/packages/adjacency/src/mst.ts
@@ -1,23 +1,26 @@
 import type { Fn } from "@thi.ng/api";
+import { sortByCachedKey } from "@thi.ng/arrays";
 import { DisjointSet } from "./disjoint-set";
 
 /**
  * Computes the Minimum Spanning Tree from given weighted `edges`, using
- * Kruskal's algorithm.
+ * Kruskal's algorithm (O(E log V)).
  *
  * @remarks
- * Edges can be of any type, but requires unsigned integer vertex IDs.
- * The latter can be extracted via the user supplied `verts` function.
- * The edge weights are extracted via the `cost` function.
+ * Edges can be of any type, but requires unsigned integer vertex IDs. The
+ * latter can be extracted via the user supplied `verts` function. The edge
+ * weights are extracted via the `cost` function.
  *
- * The `maxID` arg should equal or greater than the largest vertex ID
- * referenced by the given edges.
+ * The `maxID` arg should equal or greater than the largest vertex ID referenced
+ * by the given edges.
  *
- * The function returns a new array of the original edges, satisfying
- * the MST criteria. The result edges will be in ascending order, based
- * on the supplied cost function.
+ * The function returns a new array of the original edges, satisfying the MST
+ * criteria. The result edges will be in ascending order, based on the supplied
+ * cost function. The cost function is called once for each edge and return
+ * values will be cached prior to sorting (see
+ * {@link @thi.ng/arrays#sortByCachedKey} for details).
  *
- * {@link https://en.wikipedia.org/wiki/Kruskal%27s_algorithm}
+ * Reference: {@link https://en.wikipedia.org/wiki/Kruskal%27s_algorithm}
  *
  * @example
  * ```ts
@@ -44,6 +47,8 @@ import { DisjointSet } from "./disjoint-set";
  * @param maxID - max vertex ID (+1)
  * @param cost - cost function
  * @param verts - vertices / graph nodes
+ *
+ * @typeParam T - edge type
  */
 export const mst = <T>(
     edges: T[],
@@ -53,10 +58,10 @@ export const mst = <T>(
 ) => {
     const graph = new DisjointSet(maxID + 1);
     const res: T[] = [];
-    for (let e of edges.sort((a, b) => cost(a) - cost(b))) {
+    for (let e of sortByCachedKey(edges, cost)) {
         const v = verts(e);
-        if (!graph.unified(...v)) {
-            graph.union(...v);
+        if (!graph.unified(v[0], v[1])) {
+            graph.union(v[0], v[1]);
             res.push(e);
         }
     }