minimum spanning tree lua HPPL

[Albert Chan]

This version shuffled the list of points to vertices, and reduce loop counts by half.

Code:

#cas
mstValid(edges, edge) := 
  contains(edges,edge) OR 
  contains(edges,reverse(edge));

mstTree(points,edges):=
BEGIN
LOCAL tree, j, k, p, v, d1, d2, pointsd, n, temp;
tree := {}
n, pointsd := 1, SIZE(points);  // n = SIZE(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];
      IF (d2 := abs(p-v)) >= d1 THEN continue END;
      IF NOT mstValid(edges, [p,v]) 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