Post Reply 
minimum spanning tree lua HPPL
10-28-2021, 06:54 PM
Post: #6
RE: minimum spanning tree lua HPPL
(10-28-2021 05:31 PM)Albert Chan Wrote:  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

Very good!
I ask a question: what if the points in the sample are not represented by a pair of numbers, but by three or four numbers, as in multivariate statistics? For instance:
points: = {{15,17,24,14}, {17,15,32,26}, {15,14,29,23}, {13,12,10,16}, {20,17,26,28}, {15,21,26,21}}.

edges:={{15,17,24,14,17,15,32,26,15,17,24,14,15,14,29,23,15,17,24,14,13,12,10,16​,15,17,24,14,20,17,26,28,15,17,24,14,15,21,26,21},{17,15,32,26,15,14,29,23,17,15​,32,26,13,12,10,16,17,15,32,26,20,17,26,28,17,15,32,26,15,21,26,21},{15,14,29,23​,13,12,10,16,15,14,29,23,20,17,26,28,15,14,29,23,15,21,26,21},{13,12,10,16,20,17​,26,28,13,12,10,16,15,21,26,21},{20,17,26,28,15,21,26,21}}.

With these points and edges, "my" code results in:

[[17,15,15,17],[15,14,17,15],[13,12,15,14],[20,17,17,15],[15,21,15,17]].

With these points and edges, what does your code provide, Albert?
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
minimum spanning tree lua HPPL - robmio - 10-28-2021, 01:04 PM
RE: minimum spanning tree lua HPPL - robmio - 10-28-2021 06:54 PM



User(s) browsing this thread: 1 Guest(s)