Source code: com/port80/graph/dot/impl/Grid.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import com.port80.util.msg;
8
9 /**
10 * Dynamic grid point for Anneal (equivalent to Cell for AnnealWithCell).
11 *
12 * @author chrisl
13 */
14 public class Grid {
15
16 ////////////////////////////////////////////////////////////////////////
17
18 private static final String NAME = "Grid";
19 private static final boolean DEBUG = false;
20 private static final boolean CHECK = true;
21
22 public static final int SPACE = 0;
23 public static final int ERASED = 1;
24
25 public static final int REJECT = 0;
26 public static final int QUEUE = 1;
27 public static final int REQUEUE = 2;
28
29 ////////////////////////////////////////////////////////////////////////
30
31 private static int fCELL_BASICFACTOR;
32 private static int fCELL_DISTFACTOR;
33 private static int fCELL_TURNFACTOR;
34 private static int fMARKCOUNTER;
35 private static int fXSPACING;
36
37 ////////////////////////////////////////////////////////////////////////
38
39 /** X-coordinates. */
40 int x;
41 /** Rank number. */
42 int rank;
43 VirtualVertex vertex;
44 VirtualVertex leftVertex;
45
46 // Temporary value validated by mark==fMARKCOUNTER.
47 int mark;
48 int heapIndex;
49 float fEstimate;
50 float curCost;
51 float estTotal;
52 Grid parent;
53
54 ////////////////////////////////////////////////////////////////////////
55
56 public static void configure(VirtualGraph graph) {
57 fCELL_BASICFACTOR = graph.fCELL_BASICFACTOR;
58 fCELL_DISTFACTOR = graph.fCELL_DISTFACTOR;
59 fCELL_TURNFACTOR = graph.fCELL_TURNFACTOR;
60 fXSPACING = graph.getVertexSpacing();
61 fMARKCOUNTER = 0;
62 }
63
64 public static void resetMarks() {
65 ++fMARKCOUNTER;
66 }
67
68 ////////////////////////////////////////////////////////////////////////
69
70 /**
71 * Travel cost to 'child' from 'parent' and 'grandparent'.
72 */
73 public static float travelCostTo(VirtualVertex child, VirtualVertex parent, VirtualVertex grandparent) {
74 if (CHECK)
75 if (Math.abs(parent.rank - child.rank) != 1)
76 msg.err(
77 NAME
78 + ".travelCostTo(): parent and child is more than 1 rank apart: parent.rank="
79 + parent.rank
80 + ", child.rank="
81 + child.rank
82 + "\n\tparent="
83 + parent.getName()
84 + "\n\tchild="
85 + child.getName());
86 float cost = fCELL_BASICFACTOR;
87 cost += ((float)((parent.x - child.x) * (parent.x - child.x))) / fCELL_DISTFACTOR;
88 if (grandparent != null)
89 if(Math.abs((grandparent.x - parent.x) - (parent.x - child.x))>=1)
90 cost += fCELL_TURNFACTOR;
91 return cost;
92 }
93
94 /**
95 * Find distance cost for the given different in x-coordinate.
96 * @param dx The x-coordindate difference.
97 */
98 public static float distCostOf(int dx) {
99 return ((float)(dx*dx)) / fCELL_DISTFACTOR;
100 }
101
102 /**
103 * Find distance that would incur the given distance cost.
104 */
105 public static int distCostToX(float distcost) {
106 return (int) (Math.sqrt(distcost * fCELL_DISTFACTOR));
107 }
108
109 /** Determine cost of the given path.
110 * @param path The cell path from tail(lower rank) to head.
111 */
112 static float pathCost(VirtualChain chain) {
113 float crosscost, travelcost;
114 float cost = 0;
115 VirtualVertex grandparent = null;
116 VirtualEdge e = chain.fChainTail;
117 VirtualVertex tail = e.tail;
118 VirtualVertex head;
119 if (DEBUG)
120 msg.println(
121 NAME + ".pathCost(): rank=" + tail.rank + ", cost=" + cost + ", v=" + tail.getName());
122 for (; e != null; e = e.next) {
123 head = e.head;
124 crosscost = tail.crossCost[head.order] * e.xPenalty;
125 cost += crosscost;
126 travelcost = travelCostTo(head, tail, grandparent);
127 cost += travelcost;
128 grandparent = tail;
129 tail = head;
130 if (DEBUG)
131 msg.println(
132 NAME
133 + ".pathCost(): rank="
134 + tail.rank
135 + ", cost="
136 + cost
137 + ", cross="
138 + crosscost
139 + ", travel="
140 + travelcost
141 + ", v="
142 + tail.getName());
143 }
144 return cost;
145 }
146
147 // Static constructors /////////////////////////////////////////////////
148 //
149
150 public static Grid newVertexGrid(VirtualVertex v) {
151 return new Grid(v);
152 }
153
154 public static Grid newSpaceGrid(int rank, int x, float cost, float est) {
155 return new Grid(rank, x, cost, est);
156 }
157
158 ////////////////////////////////////////////////////////////////////////
159
160 Grid() {}
161
162 Grid(float est) {
163 estTotal = est;
164 }
165
166 private Grid(VirtualVertex v) {
167 rank = v.rank;
168 x = v.x;
169 vertex = v;
170 leftVertex = v;
171 }
172
173 private Grid(int r, int x, float cost, float est) {
174 rank = r;
175 this.x = x;
176 curCost = cost;
177 estTotal = est;
178 }
179
180 ////////////////////////////////////////////////////////////////////////
181
182 /** Reset all temporary fields controlled by mark. */
183 public void init() {
184 mark = 0;
185 }
186
187 public boolean reached(VirtualVertex dest) {
188 if (dest.isBus()) {
189 return rank == dest.rank;
190 }
191 return vertex == dest;
192 }
193
194 /**
195 * Check if visit from parent would result in a better path.
196 */
197 public int accept(Grid parent, VirtualVertex dest, float cost) {
198 if (mark == fMARKCOUNTER) {
199 // Visited before.
200 if (cost < curCost) {
201 // The new visit have lower cost, requeue it.
202 curCost = cost;
203 estTotal = cost + fEstimate;
204 this.parent = parent;
205 return (heapIndex==0)? QUEUE: REQUEUE;
206 }
207 } else {
208 mark = fMARKCOUNTER;
209 heapIndex = 0;
210 curCost = cost;
211 estTotal = cost + estimate(dest);
212 this.parent = parent;
213 return QUEUE;
214 }
215 return REJECT;
216 }
217
218 public void setVertex(VirtualVertex v) {
219 vertex = v;
220 }
221
222 public void setLeftVertex(VirtualVertex v) {
223 leftVertex = v;
224 }
225
226 public float travelCostFrom(Grid parent, Grid grandparent) {
227 if (CHECK)
228 if (Math.abs(parent.rank - rank) != 1)
229 msg.err(
230 NAME
231 + ".travelCostTo(): parent and child is more than 1 rank apart: parent.rank="
232 + parent.rank
233 + ", rank="
234 + rank
235 + "\n\tparent="
236 + parent
237 + "\n\tthis="
238 + this);
239 float cost = fCELL_BASICFACTOR;
240 cost += ((float)((parent.x - x) * (parent.x - x))) / fCELL_DISTFACTOR;
241 if (grandparent != null) {
242 if (Math.abs((grandparent.x - parent.x) - (parent.x - x))>=1)
243 cost += fCELL_TURNFACTOR;
244 // } else if (parent.x - x != 0) {
245 // cost += fCELL_TURNFACTOR;
246 }
247 return cost;
248 }
249
250 /**
251 * Optimistic estimate cost from this Grid to the given destination.
252 * The estimate cost is static, so it is only calculated once when the Grid is first accepted.
253 */
254 public float estimate(VirtualVertex dest) {
255 int dy = Math.abs(rank - dest.rank);
256 fEstimate = dy * fCELL_BASICFACTOR;
257 if (dest.isReal()) {
258 float dx =this.x - dest.x;
259 // Minimium distance cost would be straight line to distance.
260 if(dy<=0) dy=1;
261 fEstimate += (dx * dx) / (dy*fCELL_DISTFACTOR);
262 }
263 return fEstimate;
264 }
265
266 ////////////////////////////////////////////////////////////////////////
267
268 /**
269 * Find the item closer to the destination, ie. estTotal is less or curCost is larger if estTotal is same.
270 * @return 1 if closer, 0 if same else -1.
271 */
272 public int lowerCostThan(Grid a) {
273 if (estTotal < a.estTotal)
274 return 1;
275 if (estTotal > a.estTotal)
276 return -1;
277 if (curCost > a.curCost)
278 return 1;
279 if (curCost < a.curCost)
280 return -1;
281 return 0;
282 }
283
284 public void toGeneralPath(StringBuffer buf, String color) {}
285
286 public String toString() {
287 StringBuffer buf = new StringBuffer();
288 if (vertex == null)
289 buf.append("SPACE (r=");
290 else
291 buf.append(vertex.getName() + " (r=");
292 buf.append(rank + ",x=" + x + ",left=");
293 if (leftVertex != null)
294 buf.append(leftVertex.getName() + ")");
295 else
296 buf.append("null)");
297 return buf.toString();
298 }
299
300 ////////////////////////////////////////////////////////////////////////
301
302 }