minimum spanning tree lua HPPL

[Albert Chan]

It is more natural to use complex number to represent points: (x,y) ≡ x + y*i
List of valid edges has each edge with 2 points. (to make a segment)

With your example, we have:

Code:

pts := [ /* total 12 points */
(3,4.5),(1,5),(5,6.5),(2.5,5),(7,3),(1.5,1),
(4,2.5),(2,2),(8,4),(3,9),(4.5,0.5),(5,2)];

edgs := [ /* total 12*11/2 = 66 edges */
[(3,4.5),(1,5)],
[(3,4.5),(5,6.5)],
[(3,4.5),(2.5,5)],
[(3,4.5),(7,3)],
[(3,4.5),(1.5,1)],
[(3,4.5),(4,2.5)],
[(3,4.5),(2,2)],
[(3,4.5),(8,4)],
[(3,4.5),(3,9)],
[(3,4.5),(4.5,0.5)],
[(3,4.5),(5,2)],
[(1,5),(5,6.5)],
[(1,5),(2.5,5)],
[(1,5),(7,3)],
[(1,5),(1.5,1)],
[(1,5),(4,2.5)],
[(1,5),(2,2)],
[(1,5),(8,4)],
[(1,5),(3,9)],
[(1,5),(4.5,0.5)],
[(1,5),(5,2)],
[(5,6.5),(2.5,5)],
[(5,6.5),(7,3)],
[(5,6.5),(1.5,1)],
[(5,6.5),(4,2.5)],
[(5,6.5),(2,2)],
[(5,6.5),(8,4)],
[(5,6.5),(3,9)],
[(5,6.5),(4.5,0.5)],
[(5,6.5),(5,2)],
[(2.5,5),(7,3)],
[(2.5,5),(1.5,1)],
[(2.5,5),(4,2.5)],
[(2.5,5),(2,2)],
[(2.5,5),(8,4)],
[(2.5,5),(3,9)],
[(2.5,5),(4.5,0.5)],
[(2.5,5),(5,2)],
[(7,3),(1.5,1)],
[(7,3),(4,2.5)],
[(7,3),(2,2)],
[(7,3),(8,4)],
[(7,3),(3,9)],
[(7,3),(4.5,0.5)],
[(7,3),(5,2)],
[(1.5,1),(4,2.5)],
[(1.5,1),(2,2)],
[(1.5,1),(8,4)],
[(1.5,1),(3,9)],
[(1.5,1),(4.5,0.5)],
[(1.5,1),(5,2)],
[(4,2.5),(2,2)],
[(4,2.5),(8,4)],
[(4,2.5),(3,9)],
[(4,2.5),(4.5,0.5)],
[(4,2.5),(5,2)],
[(2,2),(8,4)],
[(2,2),(3,9)],
[(2,2),(4.5,0.5)],
[(2,2),(5,2)],
[(8,4),(3,9)],
[(8,4),(4.5,0.5)],
[(8,4),(5,2)],
[(3,9),(4.5,0.5)],
[(3,9),(5,2)],
[(4.5,0.5),(5,2)]];

This is the PPL code for mstTree(points, edges)

Code:

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

mstTree(points,edges):=
BEGIN
LOCAL vertices, tree, j, k, p, v, d1, d2, pointsd, n, temp;
vertices, tree := {points[1]}, {}
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 := vertices[j];
    FOR k FROM 1 TO pointsd DO
      p := points[k];
      IF contains(vertices, p) THEN continue END;      
      IF (d2 := abs(p-v)) >= d1 THEN continue END;
      IF NOT mstValid(edges, [p,v]) THEN continue END;
      d1, temp := d2, [p,v]
    END
  END
  tree[n] := temp;
  vertices[n+=1] := temp[1];
END
return tree;
END;
#end

Input pts, and edgs into HP Prime emulator, we get

CAS> r := mstTree(pts,edgs)

\(\left(\begin{array}{cc}
2.5+5.0*i & 3.0+4.5*i \\
1.0+5.0*i & 2.5+5.0*i \\
4.0+2.5*i & 3.0+4.5*i \\
5.0+2.0*i & 4.0+2.5*i \\
4.5+0.5*i & 5.0+2.0*i \\
2.0+2.0*i & 4.0+2.5*i \\
1.5+i & 2.0+2.0*i \\
7.0+3.0*i & 5.0+2.0*i \\
8.0+4.0*i & 7.0+3.0*i \\
5.0+6.5*i & 3.0+4.5*i \\
3.0+9.0*i & 5.0+6.5*i
\end{array}\right) \)

This matched the results of Lua code.
When plotted line segments, it matched your supplied image.

CAS> apply((x)->segment(x[0],x[1]),r)

Perhaps we should let the code make the valid edges ?
This way mstValid(edges, [p,v]) can be removed, with boost in speed.