Mercurial > hg > STI-GWT

comparison war/scripts/sti/kruskal.js @ 3:cf06b77a8bbd

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