minimum spanning tree lua HPPL

[Albert Chan]

(10-29-2021 05:53 AM)robmio Wrote:  Thank you for having brilliantly solved the "multivariate" version as well. Are you a computer scientist?

No. I had never heard of minimum spanning tree

(10-28-2021 09:07 PM)Albert Chan Wrote:  Version 3, extending to multi-dimensional points
...

CAS> pts := [[15,17,24,14], [17,15,32,26], [15,14,29,23], [13,12,10,16], [20,17,26,28], [15,21,26,21]]
CAS> mstTree(pts, [])

{[[15,21,26,21] , [15,17,24,14]],
  [[15,14,29,23] , [15,21,26,21]],
  [[17,15,32,26] , [15,14,29,23]],
  [[20,17,26,28] , [17,15,32,26]],
  [[13,12,10,16] , [15,17,24,14]]}

sum of line segments length = √69 + √62 + √23 + √53 + √229 ≈ 43.3893

Instead of badEdges = [[p1,p2],[p2,p1], ...], we could simplify to [[1,2],[2,1], ...]
Same for tree = [[p(j1),p(k1)], [p(j2),p(k2)], ...], simplified to [[j1,k1],[j2,k2], ...]

But, this required pts not be shuffled (otherwise indexes meant nothing)
Version 4 solve the problems with another level of indirection (*)

Code:

#cas
mstTree(points, badEdges):=
BEGIN
LOCAL tree, j, k, v, d1, d2, pointsd, n, temp;
LOCAL m, mj, mk;                // mapped indexes
n, pointsd := 1, len(points);   // n = len(vertices)
tree, m := {}, range(1,pointsd+1);
WHILE n < pointsd DO
  d1 := temp := inf;
  FOR j FROM 1 TO n DO
    v := points[mj := m[j]];    // filled vertices
    FOR k FROM n+1 TO pointsd DO
      d2 = v .- points[mk := m[k]];
      IF (d2 *= d2) >= d1 THEN continue END;            
      IF member([mk,mj], badEdges) THEN continue END;
      d1, temp := d2, [k, [mk,mj]];
    END
  END
  k, tree[n] := temp;
  m[k] := m[n += 1];            // swap m[k], m[n+1]
  m[n] := temp[2][1];
END
return tree;
END;
#end

Redo the same example, with this new version

CAS> pts := [[15,17,24,14], [17,15,32,26], [15,14,29,23], [13,12,10,16], [20,17,26,28], [15,21,26,21]]
CAS> tree := mstTree(pts, [])

[[6,1],[3,6],[2,3],[5,2],[4,1]]

CAS> norm2(x) := sqrt(dot(x,x))
CAS> map(tree, x -> norm2(pts[x[1]] - pts[x[2]]))       → [√69,√62,√23,√53,√229]
CAS> sum(float(Ans))       → 43.3893190999

What if points #2, #3 line segment not allowed ?

CAS> tree := mstTree(pts, [[2,3],[3,2]])

[[6,1],[3,6],[5,3],[2,5],[4,1]]

CAS> map(tree, x -> norm2(pts[x[1]] - pts[x[2]]))       → [√69,√62,2*√17,√53,√229]
CAS> sum(float(Ans))       → 46.8396988279

(*)