Mercurial > hg > STI-GWT

annotate war/scripts/sti/kruskal.js @ 41:90b7bbc9962f default

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged the bugfixes
author Sebastian Kruse <skruse@mpiwg-berlin.mpg.de>
date Thu, 06 Dec 2012 18:09:00 +0100
parents cf06b77a8bbd
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
1 var infinity = 100000000000; // !!! beware, not allowable for many applications
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
2
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
3 function Edge2(a, b, w) { this.v1=a; this.v2=b; this.wt=w; }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
4
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
5 function setEdgeAdjMatrix(i, j, w)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
6 { if(j > i) { var t=i; i=j; j=t; }//swap so that i >= j
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
7 this.matrix[i][j] = w;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
8 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
9
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
10
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
11 function randomAdjMatrix(pr) // allocate random edges with probability 'pr'; LA
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
12 { var i, j;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
13 for(i=0; i < this.Vertices; i++)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
14 { for(j=0; j < i; j++)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
15 { if(Math.random() <= pr)//LAllison, roll dice
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
16 this.setEdge(i, j, 1+Math.round(Math.random()*8)); // wt in [1..9]
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
17 } } }//randomAdjMatrix
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
18
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
19
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
20 function edgeWeightAdjMatrix(i,j)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
21 { return i >= j ? this.matrix[i][j] : this.matrix[j][i]; }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
22
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
23 function adjacentAdjMatrix(i, j)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
24 { return this.edgeWeight(i,j) < infinity; }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
25
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
26
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
27 function AdjMatrix(Vrtcs) // constructor for a Graph as an Adjacency Matrix
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
28 { this.Vertices = Vrtcs; // Vertices [0..Vrtcs-1]
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
29 this.edgeWeight = edgeWeightAdjMatrix; // These functions
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
30 this.adjacent = adjacentAdjMatrix; // and values
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
31 this.random = randomAdjMatrix;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
32 this.setEdge = setEdgeAdjMatrix;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
33
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
34 this.matrix = new Array(Vrtcs); // the Graph representation...
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
35 var i, j;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
36 for(i=0; i < Vrtcs; i++) // undirected graph so...
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
37 { this.matrix[i] = new Array(i+1); // symmetric => triangular !!!
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
38 for(j=0; j <= i; j++)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
39 this.setEdge(i, j, infinity); // no edges, yet
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
40 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
41 }//AdjMatrix
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
42
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
43 //-----------------------------------------------------------------------------
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
44
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
45 function AdjListCell(vert, w, next)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
46 { this.v = vert; this.wt = w; this.tl = next; }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
47
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
48 function AdjListFromAdjMatrix(GbyMatrix)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
49 { var v1, v2;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
50 this.Vertices = GbyMatrix.Vertices;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
51
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
52 for(v1=0; v1 < this.Vertices; v1++)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
53 { this.vertex[v1] = null; // clear
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
54
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
55 for(v2=this.Vertices-1; v2 >= v1; v2--) // v1 <= v2
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
56 { if(GbyMatrix.adjacent(v1, v2))
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
57 { var wt = GbyMatrix.edgeWeight(v1, v2);
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
58 this.vertex[v1] = new AdjListCell(v2, wt, this.vertex[v1]);
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
59 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
60 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
61 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
62 }//AdjListFromAdjMatrix
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
63
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
64 function AdjList(Vrtcs) // Constructor for a Graph by Adjacency Lists C
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
65 { this.Vertices = Vrtcs; // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
66 this.fromAdjMatrix = AdjListFromAdjMatrix; // m
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
67 // p
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
68 this.vertex = new Array(Vrtcs); // set up the adjacency lists .
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
69 var i; // S
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
70 for(i=0; i < Vrtcs; i++) this.vertex[i]=null; // c
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
71 }//AdjList i
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
72
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
73 //-----------------------------------------------------------------------------
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
74
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
75 function Prim(G)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
76 // Post: T[] is a minimum spanning tree of G and
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
77 // T[i-1] is the edge linking Vertex i into the tree
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
78 // Time complexity is O(|V|**2)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
79 { var T = new Array(G.Vertices-1);
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
80 var i;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
81 var done = new Array(G.Vertices);
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
82
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
83 done[0] = true; // initially T=<{0},{ }>
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
84 for(i = 1; i < G.Vertices; i++)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
85 { T[i-1] = new Edge2(0, i, G.edgeWeight(0,i));
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
86 done[i]=false;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
87 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
88
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
89 var dontCare;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
90 for(dontCare = 1; dontCare < G.Vertices; dontCare++)// |V|-1 times... L
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
91 // Invariant: T is a min' spanning sub-Tree of vertices in done A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
92 { // find the undone vertex that is closest to the Spanning (sub-)Tree l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
93 var minDist = infinity, closest = -1; // l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
94 for(i = 1; i < G.Vertices; i++) // i
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
95 if(! done[i] && T[i-1].wt <= minDist) // s
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
96 { minDist = T[i-1].wt; closest = i; } // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
97 done[closest] = true; // n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
98
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
99 for(i=1; i < G.Vertices; i++) // recompute undone proximities to T
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
100 if(! done[i])
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
101 { var Gci = G.edgeWeight(closest, i);
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
102 if(Gci < T[i-1].wt)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
103 { T[i-1].wt = Gci;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
104 T[i-1].v1 = closest;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
105 } } }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
106
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
107 return T;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
108 }//Prim
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
109
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
110 // ----------------------------------------------------------------------------
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
111
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
112 function PartitionMerge(s1, s2)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
113 // merge the smaller of subsets s1 and s2 into the larger of them. M
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
114 { var drop, keep; // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
115 if(this.subset[s1].nElts < this.subset[s2].nElts) // drop the smaller n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
116 { drop=s1; keep=s2; } // a
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
117 else // s
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
118 { drop=s2; keep=s1; } // h
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
119
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
120 var dropElt = this.subset[drop].firstElt; // each element in smaller subset
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
121 var done=false;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
122 while(! done)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
123 { this.elt[dropElt].setNumber = keep; // move the element to larger subset
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
124 if( this.elt[dropElt].nextElt < 0)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
125 done = true;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
126 else
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
127 dropElt = this.elt[dropElt].nextElt;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
128 }//end while
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
129
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
130 this.elt[dropElt].nextElt = this.subset[keep].firstElt; // join lists
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
131 this.subset[keep].firstElt = this.subset[drop].firstElt;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
132 this.subset[keep].nElts += this.subset[drop].nElts;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
133
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
134 this.subset[drop].firstElt = -1; // clear smaller subset
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
135 this.subset[drop].nElts = 0;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
136
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
137 this.size --; // one less subset in the partition
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
138 }//PartitionMerge
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
139
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
140
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
141 function PartitionEltCell(sn, nxt) { this.setNumber = sn; this.nextElt = nxt; }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
142
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
143 function PartitionSetCell(ne, fst) { this.nElts = ne; this.firstElt = fst; }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
144
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
145
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
146 function PartitionSingletons() // make {{0}, {1}, {2}, ...}
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
147 { var i;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
148 this.size = (this.elt).length; // # of subsets in the partition
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
149 for(i=0; i < this.size; i++)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
150 { this.elt[i] = new PartitionEltCell(i, -1);
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
151 this.subset[i] = new PartitionSetCell(1, i); // i.e. i is in {i}
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
152 } }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
153
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
154
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
155 function Partition(N) // A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
156 { this.elt = new Array(N); // elements -> subsets l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
157 this.subset = new Array(N); // subsets -> elements l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
158 // i
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
159 this.singletons = PartitionSingletons; // s
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
160 this.merge = PartitionMerge; // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
161 }//Partition constructor n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
162
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
163
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
164 function upHeap(e) // see PriorityQ L
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
165 // add e to the (smallest on top) heap, arr[1..size] A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
166 // PRE: arr[1..size] is a (smallest at top) heap / priority Q l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
167 // POST: arr[1..size] is a (bigger) heap, with e added l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
168 { this.size++; // i
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
169 var child = this.size, parent; // s
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
170 while(child > 1)//i.e. not top of heap // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
171 { parent = Math.floor(child / 2); // n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
172
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
173 if(this.arr[parent].wt > e.wt)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
174 this.arr[child] = this.arr[parent]; // move parent down
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
175 else
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
176 break; // found a place for e
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
177 child = parent;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
178 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
179
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
180 // either child==1, i.e. parentless, or parent is less than or eq to e
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
181 this.arr[child] = e;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
182 }//upHeap, L.Allison, Comp Sci and Software Engineering, Monash University
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
183
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
184
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
185 function downHeap(e)
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
186 // add e to the (smallest on top) heap, arr[2..size]
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
187 // PRE: arr[2..size] is a heap
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
188 // POST: arr[1..size] is a heap
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
189 { var parent = 1, child; // A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
190 while(2*parent <= this.size) // U
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
191 { child = 2*parent; // left child is 2*parent, right is 2*parent+1 // S
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
192 // T
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
193 if(child < this.size && this.arr[child+1].wt < this.arr[child].wt) // R
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
194 child++; // right child is smaller then left child // A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
195 // L
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
196 if(this.arr[child].wt < e.wt) // I
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
197 this.arr[parent] = this.arr[child]; // move the child up // I
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
198 else // A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
199 break; // found a place for e
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
200 parent = child;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
201 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
202
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
203 // either parent childless or child(ren) of parent are greater or eq to e
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
204 this.arr[parent] = e;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
205 }//downHeap, L.Allison, Comp Sci and Software Engineering, Monash University
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
206
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
207
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
208 function topHeap()
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
209 // PRE: this.size > 0
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
210 { var ans = this.arr[1]; // C
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
211 this.size--; // S
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
212 if(this.size <= 0) return ans; // S
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
213 //else // E
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
214 this.downHeap(this.arr[this.size+1]);
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
215 return ans;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
216 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
217
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
218
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
219 function PriorityQ() // A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
220 { this.arr = new Array(); // NB. never use arr[0] l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
221 this.size = 0; // so far l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
222 // i
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
223 this.pushq = upHeap; // s
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
224 this.popq = topHeap; this.downHeap = downHeap; // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
225 }//constructor n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
226
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
227
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
228 function Kruskal(G) // L
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
229 // G is a graph implemented by adjacency lists! A
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
230 // return a minimum spanning tree, T l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
231 { var i; // l
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
232 var T = new Array(); // to be the min' spanning tree i
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
233 // s
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
234 var Q = new PriorityQ(); // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
235 // n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
236 for(i=0; i < G.Vertices; i++)//first make a PriorityQ of all the edges of G
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
237 { var Gi = G.vertex[i];
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
238 while(Gi != null) // i.e. for each edge {i,v}
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
239 { Q.pushq(new Edge2(i, Gi.v, Gi.wt));
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
240 Gi = Gi.tl;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
241 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
242 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
243
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
244 var n = 0; // Computer Science
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
245 var P = new Partition(G.Vertices); // M
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
246 P.singletons(); // o
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
247 while(P.size > 1) // the min' spanning tree algorithm proper n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
248 { if(Q.size <= 0) // G disconnected a
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
249 break; // s
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
250 // h
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
251 var e = Q.popq(); // shortest edge
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
252 if(P.elt[e.v1].setNumber != P.elt[e.v2].setNumber) // U
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
253 { T[n] = e; n++; // n
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
254 P.merge(P.elt[e.v1].setNumber, P.elt[e.v2].setNumber); // i
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
255 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
256 }
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
257
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
258 return T;
cf06b77a8bbd Committed branch of the e4D repos sti-gwt branch 16384.
StefanFunk <StefanFunk@f2b5be40-def6-11e0-8a09-b3c1cc336c6b>
parents:
diff changeset
259 }//Kruskal, NB. can work on adjacency matrix, but is best on sparse graphs.