minimum spanning tree lua HPPL

[Albert Chan]

Version 3, extending to multi-dimensional points.

List of possible edges may be huge, this version switched the logic, and disallowed "bad" edges.
Example, if edge [p1,p2] (and of course, [p2, p1]) is not allowed: badEdges = [[p1,p2], [p2,p1]]
Note that badEdges list length always even.

For comparing "distance", it uses norm2, squared, of difference of 2 points.

Without doing square roots, this version is even faster than my previous version.
Running same example, 12 points, 66 edges (badEdges = []) , it finished in 0.004 sec.

Code:

#cas  
mstTree(points, badEdges):=
BEGIN
LOCAL tree, j, k, p, v, d1, d2, pointsd, n, temp;
tree := {}
n, pointsd := 1, len(points);   // n = len(vertices)
WHILE n < pointsd DO
  d1, temp := inf, (inf, inf)
  FOR j FROM 1 TO n DO
    v := points[j];             // filled vertices
    FOR k FROM n+1 TO pointsd DO
      p := points[k];
      d2 = p .- v;
      IF (d2 *= d2) >= d1 THEN continue END;
      IF member([k,j], badEdges) THEN continue END;
      d1, temp := d2, [k,p,v];
    END
  END
  [k,p,v] := temp;
  tree[n] := [p,v];
  points[k] := points[n+=1];    // make space
  points[n] := p;               // save vertice
END
return tree;
END;
#end

With your example, 6 points, 6*5/2=15 edges (again, badEdges = []), this is the result:

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