Source code: com/port80/graph/dot/impl/Anneal_Test02.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.io.File;
8 import java.util.ArrayList;
9 import java.util.HashMap;
10 import java.util.List;
11 import java.util.Map;
12 import java.util.Random;
13
14 import junit.framework.Assert;
15 import junit.framework.Test;
16 import junit.framework.TestCase;
17 import junit.framework.TestSuite;
18
19 import com.port80.graph.IGraph;
20 import com.port80.util.Debug;
21 import com.port80.util.msg;
22
23 /**
24 * @author chrisl
25 *
26 * To change this generated comment edit the template variable "typecomment":
27 * Window>Preferences>Java>Templates.
28 * To enable and disable the creation of type comments go to
29 * Window>Preferences>Java>Code Generation.
30 */
31 public class Anneal_Test02 extends TestCase {
32
33 ////////////////////////////////////////////////////////////////////////
34
35 private static final String NAME = "AnnealTest_02";
36 private static final boolean DEBUG = false;
37 private static boolean VERBOSE = false;
38 private static boolean CHECK = true;
39
40 private static boolean fSAVE = false;
41
42 ////////////////////////////////////////////////////////////////////////
43
44 static private String fTestFilename;
45 private IGraph fGraph;
46 private VirtualGraph fVGraph;
47
48 ////////////////////////////////////////////////////////////////////////
49
50 public Anneal_Test02(String name) {
51 super(name);
52 }
53
54 ////////////////////////////////////////////////////////////////////////
55
56 public void testAnneal_02() {
57 fGraph = TestUtil.createGraph(new File(fTestFilename));
58 fVGraph = new VirtualGraph(fGraph);
59 MinCross.dot(fVGraph, 0, 6, 0);
60 fVGraph.removeAux();
61 //MinCross.dot(fVGraph, 4, 6, 0);
62 Position.dotPosition(fVGraph);
63 if (fSAVE) {
64 // Save graph layout.
65 Position.saveResult(fVGraph);
66 TestUtil.updateShape(fGraph);
67 Route.dot(fVGraph);
68 msg.println(fGraph.sprintGraph());
69 TestUtil.saveImage("out/test/testAnneal_02", 1f, fGraph);
70 }
71 Anneal anneal = new Anneal(fVGraph, 1);
72 if (VERBOSE)
73 fVGraph.debugPrintRanks();
74 //
75 checkRouteBus(anneal, fVGraph);
76 checkRoutePTP(anneal, fVGraph);
77 checkMoveVertex(anneal, fVGraph);
78 checkRestorePath(anneal, fVGraph);
79 }
80
81 ////////////////////////////////////////////////////////////////////////
82
83 public void checkRouteBus(Anneal anneal, VirtualGraph vgraph) {
84 final String PREFIX = NAME + ".checkRouteBus()";
85 if (VERBOSE)
86 msg.println("### " + PREFIX);
87 anneal.clear();
88 GridFactory factory = anneal.getGridFactory();
89 //
90 // Stub chain routing. Banking->Economics#xx
91 //
92 VirtualGraph.Rank rank, rank1;
93 VirtualVertex src, dest, v;
94 VirtualEdge e;
95 VirtualChain chain;
96 //
97 int espacing = vgraph.fESpacing;
98 //
99 src = vgraph.getVertex("Banking");
100 List chains = new ArrayList();
101 for (int i = 0; i < src.outs.length; ++i) {
102 e = src.outs[i];
103 chain = new VirtualChain(e);
104 chains.add(chain);
105 }
106 if (CHECK)
107 Assert.assertTrue(
108 "Expected 1 output chain from Banking: actual=" + chains.size(),
109 chains.size() == 1);
110 chain = (VirtualChain) chains.get(0);
111 float oldcost = Grid.pathCost(chain);
112 if (VERBOSE) {
113 msg.println("oldcost=" + oldcost + "\n" + chain.toDump());
114 msg.println(PREFIX + "r=17, spaces=", factory.getSpaceTable()[17]);
115 }
116 scrambleChain(chain, vgraph, factory);
117 // Need to update SpaceTable aftering moving the vertices.
118 factory.initSpaceTable();
119 factory.sanityCheck();
120 float newcost = Grid.pathCost(chain);
121 if (VERBOSE) {
122 msg.println("oldcost=" + oldcost + ", newcost=" + newcost + "\n" + chain.toDump());
123 msg.println(PREFIX + "r=17, spaces=", factory.getSpaceTable()[17]);
124 }
125 Assert.assertTrue(
126 "Unable for distort path for routing: oldcost="
127 + oldcost
128 + ", newcost="
129 + newcost
130 + ", chain="
131 + chain.toDump(),
132 newcost > oldcost);
133 boolean ret = anneal.route(chain, true, PREFIX);
134 if (VERBOSE) {
135 msg.println(PREFIX + "r=17, spaces=", factory.getSpaceTable()[17]);
136 }
137 newcost = Grid.pathCost(chain);
138 vgraph.sanityCheck();
139 factory.sanityCheck();
140 if (CHECK) {
141 Assert.assertTrue("Expected route successful and newcost=4: actual=" + newcost, newcost == 4);
142 }
143 //
144 // A long route from a vertex up to a bus.
145 // Mobile Warfare->Tactics.outbus.
146 //
147 chains.clear();
148 src = vgraph.getVertex("Mobile Warfare");
149 for (int i = 0; i < src.ins.length; ++i) {
150 e = src.ins[i];
151 chain = new VirtualChain(e);
152 if (chain.fTail.isBus()) {
153 chains.add(chain);
154 }
155 }
156 if (CHECK) {
157 Assert.assertTrue(
158 "Expected only one bus->Mobile Warfare edge: actual=" + chains.size(),
159 chains.size() == 1);
160 }
161 chain = (VirtualChain) chains.get(0);
162 if (VERBOSE)
163 msg.println("oldcost=" + oldcost + "\n" + chain.toDump());
164 oldcost = Grid.pathCost(chain);
165 scrambleChain(chain, vgraph, factory);
166 // Need to update SpaceTable aftering moving the vertices.
167 factory.initSpaceTable();
168 factory.sanityCheck();
169 newcost = Grid.pathCost(chain);
170 if (VERBOSE) {
171 msg.println("Scramble: oldcost=" + oldcost + ", newcost=" + newcost + "\n" + chain.toDump());
172 }
173 if (CHECK)
174 Assert.assertTrue(
175 "Expected newcost>oldcost: oldcost=" + oldcost + ", newcost=" + newcost,
176 newcost > oldcost);
177 ret = anneal.route(chain, false, PREFIX);
178 vgraph.sanityCheck();
179 factory.sanityCheck();
180 oldcost = newcost;
181 newcost = Grid.pathCost(chain);
182 if (VERBOSE)
183 msg.println("# oldcost=" + oldcost + ", newcost=" + newcost);
184 if (CHECK) {
185 Assert.assertTrue(
186 "Expected route successful and cost less: oldcost=" + oldcost + ", newcost=" + newcost,
187 newcost < oldcost);
188 }
189 }
190
191 public void checkRoutePTP(Anneal anneal, VirtualGraph vgraph) {
192 final String PREFIX = NAME + ".checkRoutePTP()";
193 if (VERBOSE)
194 msg.println("### " + PREFIX);
195 anneal.clear();
196 GridFactory factory = anneal.getGridFactory();
197 //
198 // Mathematics->University. Expected to cross some edges.
199 //
200 VirtualGraph.Rank rank, rank1;
201 VirtualVertex src, dest, v;
202 VirtualEdge e;
203 VirtualChain chain;
204 //
205 int espacing = vgraph.fESpacing;
206 //
207 src = vgraph.getVertex("Mathematics");
208 List chains = new ArrayList();
209 for (int i = 0; i < src.outs.length; ++i) {
210 e = src.outs[i];
211 chain = new VirtualChain(e);
212 if (chain.fHead.getName().equals("University")) {
213 chains.add(chain);
214 }
215 }
216 if (CHECK)
217 Assert.assertTrue(
218 "Expected to find single edge Mathematics->University: actual=" + chains.size(),
219 chains.size() == 1);
220 chain = (VirtualChain) chains.get(0);
221 float oldcost = Grid.pathCost(chain);
222 if (VERBOSE) {
223 msg.println("oldcost=" + oldcost + "\n" + chain.toDump());
224 }
225 scrambleChain(chain, vgraph, factory);
226 // Need to update SpaceTable aftering moving the vertices.
227 factory.initSpaceTable();
228 factory.sanityCheck();
229 float newcost = Grid.pathCost(chain);
230 if (VERBOSE) {
231 msg.println("oldcost=" + oldcost + ", newcost=" + newcost + "\n" + chain.toDump());
232 }
233 Assert.assertTrue(
234 "Unable for distort path for routing: oldcost="
235 + oldcost
236 + ", newcost="
237 + newcost
238 + ", chain="
239 + chain.toDump(),
240 newcost > oldcost);
241 boolean ret = anneal.route(chain, true, PREFIX);
242 vgraph.sanityCheck();
243 factory.sanityCheck();
244 newcost = Grid.pathCost(chain);
245 if (VERBOSE)
246 msg.println("# oldcost=" + oldcost + ", newcost=" + newcost);
247 if (CHECK) {
248 Assert.assertTrue(
249 "Expected route successful and cost less: oldcost=" + oldcost + ", newcost=" + newcost,
250 newcost < oldcost);
251 }
252 }
253
254 /**
255 * Check GridFactory.moveVertex().
256 */
257 public void checkMoveVertex(Anneal anneal, VirtualGraph vgraph) {
258 final String PREFIX = NAME + ".checkMoveVertex()";
259 GridFactory factory = anneal.getGridFactory();
260 int r = 10;
261 int[] spaces = factory.getSpaceTable()[r];
262 if (VERBOSE)
263 msg.println("r=" + r + ", spaces=", spaces);
264 factory.sanityCheck();
265 VirtualGraph.Rank rank = vgraph.ranks[r];
266 int from = rank.nVts / 4;
267 int to = rank.nVts * 3 / 4;
268 rank.moveVertex(from, to);
269 factory.moveVertex(rank.vts[from], from, to);
270 boolean ok = factory.sanityCheck();
271 if (CHECK)
272 Assert.assertTrue(PREFIX + ": GridFactory.sanityCheck() FAILED: #1", ok);
273 rank.moveVertex(to, from);
274 factory.moveVertex(rank.vts[from], to, from);
275 ok = factory.sanityCheck();
276 if (CHECK)
277 Assert.assertTrue(PREFIX + ": GridFactory.sanityCheck() FAILED: #2", ok);
278 // Restore corrupted space table.
279 factory.initSpaceTable();
280 }
281
282 /**
283 * Check ErasedPath.restore() by removing and restoring arbitrary edges.
284 */
285 public void checkRestorePath(Anneal anneal, VirtualGraph vgraph) {
286 final String PREFIX = NAME + ".checkRestorePath()";
287 final int ITER = 50;
288 int index;
289 List chainlist = vgraph.getChainList();
290 ErasedPath erased = new ErasedPath(vgraph);
291 boolean down = true;
292 for (int iter = 0; iter < ITER; ++iter) {
293 index = (int) (Math.random() * chainlist.size());
294 float oldcost = erased.erase((VirtualChain) chainlist.get(index), down);
295 if (VERBOSE)
296 msg.println(PREFIX + ": oldcost=" + oldcost + ", erased=" + erased.toString());
297 if(oldcost==0) continue;
298 erased.restore();
299 down=!down;
300 }
301 boolean ok = vgraph.checkCrossCosts();
302 if (CHECK)
303 Assert.assertTrue(PREFIX + ": VirtualGraph.checkCrossCost() FAILED: #1", ok);
304 // Make sure cross costs not corrupted.
305 vgraph.staticCost();
306 }
307
308 ////////////////////////////////////////////////////////////////////////
309
310 /**
311 * Move chain vertices around to make sure it would be rerouted.
312 */
313 private void scrambleChain(VirtualChain chain, VirtualGraph vgraph, GridFactory factory) {
314 VirtualGraph.Rank rank;
315 int espacing = vgraph.getESpacing();
316 int dir = -1;
317 VirtualVertex v, vv;
318 int x;
319 for (VirtualEdge e = chain.fChainTail; e.next != null; e = e.next, dir *= -1) {
320 v = e.head;
321 rank = vgraph.ranks[v.rank];
322 if (dir < 0 && v.order > 0) {
323 vv = rank.vts[v.order - 1];
324 x = factory.rightBorder(vv) + v.leftWidth;
325 if (x < v.x) {
326 v.x = x;
327 continue;
328 }
329 }
330 if (v.order < rank.nVts - 1) {
331 vv = rank.vts[v.order + 1];
332 x = factory.leftBorder(vv) - v.rightWidth;
333 if (x > v.x)
334 v.x = x;
335 }
336 }
337 }
338
339 // Main ////////////////////////////////////////////////////////////////
340 //
341
342 public static void main(String[] args) {
343 Map opts = new HashMap();
344 args = msg.getArgs(opts, NAME, args, "- verbose=v nocheck=c save=s");
345 if (args.length == 0)
346 usage();
347 fTestFilename = args[0];
348 if (opts.get("verbose") != null) {
349 Debug.enable("verbose");
350 VERBOSE = true;
351 }
352 if (opts.get("nocheck") != null) {
353 CHECK = false;
354 }
355 if (opts.get("save") != null) {
356 fSAVE = true;
357 }
358 junit.textui.TestRunner.run(new TestSuite(Anneal_Test02.class));
359 // junit.swingui.TestRunner.run(new TestVirtualGraph("TestVirtualGraph").getClass());
360 }
361
362 private static void usage() {
363 msg.print("Usage: " + NAME + " <dotfile>");
364 System.exit(100);
365 }
366
367 ////////////////////////////////////////////////////////////////////////
368
369 }