Source code: com/port80/graph/dot/impl/Anneal_Test01.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.ArrayList;
8 import java.util.HashMap;
9 import java.util.List;
10 import java.util.Map;
11
12 import junit.framework.Assert;
13 import junit.framework.Test;
14 import junit.framework.TestCase;
15 import junit.framework.TestSuite;
16
17 import com.port80.graph.IGraph;
18 import com.port80.graph.dot.impl.GridFactory.GridIterator;
19 import com.port80.util.Debug;
20 import com.port80.util.msg;
21 import com.port80.util.struct.IntKeyHashMap;
22 import com.port80.util.struct.IntList;
23 import com.port80.util.struct.IntValueHashMap;
24
25 /**
26 * Check Anneal() rank cost calculation methods.
27 *
28 * @author chrisl
29 */
30 public class Anneal_Test01 extends TestCase {
31
32 ////////////////////////////////////////////////////////////////////////
33
34 private static final String NAME = "AnnealTest_01";
35 private static final boolean DEBUG = false;
36 private static boolean CHECK = true;
37 private static boolean VERBOSE = Debug.isVerbose();
38
39 private static Map opts = new HashMap();
40
41 ////////////////////////////////////////////////////////////////////////
42
43 IGraph fGraph;
44 VirtualGraph fVGraph;
45 Anneal fAnneal;
46
47 ////////////////////////////////////////////////////////////////////////
48
49 public Anneal_Test01(String name) {
50 super(name);
51 if (VERBOSE)
52 msg.println("### testRankCost01()");
53 // The simplest 2-4-2 fully connected graph.
54 String testGraph =
55 "digraph testRankCost01"
56 + "{"
57 + "01->11; 01->12; 01->13; 01->14; "
58 + "02->11; 02->12; 02->13; 02->14; "
59 + "11->21; 12->21; 13->21; 14->21; "
60 + "11->22; 12->22; 13->22; 14->22; "
61 + "11->31; 22->31; "
62 + "}";
63 fGraph = TestUtil.createGraph(testGraph);
64 fVGraph = new VirtualGraph(fGraph);
65 MinCross.dot(fVGraph, 0, 6, 0);
66 fVGraph.removeAux();
67 Position.dotPosition(fVGraph);
68 if (DEBUG) {
69 // Save graph layout.
70 Position.saveResult(fVGraph);
71 TestUtil.updateShape(fGraph);
72 Route.dot(fVGraph);
73 msg.println(fGraph.sprintGraph());
74 TestUtil.saveImage("out/test/testAnneal_01", 1f, fGraph);
75 }
76 fVGraph.sanityCheck();
77 //
78 // Test Anneal and ErasedPath methods.
79 //
80 fAnneal = new Anneal(fVGraph, 1);
81 }
82
83 ////////////////////////////////////////////////////////////////////////
84
85 public void testRankCost01() {
86 String PREFIX = NAME + ".checkRankCost(): ";
87 if (VERBOSE)
88 msg.println("\n### " + PREFIX);
89 Anneal anneal=fAnneal;
90 VirtualGraph vgraph=fVGraph;
91 int cost;
92 int[] expects;
93 //
94 int xpenalty = vgraph.fXPENALTY_DEFAULT;
95 int xpenalty2=xpenalty*xpenalty;
96 int expected = 6 * xpenalty2;
97 int r = vgraph.minRank;
98 VirtualGraph.Rank rank = vgraph.ranks[r];
99 VirtualGraph.Rank rank1 = vgraph.ranks[r + 1];
100 VirtualVertex v01 = vgraph.getVertex("01");
101 VirtualVertex v02 = vgraph.getVertex("02");
102 //
103 // In this, the imaginary cross costs are same as real cross costs in rank 0.
104 if (CHECK) {
105 cost = vgraph.ranks[r].crossCost;
106 Assert.assertTrue("expected=" + expected + ", actual=" + cost, cost == expected);
107 cost = vgraph.ranks[r + 1].crossCost;
108 Assert.assertTrue("expected=" + expected + ", actual=" + cost, cost == expected);
109 }
110 //
111 // Check rankCostRemoveEdge()
112 //
113 VirtualEdge ee;
114 if (v01.order == 0)
115 ee = v01.findOutChain(rank1.vts[rank1.nVts - 1]);
116 else
117 ee = v01.findOutChain(rank1.vts[0]);
118 vgraph.ranks[r].saveCrossCost();
119 vgraph.rankCostRemoveEdge(ee);
120 if (VERBOSE) {
121 printCrossCost(v01);
122 printCrossCost(v02);
123 }
124 if (CHECK) {
125 cost = vgraph.ranks[r].crossCost;
126 Assert.assertTrue("expected=" + expected + ", actual=" + cost, cost == expected);
127 }
128 //
129 expects = new int[] {0,xpenalty,2*xpenalty,3*xpenalty};
130 for (int i = 0; i < v01.crossCost.length; ++i) {
131 cost = v01.crossCost[i];
132 if (CHECK) {
133 expected = expects[i];
134 Assert.assertTrue(
135 "i=" + i + ", expected=" + expected + ", actual=" + cost,
136 cost == expected);
137 }
138 }
139 //
140 expects = new int[] { 2*xpenalty, xpenalty, 0, 0};
141 for (int i = 0; i < v02.crossCost.length; ++i) {
142 cost = v02.crossCost[i];
143 expected = expects[i];
144 if (CHECK) {
145 Assert.assertTrue(
146 "i=" + i + ", expected=" + expected + ", actual=" + cost,
147 cost == expected);
148 }
149 }
150 //
151 // Check crossAfter(), crossAfterBefore, crossBeforeAfter return correct cost.
152 //
153 VirtualVertex tail, head, beforetail, beforehead;
154 VirtualEdge e;
155 Grid parent, child;
156 //
157 if (VERBOSE)
158 msg.println("# tail->head");
159
160 expects = new int[] { 0, xpenalty2, 2*xpenalty2, 3*xpenalty2, 2*xpenalty2, xpenalty2, 0, 0};
161 int n = 0;
162 for (int tn = 0; tn < rank.nVts; ++tn) {
163 tail = rank.vts[tn];
164 beforetail = tail;
165 for (int hn = 0; hn < rank1.nVts; ++hn) {
166 head = rank1.vts[hn];
167 beforehead = head;
168 e = tail.findOutChain(head);
169 parent = Grid.newVertexGrid(tail);
170 child = Grid.newVertexGrid(head);
171 cost = anneal.crossAfter(parent, child, beforetail, beforehead, e);
172 if (CHECK) {
173 expected = expects[n++];
174 Assert.assertTrue("expected=" + expected + ", cost=" + cost, cost == expected);
175 }
176 if (VERBOSE)
177 msg.println(
178 "tn="
179 + tn
180 + ", hn="
181 + hn
182 + ", tail="
183 + tail.getName()
184 + ", head="
185 + head.getName()
186 + ", cost="
187 + cost);
188 }
189 }
190 //
191 // Crosscost for tail->space before head.
192 //
193 if (VERBOSE)
194 msg.println("# tail->space before head");
195 expects = new int[] { 0, xpenalty2, 2*xpenalty2, 3*xpenalty2, 3*xpenalty2, 2*xpenalty2, xpenalty2, 0 };
196 n = 0;
197 for (int tn = 0; tn < rank.nVts; ++tn) {
198 tail = rank.vts[tn];
199 beforetail = tail;
200 beforehead = null;
201 for (int hn = 0; hn < rank1.nVts; ++hn) {
202 head = rank1.vts[hn];
203 e = tail.findOutChain(head);
204 parent = Grid.newVertexGrid(tail);
205 child = Grid.newSpaceGrid(head.rank, head.x, 0, 0);
206 cost = anneal.crossAfter(parent, child, beforetail, beforehead, e);
207 if (CHECK) {
208 expected = expects[n++];
209 Assert.assertTrue("expected=" + expected + ", cost=" + cost, cost == expected);
210 }
211 if (VERBOSE)
212 msg.println(
213 "tn="
214 + tn
215 + ", hn="
216 + hn
217 + ", tail="
218 + tail.getName()
219 + ", head="
220 + head.getName()
221 + ", cost="
222 + cost);
223 beforehead = head;
224 }
225 }
226 //
227 // Crosscost for tail->space after head.
228 //
229 if (VERBOSE)
230 msg.println("# tail->space after head");
231 //expects = new int[] { 256, 512, 768, 1024, 512, 256, 0, 0 };
232 expects = new int[] { xpenalty2, 2*xpenalty2, 3*xpenalty2, 4*xpenalty2, 2*xpenalty2, xpenalty2, 0, 0};
233 n = 0;
234 for (int tn = 0; tn < rank.nVts; ++tn) {
235 tail = rank.vts[tn];
236 beforetail = tail;
237 for (int hn = 0; hn < rank1.nVts; ++hn) {
238 head = rank1.vts[hn];
239 beforehead = head;
240 e = tail.findOutChain(head);
241 parent = Grid.newVertexGrid(tail);
242 child = Grid.newSpaceGrid(head.rank, head.x, 0, 0);
243 cost = anneal.crossAfter(parent, child, beforetail, beforehead, e);
244 expected = expects[n++];
245 Assert.assertTrue("expected=" + expected + ", cost=" + cost, cost == expected);
246 if (VERBOSE)
247 msg.println(
248 "tn="
249 + tn
250 + ", hn="
251 + hn
252 + ", tail="
253 + tail.getName()
254 + ", head="
255 + head.getName()
256 + ", cost="
257 + cost);
258 }
259 }
260 //
261 // Check saveRankCost(), restoreRankCost() and checkRankCost()s.
262 //
263 boolean ok;
264 rank.restoreCrossCost();
265 ok = vgraph.checkCrossCosts();
266 if (CHECK) {
267 Assert.assertTrue("checkCrossCosts FAILED", ok);
268 }
269 vgraph.rankCostRemoveEdge(ee);
270 if (CHECK)
271 msg.println("# Expected 3 mismatches:");
272 ok = vgraph.checkCrossCosts();
273 if (CHECK) {
274 Assert.assertTrue("Expected 3 mismatches", !ok);
275 }
276 }
277
278 /**
279 * Check ErasedPath.erase() return correct cross cost (0) after erasing 11->31
280 * (ignoring distance costs).
281 */
282 public void testErasedPath() {
283 String PREFIX = NAME + ".checkErasedPath(): 1: ";
284 if (VERBOSE)
285 msg.println("\n### " + PREFIX);
286 //
287 Anneal anneal=fAnneal;
288 VirtualGraph vgraph=fVGraph;
289 //
290 int x = vgraph.fXPENALTY_DEFAULT;
291 int r = vgraph.minRank;
292 VirtualGraph.Rank rank1 = vgraph.ranks[r + 1];
293 VirtualGraph.Rank rank2 = vgraph.ranks[r + 2];
294 float expected, cost;
295 //
296 vgraph.staticCost();
297 ErasedPath erased = new ErasedPath(vgraph);
298 //
299 // Erase, restore and check that nothing changed.
300 //
301 VirtualVertex v11 = vgraph.getVertex("11");
302 VirtualVertex v31 = vgraph.getVertex("31");
303 VirtualEdge e = v11.findOutChain(v31);
304 Assert.assertTrue(PREFIX + "e!=null", e != null);
305 // To avoid travel costs, clear all vertex.x just for testing.
306 IntValueHashMap savedx = new IntValueHashMap(5);
307 clearVertexX(e, savedx);
308 cost = erased.erase(new VirtualChain(e), true);
309 if (VERBOSE)
310 msg.println("erased=" + erased);
311 if (CHECK) {
312 Assert.assertTrue(PREFIX + "expected=0, cost=" + cost, cost == 0);
313 }
314 // Erased cost==0, rank cost already restored by ErasedPath.erase().
315 restoreVertexX(e, savedx);
316 vgraph.sanityCheck();
317 vgraph.checkCrossCosts();
318 //
319 // As above but erase a chain that have cross cost (01->ranks[1]).
320 //
321 PREFIX = NAME + ".checkErasedPath(): 2: ";
322 VirtualVertex v01 = vgraph.getVertex("01");
323 if (v01.order == 0)
324 e = v01.findOutChain(rank1.vts[rank1.nVts - 1]);
325 else
326 e = v01.findOutChain(rank1.vts[0]);
327 Assert.assertTrue(PREFIX + "e!=null", e != null);
328 savedx = new IntValueHashMap(5);
329 clearVertexX(e, savedx);
330 cost = erased.erase(new VirtualChain(e), false);
331 if (VERBOSE) {
332 msg.println("# checkErasedPath: cost=" + cost);
333 }
334 if (CHECK) {
335 expected = 3 * x * x + vgraph.fCELL_BASICFACTOR;
336 Assert.assertTrue(PREFIX + "expected=" + expected + ", cost=" + cost, cost == expected);
337 }
338 // Restore path and check cross costs not changed.
339 erased.restore();
340 restoreVertexX(e, savedx);
341 vgraph.sanityCheck();
342 vgraph.checkCrossCosts();
343 }
344
345 ////////////////////////////////////////////////////////////////////////
346
347 // Helpers /////////////////////////////////////////////////////////////
348 //
349
350 private void printCrossCost(VirtualVertex v) {
351 StringBuffer buf = new StringBuffer(v.getName() + ": ");
352 for (int i = 0; i < v.crossCost.length; ++i)
353 buf.append(v.crossCost[i] + " ");
354 msg.println(buf.toString());
355 }
356
357 /** Save the x-coordinates of the vertices in the given chain. */
358 private void clearVertexX(VirtualEdge chaintail, IntValueHashMap savedx) {
359 if (savedx == null)
360 savedx = new IntValueHashMap(5);
361 for (VirtualEdge e = chaintail; e != null; e = e.next) {
362 savedx.put(e.tail, e.tail.x);
363 savedx.put(e.head, e.head.x);
364 e.tail.x = 0;
365 e.head.x = 0;
366 }
367 }
368
369 /** Restore the x-coordinates of the vertices in the given chain. */
370 private void restoreVertexX(VirtualEdge chaintail, IntValueHashMap savedx) {
371 for (VirtualEdge e = chaintail; e != null; e = e.next) {
372 e.tail.x = savedx.get(e.tail);
373 e.head.x = savedx.get(e.head);
374 }
375 }
376
377 // Main ////////////////////////////////////////////////////////////////
378 //
379
380 public static void main(String[] args) {
381 args = msg.getArgs(opts, "AnnealTest_01", args, "- verbose=v nocheck=c");
382 if (opts.get("verbose") != null) {
383 Debug.enable("verbose");
384 VERBOSE = true;
385 }
386 if (opts.get("nocheck") != null) {
387 CHECK = false;
388 }
389 junit.textui.TestRunner.run(new TestSuite(Anneal_Test01.class));
390 // junit.swingui.TestRunner.run(new TestVirtualGraph("TestVirtualGraph").getClass());
391 }
392
393 ////////////////////////////////////////////////////////////////////////
394 }