1 cananian 1.3.2.4 // Partition.java, created Mon Nov 16 23:33:21 1998 by mfoltz
2 cananian 1.3.2.4 // Copyright (C) 1998 Mark A. Foltz <mfoltz@ai.mit.edu>
3 cananian 1.3.2.4 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.3.2.4
5 mfoltz 1.1 // -*-Mode: Java-*-
6 mfoltz 1.1 // Partition.java --
7 mfoltz 1.1 // Author: Mark Foltz <mfoltz@ai.mit.edu>
8 mfoltz 1.1 // Maintainer: Mark Foltz <mfoltz@ai.mit.edu>
9 mfoltz 1.1 // Version:
10 mfoltz 1.1 // Created: <Fri Oct 23 00:24:17 1998>
11 mfoltz 1.4 // Time-stamp: <1998-11-26 11:47:57 mfoltz>
12 mfoltz 1.1 // Keywords:
13 mfoltz 1.1
14 mfoltz 1.2 package harpoon.Analysis.Partition;
15 mfoltz 1.1
16 mfoltz 1.1 import java.util.Enumeration;
17 mfoltz 1.1 import java.util.Vector;
18 mfoltz 1.1
19 mfoltz 1.1 /**
20 mfoltz 1.1 *
21 mfoltz 1.1 * @author Mark A. Foltz <mfoltz@ai.mit.edu>
22 cananian 1.5 * @version $Id: Partition.java,v 1.5 2002/02/25 20:58:28 cananian Exp $
23 mfoltz 1.1 */
24 mfoltz 1.1
25 mfoltz 1.1 public class Partition {
26 mfoltz 1.1
27 mfoltz 1.1 public static void initialPartition(WeightedGraph g, int k, WeightedGraph p[]) {
28 mfoltz 1.1
29 mfoltz 1.1 Enumeration nodes;
30 mfoltz 1.1 WGNode node;
31 mfoltz 1.1
32 mfoltz 1.1 p[0] = new WeightedGraph();
33 mfoltz 1.1 p[1] = new WeightedGraph();
34 mfoltz 1.4
35 mfoltz 1.4 nodes = g.getNodes();
36 mfoltz 1.4 while (nodes.hasMoreElements()) {
37 mfoltz 1.4 node = (WGNode) nodes.nextElement();
38 mfoltz 1.4 if (node._binding > -1) p[node._binding].addNode(node);
39 mfoltz 1.4 }
40 mfoltz 1.1
41 mfoltz 1.1 nodes = g.getNodes();
42 mfoltz 1.1 while (p[0].size() < g.size()/2) {
43 mfoltz 1.1 node = (WGNode) nodes.nextElement();
44 mfoltz 1.4 if (node._binding < 0) p[0].addNode(node);
45 mfoltz 1.1 }
46 mfoltz 1.1
47 mfoltz 1.1 while (nodes.hasMoreElements()) {
48 mfoltz 1.1 node = (WGNode) nodes.nextElement();
49 mfoltz 1.4 if (node._binding < 0) p[1].addNode(node);
50 mfoltz 1.1 }
51 mfoltz 1.1
52 mfoltz 1.1 return;
53 mfoltz 1.1
54 mfoltz 1.1 }
55 mfoltz 1.1
56 mfoltz 1.3 public static long exchange(WeightedGraph g1, WeightedGraph g2) throws Exception {
57 mfoltz 1.1
58 mfoltz 1.1 // we assume g1 and g2 are the same size
59 mfoltz 1.1
60 mfoltz 1.3 int size = g1.size();
61 mfoltz 1.3 if (size != g2.size()) throw new Exception("exchange bailed on graphs of unequal size!!!");
62 mfoltz 1.3
63 mfoltz 1.1 // set up A and B
64 mfoltz 1.1
65 mfoltz 1.1 WGNode node;
66 mfoltz 1.1 int pair[] = new int[2], i, j;
67 mfoltz 1.1 Enumeration nodes;
68 mfoltz 1.1
69 mfoltz 1.3 // clone the WeightedGraphs into A and B.
70 mfoltz 1.3
71 mfoltz 1.1 WeightedGraph A = new WeightedGraph(g1);
72 mfoltz 1.1 WeightedGraph B = new WeightedGraph(g2);
73 mfoltz 1.1
74 mfoltz 1.1 // fixPartition will fix the pointers of external edges.
75 mfoltz 1.1
76 mfoltz 1.1 fixPartition(A,B);
77 mfoltz 1.1 fixPartition(B,A);
78 mfoltz 1.1
79 mfoltz 1.1 // System.err.print(A);
80 mfoltz 1.1 // System.err.print(B);
81 mfoltz 1.1
82 mfoltz 1.1 // WeightedGraph A = g1;
83 mfoltz 1.1 // WeightedGraph B = g2;
84 mfoltz 1.1
85 mfoltz 1.1 // compute initial D values
86 mfoltz 1.1
87 mfoltz 1.1 recomputeD(A.getNodes(),A,B);
88 mfoltz 1.1 recomputeD(B.getNodes(),B,A);
89 mfoltz 1.1
90 mfoltz 1.3 WGNode X[] = new WGNode[size];
91 mfoltz 1.3 WGNode Y[] = new WGNode[size];
92 mfoltz 1.3 long gains[] = new long[size];
93 mfoltz 1.1
94 mfoltz 1.3 for (i = 0; i < size; i++) {
95 mfoltz 1.1
96 mfoltz 1.1 // System.err.print("A:\n"+A);
97 mfoltz 1.1 // System.err.print("B:\n"+B);
98 mfoltz 1.1
99 mfoltz 1.1 // create sorted lists of the Ds
100 mfoltz 1.1
101 mfoltz 1.1 WGNode Ap[] = new WGNode[A.size()];
102 mfoltz 1.1 WGNode Bp[] = new WGNode[B.size()];
103 mfoltz 1.1
104 mfoltz 1.1 nodes = A.getNodes();
105 mfoltz 1.1 for (j = 0; j < A.size(); j++) {
106 mfoltz 1.1 node = (WGNode) nodes.nextElement();
107 mfoltz 1.1 Ap[j] = node;
108 mfoltz 1.1 }
109 mfoltz 1.1
110 mfoltz 1.1 nodes = B.getNodes();
111 mfoltz 1.1 for (j = 0; j < B.size(); j++) {
112 mfoltz 1.1 node = (WGNode) nodes.nextElement();
113 mfoltz 1.1 Bp[j] = node;
114 mfoltz 1.1 }
115 mfoltz 1.1
116 mfoltz 1.1 // sort the lists of nodes by D and find a pair to exchange
117 mfoltz 1.1
118 mfoltz 1.1 quicksort(Ap,0,Ap.length-1);
119 mfoltz 1.1 quicksort(Bp,0,Bp.length-1);
120 mfoltz 1.1
121 mfoltz 1.3 System.err.print("Ap: ");
122 mfoltz 1.1 for (j = 0; j < Ap.length; j++)
123 mfoltz 1.3 System.err.print("Ap["+Ap[j]._name+"]="+Ap[j]._d+" ");
124 mfoltz 1.1 System.err.print("\n");
125 mfoltz 1.1
126 mfoltz 1.3 System.err.print("Bp: ");
127 mfoltz 1.1 for (j = 0; j < Bp.length; j++)
128 mfoltz 1.3 System.err.print("Bp["+Bp[j]._name+"]="+Bp[j]._d+" ");
129 mfoltz 1.1 System.err.print("\n");
130 mfoltz 1.1
131 mfoltz 1.3 // System.err.print("Bp[] = ");
132 mfoltz 1.3 // for (j = 0; j < Bp.length; j++)
133 mfoltz 1.3 // System.err.print(Bp[j]._d+" ");
134 mfoltz 1.3 // System.err.print("\n");
135 mfoltz 1.3
136 mfoltz 1.1 gains[i] = findBestPair(Ap, Bp, pair);
137 mfoltz 1.1
138 mfoltz 1.1 System.err.println("Best pair: Ap["+Ap[pair[0]]._name+"] = "+Ap[pair[0]]._d+", Bp["+Bp[pair[1]]._name+"] = "+Bp[pair[1]]._d+"\n");
139 mfoltz 1.1
140 mfoltz 1.1 // now put the exchange pair into X, Y and remove from A, B
141 mfoltz 1.1
142 mfoltz 1.1 X[i] = Ap[pair[0]];
143 mfoltz 1.1 Y[i] = Bp[pair[1]];
144 mfoltz 1.1
145 mfoltz 1.3 A.removeNode(X[i]);
146 mfoltz 1.3 B.removeNode(Y[i]);
147 mfoltz 1.1
148 mfoltz 1.1 // recompute Ds for nodes adjacent to the pair
149 mfoltz 1.1
150 mfoltz 1.3 recomputeD(X[i].getAdjacent(),A,B);
151 mfoltz 1.3 recomputeD(Y[i].getAdjacent(),B,A);
152 mfoltz 1.1 }
153 mfoltz 1.1
154 mfoltz 1.1 // find k to maximize total gain
155 mfoltz 1.1
156 mfoltz 1.1 int k = -1;
157 mfoltz 1.1 long gain = 0, max_gain = 0;
158 mfoltz 1.1
159 mfoltz 1.3 for (i = 0; i < size; i++) {
160 mfoltz 1.3 gain = WeightedGraph.weightPlus(gain,gains[i]);
161 mfoltz 1.1 if (gain > max_gain) {
162 mfoltz 1.1 max_gain = gain;
163 mfoltz 1.1 k = i;
164 mfoltz 1.1 }
165 mfoltz 1.1 }
166 mfoltz 1.1
167 mfoltz 1.1 // swap it
168 mfoltz 1.3 if (max_gain > 0) {
169 mfoltz 1.3
170 mfoltz 1.3 for (i = 0; i <= k; i++) {
171 mfoltz 1.3 System.err.println("exchange "+X[i]._name+" and "+Y[i]._name);
172 mfoltz 1.3 WeightedGraph.exchange(g1, X[i], g2, Y[i]);
173 mfoltz 1.3 }
174 mfoltz 1.1
175 mfoltz 1.1 }
176 mfoltz 1.1
177 mfoltz 1.1 return max_gain;
178 mfoltz 1.1
179 mfoltz 1.1 }
180 mfoltz 1.1
181 mfoltz 1.1 // traverse the lists and pick the best pair a, b to exchange.
182 mfoltz 1.1 private static long findBestPair(WGNode Ap[], WGNode Bp[], int pair[]) {
183 mfoltz 1.1
184 mfoltz 1.1 long gain, max_gain = 0;
185 mfoltz 1.1 int i = 0, j = 0, k;
186 mfoltz 1.1 pair[0] = 0;
187 mfoltz 1.1 pair[1] = 0;
188 mfoltz 1.1
189 mfoltz 1.1 while (i < Ap.length-1 || j < Bp.length-1) {
190 mfoltz 1.1
191 mfoltz 1.1 for (k = 0; k <= j; k++) {
192 mfoltz 1.1 // if (Ap[i]._d + Bp[k]._d < max_gain) return;
193 mfoltz 1.3 gain = WeightedGraph.weightPlus(WeightedGraph.weightPlus(Ap[i]._d,Bp[k]._d),
194 mfoltz 1.3 WeightedGraph.weightPlus(-Ap[i].getWeight(Bp[k]),
195 mfoltz 1.3 -Ap[i].getWeight(Bp[k])));
196 mfoltz 1.3 System.err.print("gain("+Ap[i]._name+","+Bp[k]._name+")="+gain+"; ");
197 mfoltz 1.1 if (gain > max_gain) {
198 mfoltz 1.1 max_gain = gain;
199 mfoltz 1.1 pair[0] = i;
200 mfoltz 1.1 pair[1] = k;
201 mfoltz 1.1 }
202 mfoltz 1.1 }
203 mfoltz 1.1
204 mfoltz 1.1 for (k = 0; k < i; k++) {
205 mfoltz 1.3 if (WeightedGraph.weightPlus(Ap[k]._d,Bp[j]._d) < max_gain) return max_gain;
206 mfoltz 1.3 gain = WeightedGraph.weightPlus(WeightedGraph.weightPlus(Ap[k]._d,Bp[j]._d),
207 mfoltz 1.3 WeightedGraph.weightPlus(-Ap[k].getWeight(Bp[j]),
208 mfoltz 1.3 -Ap[k].getWeight(Bp[j])));
209 mfoltz 1.3 System.err.print("gain("+Ap[k]._name+","+Bp[j]._name+")="+gain+"; ");
210 mfoltz 1.1 if (gain > max_gain) {
211 mfoltz 1.1 max_gain = gain;
212 mfoltz 1.1 pair[0] = k;
213 mfoltz 1.1 pair[1] = j;
214 mfoltz 1.1 }
215 mfoltz 1.1 }
216 mfoltz 1.1
217 mfoltz 1.1 if (i < Ap.length-1) i++;
218 mfoltz 1.1 if (j < Bp.length-1) j++;
219 mfoltz 1.1
220 mfoltz 1.1 }
221 mfoltz 1.1
222 mfoltz 1.1 System.err.print("\n");
223 mfoltz 1.1
224 mfoltz 1.1 return max_gain;
225 mfoltz 1.1 }
226 mfoltz 1.1
227 mfoltz 1.1
228 mfoltz 1.1 // recompute D for nodes in the enumeration, some subset of g1
229 mfoltz 1.1 private static void recomputeD(Enumeration nodes, WeightedGraph g1, WeightedGraph g2) {
230 mfoltz 1.1
231 mfoltz 1.1 Enumeration adjacents, weights;
232 mfoltz 1.1 WGNode node, adjacent;
233 mfoltz 1.1 Long weight;
234 mfoltz 1.1
235 mfoltz 1.1 while (nodes.hasMoreElements()) {
236 mfoltz 1.1 node = (WGNode) nodes.nextElement();
237 mfoltz 1.1 node._d = 0;
238 mfoltz 1.1 adjacents = node.getAdjacent();
239 mfoltz 1.1 weights = node.getWeights();
240 mfoltz 1.1 while (adjacents.hasMoreElements()) {
241 mfoltz 1.1 adjacent = (WGNode) adjacents.nextElement();
242 mfoltz 1.1 weight = (Long) weights.nextElement();
243 mfoltz 1.1 if (g1.contains(adjacent))
244 mfoltz 1.3 node._d = WeightedGraph.weightPlus(node._d,-weight.longValue());
245 mfoltz 1.3 // node._d -= weight.longValue();
246 mfoltz 1.1 else if (g2.contains(adjacent))
247 mfoltz 1.3 node._d = WeightedGraph.weightPlus(node._d,weight.longValue());
248 mfoltz 1.3 // node._d += weight.longValue();
249 mfoltz 1.1 }
250 mfoltz 1.1 }
251 mfoltz 1.1
252 mfoltz 1.1 }
253 mfoltz 1.1
254 mfoltz 1.3 // sort nodes in descending order by D.
255 mfoltz 1.1 private static void quicksort(WGNode X[], int i, int j) {
256 mfoltz 1.1
257 mfoltz 1.1 // System.err.println("quicksort(X[],"+i+","+j+")\n");
258 mfoltz 1.1
259 mfoltz 1.1 if (i >= j) return;
260 mfoltz 1.1 else {
261 mfoltz 1.1 long pivot = X[i]._d;
262 mfoltz 1.1 int k = i;
263 mfoltz 1.1 int m = j;
264 mfoltz 1.1 WGNode temp;
265 mfoltz 1.1 while (k < m) {
266 mfoltz 1.3 while (X[k]._d > pivot && (k < m)) k++;
267 mfoltz 1.3 while (X[m]._d <= pivot && (k < m)) m--;
268 mfoltz 1.1 if (k != m) {
269 mfoltz 1.1 temp = X[m];
270 mfoltz 1.1 X[m] = X[k];
271 mfoltz 1.1 X[k] = temp;
272 mfoltz 1.1 }
273 mfoltz 1.1 }
274 mfoltz 1.1 if (j == i + 1) return;
275 mfoltz 1.1 else {
276 mfoltz 1.1 quicksort(X,i,k);
277 mfoltz 1.1 quicksort(X,k+1,j);
278 mfoltz 1.1 }
279 mfoltz 1.1 }
280 mfoltz 1.1 return;
281 mfoltz 1.1 }
282 mfoltz 1.1
283 mfoltz 1.1 private static void fixPartition(WeightedGraph A, WeightedGraph B) {
284 mfoltz 1.1
285 mfoltz 1.1 // fix up edge pointers in A to point to nodes in B.
286 mfoltz 1.1
287 mfoltz 1.1 Enumeration nodes;
288 mfoltz 1.1 WGNode node, to, oldto;
289 mfoltz 1.1 int i;
290 mfoltz 1.1
291 mfoltz 1.1 nodes = A.getNodes();
292 mfoltz 1.1 while (nodes.hasMoreElements()) {
293 mfoltz 1.1 node = (WGNode) nodes.nextElement();
294 mfoltz 1.1 for (i = 0; i < node._edges.size(); i++) {
295 mfoltz 1.1 oldto = (WGNode) node._edges.elementAt(i);
296 mfoltz 1.1 to = B.getNode(oldto._name);
297 mfoltz 1.1 if (to != null) node._edges.setElementAt(to,i);
298 mfoltz 1.1 }
299 mfoltz 1.1 }
300 mfoltz 1.1 }
301 mfoltz 1.1
302 mfoltz 1.1 public static long computeEdgeSum(WeightedGraph g1, WeightedGraph g2) {
303 mfoltz 1.1
304 mfoltz 1.1 Enumeration nodes;
305 mfoltz 1.1 WGNode node, to;
306 mfoltz 1.1 int i;
307 mfoltz 1.1 long sum = 0;
308 mfoltz 1.1
309 mfoltz 1.1 nodes = g1.getNodes();
310 mfoltz 1.1 while (nodes.hasMoreElements()) {
311 mfoltz 1.1 node = (WGNode) nodes.nextElement();
312 mfoltz 1.1 for (i = 0; i < node._edges.size(); i++) {
313 mfoltz 1.1 to = (WGNode) node._edges.elementAt(i);
314 mfoltz 1.1 if (g2.contains(to)) {
315 mfoltz 1.3 sum = WeightedGraph.weightPlus(sum,((Long) node._weights.elementAt(i)).longValue());
316 mfoltz 1.1 }
317 mfoltz 1.1 }
318 mfoltz 1.1 }
319 mfoltz 1.1
320 mfoltz 1.1 return sum;
321 mfoltz 1.1
322 mfoltz 1.1 }
323 mfoltz 1.1
324 mfoltz 1.1
325 mfoltz 1.1
326 mfoltz 1.1 }
327 mfoltz 1.1