RE: minimum spanning tree lua HPPL
(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
|