Source code: com/port80/graph/dot/impl/GridFactory_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.TestCase;
14 import junit.framework.TestSuite;
15
16 import com.port80.graph.IGraph;
17 import com.port80.graph.dot.impl.GridFactory.GridIterator;
18 import com.port80.util.Debug;
19 import com.port80.util.msg;
20 import com.port80.util.struct.IntKeyHashMap;
21 import com.port80.util.struct.IntList;
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 GridFactory_Test01 extends TestCase {
32
33 ////////////////////////////////////////////////////////////////////////
34
35 private static final String NAME = "GridFactoryTest_01";
36 private static final boolean DEBUG = false;
37
38 private static boolean CHECK = true;
39 private static boolean VERBOSE = Debug.isVerbose();
40
41 private static Map opts = new HashMap();
42
43 ////////////////////////////////////////////////////////////////////////
44
45 IGraph fGraph;
46 VirtualGraph fVGraph;
47 Anneal fAnneal;
48
49 ////////////////////////////////////////////////////////////////////////
50
51 public GridFactory_Test01(String name) {
52 super(name);
53 if (VERBOSE)
54 msg.println("### " + name);
55 // The simplest 2-4-2 fully connected graph.
56 String testGraph =
57 "digraph testRankCost01"
58 + "{"
59 + "01->11; 01->12; 01->13; 01->14; "
60 + "02->11; 02->12; 02->13; 02->14; "
61 + "11->21; 12->21; 13->21; 14->21; "
62 + "11->22; 12->22; 13->22; 14->22; "
63 + "11->31; 22->31; "
64 + "}";
65 fGraph = TestUtil.createGraph(testGraph);
66 fVGraph = new VirtualGraph(fGraph);
67 MinCross.dot(fVGraph, 0, 6, 0);
68 fVGraph.removeAux();
69 Position.dotPosition(fVGraph);
70 if (DEBUG) {
71 // Save graph layout.
72 Position.saveResult(fVGraph);
73 TestUtil.updateShape(fGraph);
74 Route.dot(fVGraph);
75 msg.println(fGraph.sprintGraph());
76 TestUtil.saveImage("out/test/testAnneal_01", 1f, fGraph);
77 }
78 fAnneal = new Anneal(fVGraph, 1);
79 //
80 fVGraph.sanityCheck();
81 }
82
83 ////////////////////////////////////////////////////////////////////////
84
85 /**
86 * Test GridFactory.GridIterator class.
87 */
88 public void testGridIterator() {
89 final String PREFIX = NAME + ".testGridIterator(): ";
90 if (VERBOSE)
91 msg.println("\n### " + PREFIX);
92 //
93 VirtualGraph vgraph = fVGraph;
94 Anneal anneal = fAnneal;
95 //
96 GridFactory factory = anneal.getGridFactory();
97 VirtualGraph.Rank rank, rank1;
98 VirtualVertex v;
99 int espacing = vgraph.getESpacing();
100 VirtualVertex v01 = vgraph.getVertex("01");
101 VirtualVertex v02 = vgraph.getVertex("02");
102 VirtualVertex v11 = vgraph.getVertex("11");
103 VirtualVertex v22 = vgraph.getVertex("22");
104 VirtualVertex v31 = vgraph.getVertex("31");
105 //
106 //
107 //
108 int[][] spacetable = factory.getSpaceTable();
109 for (int r = 0; r < spacetable.length; ++r) {
110 if (VERBOSE)
111 msg.println("r=" + r + ", spaces: ", spacetable[r]);
112 if (CHECK)
113 Assert.assertTrue(
114 PREFIX + "checkMonotonic() FAILED: ",
115 TestUtil.checkMonotonic(spacetable[r], "r=" + r));
116 }
117 //
118 // Check first Grid point.
119 //
120 if (VERBOSE)
121 msg.println("\n# First Grid points.");
122 factory.initGrid(v11, v01);
123 GridFactory.GridIterator it = factory.new GridIterator(0, 0, 0);
124 Grid grid = it.next();
125 if (VERBOSE)
126 msg.println("grid=" + grid);
127 if (CHECK)
128 Assert.assertTrue(PREFIX + "expected first grid!=null", grid != null);
129 it = factory.new GridIterator(0, factory.fMaxX + espacing, 0);
130 grid = it.next();
131 if (VERBOSE)
132 msg.println("grid=" + grid);
133 if (CHECK)
134 Assert.assertTrue(PREFIX + "expected out of bound grid==null", grid == null);
135 it = factory.new GridIterator(0, 0, Integer.MAX_VALUE);
136 grid = it.next();
137 if (CHECK) {
138 int expected = v11.x % espacing + espacing;
139 Assert.assertTrue(
140 PREFIX + "expected first grid.x=" + expected + ", actual=" + grid.x,
141 grid.x == expected);
142 }
143 //
144 // Grid points without erased vertex.
145 //
146 if (VERBOSE)
147 msg.println("\n# Grid points without erased vertex:");
148 int n = 0;
149 IntList xs = new IntList(10);
150 for (grid = it.next(); grid != null; grid = it.next()) {
151 xs.add(grid.x);
152 }
153 if (VERBOSE)
154 msg.println("r=0: grids=\n" + xs);
155 if (CHECK) {
156 int x = (v01.x + v02.x) / 2;
157 int index = xs.binarySearch(x);
158 if (VERBOSE)
159 msg.println("size=" + xs.size() + ", x=" + x + ", index=" + index);
160 Assert.assertTrue(
161 PREFIX + "expected grid at mid point between v01 and v02: x=" + x + ", index=" + index,
162 index > 0);
163 }
164 //
165 // Grids with erased vertex.
166 //
167 if (VERBOSE)
168 msg.println("\n# Grid points erased vertex:");
169 VirtualEdge e = v11.findOutChain(v31);
170 Assert.assertTrue(PREFIX + "e!=null", e != null);
171 ErasedPath erased = new ErasedPath(vgraph);
172 erased.erase(new VirtualChain(e), true);
173 factory.initGrid(v11, v31);
174 if (VERBOSE)
175 msg.println(PREFIX + erased);
176 //
177 // Check that no Grid inside the source vertex.
178 if (false) {
179 // GridFactory no longer init. for the src.rank.
180 xs.clear();
181 it = factory.new GridIterator(1, v11.x, v11.x * v11.x); // , v31);
182 for (grid = it.next(); grid != null; grid = it.next()) {
183 xs.add(grid.x);
184 }
185 if (VERBOSE)
186 msg.println("r=1, grids=\n" + xs);
187 if (CHECK) {
188 for (int i = v11.x - v11.leftWidth; i < v11.x + v11.rightWidth; ++i) {
189 Assert.assertTrue(
190 PREFIX + "expected no grid point inside source vertex: x=" + i,
191 xs.binarySearch(i) < 0);
192 }
193 }
194 }
195 //
196 // Check that Grid created inside erased vertex.
197 xs.clear();
198 it = factory.new GridIterator(2, v11.x, v11.x * v11.x); // , v31);
199 for (grid = it.next(); grid != null; grid = it.next()) {
200 xs.add(grid.x);
201 }
202 if (VERBOSE)
203 msg.println("r=2, grids=\n" + xs);
204 if (CHECK) {
205 // Should have Grid inside erased vertex.
206 rank = vgraph.ranks[2];
207 v = null;
208 for (int i = 0; i < rank.nVts; ++i) {
209 v = rank.vts[i];
210 if (v.isVirtual())
211 break;
212 }
213 boolean found = false;
214 for (int i = v.x - v.leftWidth; i <= v.x + v.rightWidth; ++i) {
215 if (xs.binarySearch(i) >= 0) {
216 found = true;
217 break;
218 }
219 }
220 Assert.assertTrue(
221 PREFIX + "expected to hit src.x: src.x=" + v11.x,
222 xs.binarySearch(v11.x) >= 0);
223 Assert.assertTrue(PREFIX + "expected grid in erased virtual vertex", found);
224 }
225 //
226 // Check that grid hit src and dest and vertex and leftVertex are set properly.
227 xs.clear();
228 List gridlist = new ArrayList(32);
229 it = factory.new GridIterator(2, v11.x, v11.x * v11.x); // , v31);
230 for (grid = it.next(); grid != null; grid = it.next()) {
231 xs.add(grid.x);
232 gridlist.add(grid);
233 }
234 if (VERBOSE) {
235 for (int i = 0; i < gridlist.size(); ++i) {
236 grid = (Grid) gridlist.get(i);
237 msg.println(grid.toString());
238 }
239 }
240 if (CHECK) {
241 // Should not hit any real vertex in rank 2.
242 boolean found = false;
243 v = null;
244 rank = vgraph.ranks[2];
245 for (int i = 0; i < rank.nVts; ++i) {
246 v = rank.vts[i];
247 if (v.isVirtual())
248 continue;
249 if (xs.binarySearch(v.x) >= 0) {
250 found = true;
251 break;
252 }
253 }
254 Assert.assertTrue(
255 PREFIX + "expected no hit on real vertex on rank 2: hit=" + v.getName(),
256 !found);
257 }
258 //
259 xs.clear();
260 IntKeyHashMap grids;
261 grids = new IntKeyHashMap(10);
262 it = factory.new GridIterator(3, v11.x, v11.x * v11.x); // , v31);
263 for (grid = it.next(); grid != null; grid = it.next()) {
264 xs.add(grid.x);
265 grids.put(grid.x, grid);
266 }
267 if (VERBOSE)
268 msg.println("r=3, grids=\n" + xs);
269 if (CHECK) {
270 // Should have Grid inside erased vertex.
271 boolean found = false;
272 for (int i = v31.x - v31.leftWidth; i < v31.x + v31.rightWidth; ++i) {
273 if (xs.binarySearch(i) >= 0) {
274 found = true;
275 break;
276 }
277 }
278 Assert.assertTrue(PREFIX + "expected grid in erased vertex not found", found);
279 // Shoud hit src.x,dest.x
280 Assert.assertTrue(
281 PREFIX + "expected to hit src.x: src.x=" + v11.x,
282 xs.binarySearch(v11.x) >= 0);
283 Assert.assertTrue(
284 PREFIX + "expected to hit dest.x: dest.x=" + v31.x,
285 xs.binarySearch(v31.x) >= 0);
286 }
287 // First Grid before first vertex.
288 {
289 grid = (Grid) grids.get(xs.get(0));
290 if (VERBOSE)
291 msg.println("x=" + xs.get(0) + ", grid=" + grid);
292 if (CHECK) {
293 Assert.assertTrue(
294 PREFIX + "expected first grid.vertex==null: actual=" + grid,
295 grid.vertex == null);
296 Assert.assertTrue(
297 PREFIX + "expected first grid.leftVertex==null: actual=" + grid,
298 grid.leftVertex == null);
299 }
300 }
301 // Grid on v31
302 {
303 grid = (Grid) grids.get(v31.x);
304 if (VERBOSE)
305 msg.println("x=" + v31.x + ", grid=" + grid);
306 if (CHECK) {
307 Assert.assertTrue(
308 PREFIX + "expected grid.vertex==v31: actual=" + grid,
309 grid.vertex == v31);
310 Assert.assertTrue(
311 PREFIX + "expected grid.leftVertex==v31: actual=" + grid,
312 grid.leftVertex == v31);
313 }
314 }
315 // Prev grid on left of v31.
316 {
317 int index = xs.binarySearch(v31.x);
318 int x = xs.get(index - 1);
319 grid = (Grid) grids.get(x);
320 if (VERBOSE)
321 msg.println("x=" + x + ", grid=" + grid);
322 if (CHECK) {
323 Assert.assertTrue(
324 PREFIX + "expected prev grid.vertex==null: actual=" + grid,
325 grid.vertex == null);
326 }
327 }
328 // Next grid on right of v31.
329 {
330 int index = xs.binarySearch(v31.x);
331 int x = xs.get(index + 1);
332 grid = (Grid) grids.get(x);
333 if (VERBOSE)
334 msg.println("x=" + x + ", grid=" + grid);
335 if (CHECK) {
336 Assert.assertTrue(
337 PREFIX + "expected next grid.vertex==null: actual=" + grid,
338 grid.vertex == null);
339 Assert.assertTrue(
340 PREFIX + "expected next grid.leftVertex==v31: actual=" + grid,
341 grid.leftVertex == v31);
342 }
343 }
344 // Last grid after last vertex (ie vertex '31' since it is the only vertex in the rank).
345 {
346 int x = xs.get(xs.size() - 1);
347 grid = (Grid) grids.get(x);
348 if (VERBOSE)
349 msg.println("x=" + x + ", grid=" + grid);
350 if (CHECK) {
351 Assert.assertTrue(
352 PREFIX + "expected last grid.vertex==null: actual=" + grid,
353 grid.vertex == null);
354 Assert.assertTrue(
355 PREFIX + "expected last grid.leftVertex==v31, actual=" + grid,
356 grid.leftVertex == v31);
357 }
358 }
359 //
360 // Check that src and dest coordinates are not skipped when they are close together.
361 //
362 {
363 xs.clear();
364 int v11x = v11.x;
365 v11.x = v31.x - 2;
366 factory.initGrid(v11, v31);
367 it = factory.new GridIterator(3, v31.x - 2, v31.x * v31.x); // , v31);
368 for (grid = it.next(); grid != null; grid = it.next()) {
369 xs.add(grid.x);
370 }
371 if (VERBOSE)
372 msg.println("r=3, grids=\n" + xs);
373 if (CHECK) {
374 // Shoud hit src.x,dest.x
375 Assert.assertTrue(
376 PREFIX + "expected to hit src.x: src.x=" + (v31.x - 2),
377 xs.binarySearch(v31.x - 2) >= 0);
378 Assert.assertTrue(
379 PREFIX + "expected to hit dest.x: dest.x=" + v31.x,
380 xs.binarySearch(v31.x) >= 0);
381 }
382 v11.x = v11x;
383 }
384 //
385 // Check that start is limited by given distance cost.
386 //
387 if (VERBOSE)
388 msg.println("\n# Distance limit:");
389 {
390 xs.clear();
391 factory.initGrid(v11, v31);
392 int distcost = 36 * 36 / vgraph.fCELL_DISTFACTOR;
393 it = factory.new GridIterator(3, v31.x, distcost); // , v31);
394 for (grid = it.next(); grid != null; grid = it.next()) {
395 xs.add(grid.x);
396 }
397 // The extra espacing is allowance for alignment.
398 int minx = v31.x - Grid.distCostToX(distcost);
399 if (VERBOSE)
400 msg.println("r=3, grids=\n" + xs + "\nminx=" + minx);
401 if (CHECK) {
402 // No grid before v31.x-2-espacing-Math.sqrt(cost)*fCELL_DISTFACTOR
403 Assert.assertTrue(PREFIX + "expected no grid.x>=" + minx, xs.get(0) >= minx);
404 }
405 //
406 xs.clear();
407 distcost = 38 * 38 / vgraph.fCELL_DISTFACTOR;
408 it = factory.new GridIterator(3, v31.x, distcost); // , v31);
409 for (grid = it.next(); grid != null; grid = it.next()) {
410 xs.add(grid.x);
411 }
412 // The extra espacing is allowance for alignment.
413 minx = v31.x - Grid.distCostToX(distcost);
414 if (VERBOSE)
415 msg.println("r=3, grids=\n" + xs + "\nminx=" + minx);
416 if (CHECK) {
417 // No grid before v31.x-2-espacing-Math.sqrt(cost)*fCELL_DISTFACTOR
418 Assert.assertTrue(PREFIX + "expected no grid.x>=" + minx, xs.get(0) >= minx);
419 }
420 }
421 //
422 erased.restore();
423
424 }
425
426 /**
427 * Check that GridFactory.ValidIterator align to the basic grid.
428 */
429 public void testGridAlign() {
430 final String PREFIX = NAME + ".testGridAlign(): ";
431 int[] spaces;
432 int[] forced;
433 GridFactory.ValidXIterator it;
434 IntList a;
435 // ValidXIterator(int[] spaces, int[] forced, int erasedindex, int srcx, int spacing) {
436 spaces = new int[] { 0, 10,20, 50,100, 120,135, 145,155, 200 };
437 forced = new int[] { 35 };
438 it = new GridFactory.ValidXIterator(spaces, forced, 1, 75, 10, 10);
439 a = new IntList();
440 for (int x = it.first(); x < spaces[spaces.length - 1]; x = it.next())
441 a.add(x);
442 if (VERBOSE)
443 msg.println(PREFIX + "#1:\n" + a);
444 if (CHECK) {
445 // Forced.
446 Assert.assertTrue("Expected grid at: 35 not found, grids=\n" + a, a.binarySearch(35) >= 0);
447 Assert.assertTrue("Expected grid at: 75 not found, grids=\n" + a, a.binarySearch(75) >= 0);
448 // fitBetween.
449 Assert.assertTrue("Expected grid at: 140 not found, grids=\n" + a, a.binarySearch(140) >= 0);
450 Assert.assertTrue("Expected grid at: 160 not found, grids=\n" + a, a.binarySearch(160) >= 0);
451 // Align.
452 Assert.assertTrue("Expected grid at: 165 not found, grids=\n" + a, a.binarySearch(165) >= 0);
453 }
454 //
455 spaces = new int[] { 0, 10,62, 100,105, 120,135, 145,154, 200 };
456 forced = new int[] { 35,82 };
457 it = new GridFactory.ValidXIterator(spaces, forced, -1, 76, 10, 10);
458 a = new IntList();
459 for (int x = it.first(); x < spaces[spaces.length - 1]; x = it.next())
460 a.add(x);
461 if (VERBOSE)
462 msg.println(PREFIX + "#2:\n" + a);
463 if (CHECK) {
464 // src.x
465 Assert.assertTrue("Expected grid at: 76 not found, grids=\n" + a, a.binarySearch(76) >= 0);
466 // dest.x
467 Assert.assertTrue("Expected grid at: 82 not found, grids=\n" + a, a.binarySearch(82) >= 0);
468 // align
469 Assert.assertTrue("Expected grid at: 86 not found, grids=\n" + a, a.binarySearch(86) >= 0);
470 // fitBetween
471 Assert.assertTrue("Expected grid at: 110 not found, grids=\n" + a, a.binarySearch(110) >= 0);
472 // fitBetween
473 Assert.assertTrue("Expected grid at: 115 not found, grids=\n" + a, a.binarySearch(115) >= 0);
474 }
475 //
476 spaces = new int[] { 0, 10,62, 101,105, 125,135, 145,154, 200 };
477 forced = new int[] { 35,82 };
478 it = new GridFactory.ValidXIterator(spaces, forced, -1, 76, 10, 10);
479 a = new IntList();
480 for (int x = it.first(); x < spaces[spaces.length - 1]; x = it.next())
481 a.add(x);
482 if (VERBOSE)
483 msg.println(PREFIX + "#3:\n" + a);
484 if (CHECK) {
485 // align
486 Assert.assertTrue("Expected grid at: 96 not found, grids=\n" + a, a.binarySearch(96) >= 0);
487 Assert.assertTrue("Expected grid at: 116 not found, grids=\n" + a, a.binarySearch(116) >= 0);
488 }
489 //
490 spaces = new int[] { 0, 80, 100, 120, 135, 146, 166, 250 };
491 forced = new int[] { 36,38 };
492 it = new GridFactory.ValidXIterator(spaces, forced, -1, 75, 20, 10);
493 a = new IntList();
494 for (int x = it.first(); x < spaces[spaces.length - 1]; x = it.next())
495 a.add(x);
496 if (VERBOSE)
497 msg.println(PREFIX + "#4:\n" + a);
498 if (CHECK) {
499 // forced
500 Assert.assertTrue("Expected grid at: 35 not found, grids=\n" + a, a.binarySearch(35) >= 0);
501 Assert.assertTrue("Expected grid at: 36 not found, grids=\n" + a, a.binarySearch(36) >= 0);
502 Assert.assertTrue("Expected grid at: 38 not found, grids=\n" + a, a.binarySearch(38) >= 0);
503 Assert.assertTrue("Expected grid at: 45 not found, grids=\n" + a, a.binarySearch(45) >= 0);
504 // fitBetween
505 Assert.assertTrue("Expected grid at: 70 not found, grids=\n" + a, a.binarySearch(70) >= 0);
506 }
507 }
508
509 ////////////////////////////////////////////////////////////////////////
510
511 public static void main(String[] args) {
512 args = msg.getArgs(opts, "GridFactoryTest_01", args, "- verbose=v nocheck=c");
513 if (opts.get("verbose") != null) {
514 Debug.enable("verbose");
515 VERBOSE = true;
516 }
517 if (opts.get("nocheck") != null) {
518 CHECK = false;
519 }
520 junit.textui.TestRunner.run(new TestSuite(GridFactory_Test01.class));
521 }
522
523 ////////////////////////////////////////////////////////////////////////
524 }