minimum spanning tree lua HPPL

[robmio]

(11-04-2021 03:47 PM)Albert Chan Wrote:  

(10-29-2021 10:52 AM)Albert Chan Wrote:  Instead of badEdges = [[p1,p2],[p2,p1], ...], we could simplify to [[1,2],[2,1], ...]

I thought it is trivial to supply 1 sided badEdges, then "doubled" them.
For python, joining two list is simply '+'

>>> bad = [[1,2],[3,6],[6,10]]
>>> bad2 = [ [k[1],k[0]] for k in bad]
>>> bad + bad2
[[1, 2], [3, 6], [6, 10], [2, 1], [6, 3], [10, 6]]

For HP Prime, close equivalent for '+' is extend.
But, instead of extending to end of list, it extend to items inside list.

Cas> bad := [[1,2],[3,6],[6,10]]
Cas> bad2 := map(bad, revserse)       → [[2,1],[6,3],[10,6]]
Cas> extend(bad, bad2)                     → [[1,2,2,1],[3,6,6,3],[6,10,10,6]]

To get what we wanted, we need to use transpose (3 times !)
This work, but ugly. Better solution welcome.

Cas> transpose(extend(transpose(bad), transpose(bad2))
[[1,2],[3,6],[6,10],[2,1],[6,3],[10,6]]


Version 5:

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([mj,mk], badEdges) THEN continue END;
      d1, temp := d2, [k, [mj,mk]];
    END
  END
  k, tree[n] =< temp;
  m[k] =< m[n += 1];            // swap m[k], m[n+1]
  m[n] =< temp[2][2];
END
return tree;
END;
#end

Since it is more natural to read from left to right, I flip the order.
Also, HP Prime always create a new list, even for just updating element.
We might as well update list element by reference, '=<' instead of ':='

OP example:

Cas> pts := [[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]]
Cas> mstTree(pts, [])
[[1,4],[4,2],[1,7],[7,12],[12,11],[7,8],[8,6],[12,5],[5,9],[1,3],[3,10]]

It is easier to sketch the tree.

3 10
|
1 4 2
|
7 12 11
| |
| 5 9
|
8 6

Indeed, it is easier to view the entire tree