Source code: com/port80/graph/dot/impl/DotPath.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 import com.port80.util.sprint;
9
10 /** Data structure for routing information.
11 *
12 * . Boxes in the path are not pre-allocated and are added by
13 * reference.
14 */
15 public class DotPath extends DotBoxList {
16
17 ////////////////////////////////////////////////////////////////////////
18
19 private static final String NAME = "DotPath";
20 private static final int DEFAULT_CAPACITY = 100;
21
22 ////////////////////////////////////////////////////////////////////////
23
24 private VirtualEdge fOriginal;
25 VirtualPort fStart, fEnd;
26
27 ////////////////////////////////////////////////////////////////////////
28
29 public DotPath() {
30 this(DEFAULT_CAPACITY);
31 }
32 public DotPath(int n) {
33 super(n);
34 fStart = new VirtualPort();
35 fEnd = new VirtualPort();
36 }
37
38 ////////////////////////////////////////////////////////////////////////
39
40 public void reset() {
41 fSize = 0;
42 fOriginal = null;
43 fStart = new VirtualPort();
44 fEnd = new VirtualPort();
45 }
46
47 public VirtualEdge getOriginal() {
48 return fOriginal;
49 }
50
51 public void addInterRank(DotBox box) {
52 add(box);
53 }
54
55 /**
56 * Initialize tail end.
57 *
58 * @return the initialized Path 'ret'.
59 * @param e The first segment of the path.
60 * @param boxes Routing path boxes for the tail rank.
61 */
62 public DotPath beginPath(VirtualEdge e) {
63 reset();
64 fOriginal = e;
65 VirtualVertex v = e.tail;
66 fStart.x = v.x;
67 fStart.y = v.y;
68 if (e.tailPort != null) {
69 fStart.x += e.tailPort.dx;
70 fStart.y += e.tailPort.dy;
71 }
72 if (e.tail.isEdge()) {
73 fStart.theta = averageSlope(e.tail);
74 fStart.constrained = true;
75 } else if (e.tailPort != null && e.tailPort.constrained) {
76 fStart.theta = e.tailPort.theta;
77 fStart.constrained = true;
78 // } else if (e.tail.isReal()) {
79 // fStart.constrained = true;
80 // fStart.theta = Math.atan2((e.head.y - e.tail.y), e.head.x - e.tail.x);
81 } else {
82 fStart.constrained = false;
83 }
84 //
85 // fTailEnd.port.x = fStart.x;
86 // fTailEnd.port.y = fStart.y;
87 //
88 //FIXME: check that record_path returns a good path.
89 //FIXME: Apparently, fTailEnd.sidemask are reset in the swith
90 // statement below and render this call to pboxfn useless.
91 // Let vertex shape determine with side can be used by
92 // the given edge 'e' later.
93 //
94 //if(v.shape) pboxfn=n.shape.pboxfn;
95 //else pboxfn=null;
96 //if(pboxfn) fTailEnd.sidemask=(*pboxfn) (v, e, 1, &fTailEnd.boxes[0], &fTailEnd.nBox);
97 //else {
98 //fTailEnd.boxes[0] = fTailEnd.box;
99 //fTailEnd.nBox = 1;
100 //}
101 // This shrink the fTailEnd.boxes[0] to just a line at the
102 // side the edge should be routed. fTailEnd.box is still the
103 // maximal box.
104 // if (e.isSelf()) {
105 // // HACK: Moving the box UR.y by+1 avoids
106 // // colinearity between port point and box that confuses
107 // // Proutespline(). it's a bug in Proutespline() but this
108 // // is the easiest fix.
109 // fTailEnd.box.ury = fStart.y + 1;
110 // fTailEnd.sidemask = Route.BOTTOM;
111 // } else if (e.isFlat()) {
112 // fTailEnd.box.lly = fStart.y;
113 // fTailEnd.sidemask = Route.TOP;
114 // } else {
115 // fTailEnd.box.ury = fStart.y;
116 // fTailEnd.sidemask = Route.BOTTOM;
117 // }
118 // fTailEnd.subDivideBox();
119 return this;
120 }
121
122 public DotPath endPath(VirtualEdge e) {
123 VirtualVertex v = e.head;
124 fEnd.x = v.x;
125 fEnd.y = v.y;
126 if (e.headPort != null) {
127 fEnd.x += e.headPort.dx;
128 fEnd.y += e.headPort.dy;
129 }
130 if (v.isEdge()) {
131 fEnd.theta = averageSlope(v) + Math.PI;
132 if (fEnd.theta >= 2 * Math.PI)
133 msg.err(NAME + ".endPath(): end.theta>=2*PI");
134 fEnd.constrained = true;
135 } else if (e.headPort != null && e.headPort.constrained) {
136 fEnd.theta = e.headPort.theta;
137 fEnd.constrained = true;
138 //} else if (v.isReal()) {
139 //fEnd.constrained = true;
140 //fEnd.theta = Math.atan2((e.head.y - e.tail.y), e.head.x - e.tail.x);
141 //fEnd.theta += Math.PI;
142 } else {
143 fEnd.constrained = false;
144 }
145 // fHeadEnd.port.x = fEnd.x;
146 // fHeadEnd.port.y = fEnd.y;
147 //
148 //if(pboxfn)
149 //fHeadEnd.sidemask=(*pboxfn)(n,e,2,fHeadEnd.boxes[0],fHeadEnd.nBox);
150 //else {
151 //fHeadEnd.boxes[0] = fHeadEnd.box;
152 //fHeadEnd.nBox = 1;
153 //}
154 // if (e.isSelf()) {
155 // fHeadEnd.box.lly = fEnd.y;
156 // fHeadEnd.sidemask = Route.TOP;
157 // } else if (e.isFlat()) {
158 // fHeadEnd.box.lly = fEnd.y;
159 // fHeadEnd.sidemask = Route.TOP;
160 // } else {
161 // fHeadEnd.box.lly = fEnd.y;
162 // fHeadEnd.sidemask = Route.TOP;
163 // }
164 // fHeadEnd.subDivideBox();
165 return this;
166 }
167
168 public String toString() {
169 StringBuffer ret = new StringBuffer("DotPath:\n");
170 for (int i = 0; i < fSize; ++i) {
171 if (i % 4 == 3)
172 ret.append(fBoxes[i].toString() + "\n");
173 else
174 ret.append(fBoxes[i].toString() + " ");
175 }
176 ret.append("\n");
177 return ret.toString();
178 }
179
180 public String toGeneralPath() {
181 StringBuffer ret = new StringBuffer("// DotPath:\n<path>\n");
182 for (int i = 0; i < fSize; ++i) {
183 ret.append(fBoxes[i].toGeneralPath());
184 }
185 ret.append("</path>\n");
186 return ret.toString();
187 }
188
189 // Helper functions ////////////////////////////////////////////////////
190 //
191
192 /** Find the average slope of all in and out edges at 'v'.
193 *
194 * @return slope in radian (-pi..pi).
195 */
196 private double averageSlope(VirtualVertex v) {
197 double inslope, outslope, x, y;
198 VirtualEdge e;
199
200 int n;
201 double sum;
202 for (n = 0, sum = 0.0; n < v.ins.length; n++) {
203 e = v.ins[n];
204 sum += e.tail.x;
205 }
206 x = v.x - (sum / n);
207 y = v.y - v.ins[0].tail.y;
208 inslope = Math.atan2(y, x);
209 //
210 for (n = 0, sum = 0.0; n < v.outs.length; n++) {
211 e = v.outs[n];
212 sum += e.head.x;
213 }
214 x = (sum / n) - v.x;
215 y = v.outs[0].head.y - v.y;
216 outslope = Math.atan2(y, x);
217 return ((inslope + outslope) / 2.0);
218 }
219
220 // Boxes functions /////////////////////////////////////////////////////
221 //
222
223 /**
224 * @param boxes The rank boxes (including rank boxes for head and tail).
225 * @param boxn The number of boxes in 'boxes'.
226 */
227 public void completeRegularPath(VirtualEdge firste, VirtualEdge laste) {
228 // DotBox[] uboxes = new DotBox[NSUB];
229 // DotBox[] lboxes = new DotBox[NSUB];
230 // //int firstbox = -1;
231 // //int lastbox = -1;
232 //
233 // for (int i = 0; i < fTailEnd.size(); ++i)
234 // add(fTailEnd.get(i));
235 //
236 // //VirtualEdge ule = null, ure = null, lle = null, lre = null;
237 // int lboxn = 0;
238 // int uboxn = 0;
239 // int len = laste.head.rank - firste.tail.rank;
240 // if (len == 0)
241 // msg.err(
242 // NAME
243 // + ".completeRegularPath(): len==0: tail="
244 // + firste.tail.getName()
245 // + ", head="
246 // + laste.head.getName());
247 // if (len > 1) {
248 // // If tail and head are more than one rank apart, bound
249 // // the routing between any routed neighbour.
250 // /*
251 // ule = topBound(firste, -1);
252 // ure = topBound(firste, 1);
253 // lle = bottomBound(laste, -1);
254 // lre = bottomBound(laste, 1);
255 // if (DEBUG)
256 // msg.println(
257 // NAME
258 // + ".completeRegularPath(): "1
259 // + "firste="
260 // + firste
261 // + "\nlaste="
262 // + laste
263 // + "\nule="
264 // + ule
265 // + "\nure="
266 // + ure
267 // + "\nlle="
268 // + lle
269 // + "\nlre="
270 // + lre
271 // + "\n");
272 // */
273 // uboxn = boxlist.get(0).subDivide(NSUB,uboxes);
274 // lboxn = boxlist.getLast().subDivide(NSUB,lboxes);
275 // //refineRegularEnds(uboxes, uboxn, ule, ure, path, fTailEnd, true);
276 // //refineRegularEnds(lboxes, lboxn, lle, lre, path, fHeadEnd, false);
277 // for (int i = 0; i < uboxn; i++)
278 // add(uboxes[i]);
279 // // Skip the refined inter-rank boxes.
280 // //firstbox = nBox;
281 // //lastbox = firstbox + rboxn - 3;
282 // for (int i = 1; i < boxlist.size() - 1; i++)
283 // add(boxlist.get(i));
284 // for (int i = 0; i < lboxn; i++)
285 // add(lboxes[i]);
286 // } else {
287 // // There are only one inter-rank box. Don't constrain the
288 // // route otherwise it may be impossible to route.
289 // uboxn = boxlist.get(0).subDivide(NSUB, uboxes);
290 // for (int i = 0; i < uboxn; i++)
291 // add(uboxes[i]);
292 // }
293 // //NOTE: Original fHeadEnd.boxes are indexed from bottom up.
294 // // Now it is changed to top down.
295 // for (int i = 0; i < fHeadEnd.size(); ++i)
296 // add(fHeadEnd.get(i));
297 // //adjustRegularPath(path,firstbox,lastbox);
298 }
299
300 ////////////////////////////////////////////////////////////////////////
301
302 }