Source code: com/port80/graph/dot/impl/ErasedPath.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.Arrays;
9 import java.util.List;
10
11 import com.port80.util.Debug;
12 import com.port80.util.msg;
13
14 /**
15 * Data structure to hold information about the erased path.
16 * @author chrisl
17 */
18 public class ErasedPath {
19
20 ////////////////////////////////////////////////////////////////////////
21
22 private static final String NAME = "ErasedPath";
23 private static final boolean DEBUG = false;
24 private static final boolean CHECK = true;
25 private static boolean VERBOSE = Debug.isVerbose();
26
27 /** Max path cost slack allowed for route to be considered done.*/
28 private final int MAXSLACK = 0;
29
30 ////////////////////////////////////////////////////////////////////////
31
32 VirtualGraph fGraph;
33 VirtualGraph.Rank[] fRanks;
34 int fMinRank, fMaxRank;
35
36 VirtualChain fChain;
37 /**
38 * Erased VirtualVertex including the source and destination in chain vertex order.
39 * The src vertex not erased is replaced by null. Destination vertex is always erased.
40 */
41 List vertices;
42 /** Erased VirtualEdges indexed by rank. */
43 VirtualEdge[] edges;
44 VirtualVertex src;
45 VirtualVertex dest;
46 int topRank;
47 int bottomRank;
48 boolean isDown;
49 float oldCost;
50
51 private int fCELL_XDIV;
52 private int fCELL_BASICFACTOR;
53 private int fCELL_TURNFACTOR;
54 private int fCELL_DISTFACTOR;
55 private float fFAST_DISTCOST;
56
57 ErasedPath(VirtualGraph graph) {
58 fGraph = graph;
59
60 fMinRank = graph.minRank;
61 fMaxRank = graph.maxRank;
62 fRanks = graph.ranks;
63
64 fCELL_XDIV = fGraph.fCELL_XDIV;
65 fCELL_BASICFACTOR = fGraph.fCELL_BASICFACTOR;
66 fCELL_TURNFACTOR = fGraph.fCELL_TURNFACTOR;
67 fCELL_DISTFACTOR = fGraph.fCELL_DISTFACTOR;
68 fFAST_DISTCOST = Grid.distCostOf(graph.getVertexSpacing());
69 vertices = new ArrayList();
70 edges = new VirtualEdge[fMaxRank];
71 }
72
73 /** @return Number of vertices in the erased path (including the src vertex that is not erased. */
74 int size() {
75 return vertices.size();
76 }
77
78 /** @return Edge for the path chain at the given rank. */
79 VirtualEdge edge(int r) {
80 return edges[r];
81 }
82
83 /** @return The ith vertex in the erased path. 0=topmost vertex (smallest vertex.rank). */
84 VirtualVertex get(int i) {
85 return (VirtualVertex) vertices.get(i);
86 }
87
88 void clear() {
89 vertices.clear();
90 Arrays.fill(edges, null);
91 oldCost = 0;
92 }
93
94 boolean isBusRoute() {
95 return dest.isBus();
96 }
97
98 boolean isDown() {
99 return isDown;
100 }
101
102 /** Cost limit for fast run. A minimal cost limit forbide AStar to search too far. */
103 float fastCost() {
104 return (bottomRank - topRank) * fCELL_BASICFACTOR
105 + fCELL_TURNFACTOR
106 + fFAST_DISTCOST
107 + 1;
108 }
109
110 /**
111 * Erase route for given edge chain to prepare for reroute.
112 * All cells on the route are marked as SPACE except the src cell.
113 *
114 * . Update cross cost in all ranks affected.
115 * . Mark vertices on the path as SPACE.
116 *
117 * Note that removing an edge currently have no cross cost still
118 * affect cross cost of imaginary edges which have counted this
119 * edge.
120 *
121 * @return The cost of the old path.
122 * @param chain The VirtualChain to be erased.
123 * @param isdown True for routing downward.
124 */
125 float erase(VirtualChain chain, boolean isdown) {
126 clear();
127 fChain = chain;
128 isDown = isdown;
129 //
130 Grid grid;
131 VirtualEdge e = chain.fChainTail;
132 VirtualVertex head = null;
133 VirtualVertex tail = e.tail;
134 vertices.add(tail);
135 for (; e != null; e = e.next) {
136 tail = e.tail;
137 head = e.head;
138 vertices.add(head);
139 edges[tail.rank] = e;
140 }
141 src = isdown ? chain.fTail : chain.fHead;
142 dest = isdown ? chain.fHead : chain.fTail;
143 topRank = isdown ? src.rank : dest.rank;
144 bottomRank = isdown ? dest.rank : src.rank;
145 //
146 // Mark src vertex, which is not erased, as null.
147 // dest vertex is always erased.
148 //
149 vertices.set((isdown ? 0 : (vertices.size() - 1)), null);
150 //
151 oldCost = Grid.pathCost(chain);
152 // Calc. min cost from src to dest.
153 float mincost = (vertices.size() - 1) * fCELL_BASICFACTOR + MAXSLACK;
154 if (oldCost == 0 || oldCost <= mincost) {
155 // // Since vertex orders are not changed, no need to restore cost for tail.rank-1.
156 // for (e = chain.fChainTail; e != null; e = e.next) {
157 // fRanks[e.tail.rank].restoreRankCost();
158 // }
159 if (VERBOSE)
160 msg.println(NAME + ".erase(): old cost is minimal=" + oldCost);
161 return 0;
162 }
163 //
164 // Calc. rank costs.
165 //
166 if (!isdown && chain.fTail.rank > fMinRank)
167 fRanks[chain.fTail.rank - 1].saveCrossCost();
168 for (e = chain.fChainTail; e != null; e = e.next) {
169 fRanks[e.tail.rank].saveCrossCost();
170 fGraph.rankCostRemoveEdge(e);
171 }
172 //
173 // Erase old path.
174 //
175 VirtualVertex v;
176 for (int i = 0, max = vertices.size(); i < max; ++i) {
177 v = (VirtualVertex) vertices.get(i);
178 if (v == null)
179 continue;
180 v.erase();
181 }
182 //
183 // Pre-calculate the grid point x-coordinates.
184 //
185 if (DEBUG)
186 msg.println(toString());
187 return oldCost;
188 }
189
190 void restore() {
191 Grid grid;
192 VirtualVertex v;
193 for (int i = 0; i < vertices.size(); ++i) {
194 v = (VirtualVertex) vertices.get(i);
195 if (v != null)
196 v.restore();
197 }
198 //Since vertex orders are not changed, no need to restore tail.rank-1.
199 for (VirtualEdge e = fChain.fChainTail; e != null; e = e.next)
200 fRanks[e.tail.rank].restoreCrossCost();
201 }
202
203 public String toString() {
204 StringBuffer buf =
205 new StringBuffer(
206 "ErasedPath: top rank="
207 + topRank
208 + ", bottom rank="
209 + bottomRank
210 + ", cost="
211 + oldCost);
212 buf.append("\n\tsrc=" + src.getName() + " (order=" + src.order + ", x=" + src.x + ")");
213 buf.append("\n\tdest=" + dest.getName() + " (order=" + dest.order + ", x=" + dest.x + ")");
214 VirtualVertex v;
215 for (int i = 0; i < vertices.size(); ++i) {
216 v = (VirtualVertex) vertices.get(i);
217 buf.append(
218 "\n\t"
219 + ((v == null)
220 ? "null"
221 : v.getName() + " (order=" + v.order + ", x=" + v.x + ")"));
222 }
223 return (buf.toString());
224 }
225
226 ////////////////////////////////////////////////////////////////////////
227
228 }