1 | /* network.c |
---|
2 | * Survex network reduction - find patterns and apply network reductions |
---|
3 | * Copyright (C) 1991-2002,2005 Olly Betts |
---|
4 | * |
---|
5 | * This program is free software; you can redistribute it and/or modify |
---|
6 | * it under the terms of the GNU General Public License as published by |
---|
7 | * the Free Software Foundation; either version 2 of the License, or |
---|
8 | * (at your option) any later version. |
---|
9 | * |
---|
10 | * This program is distributed in the hope that it will be useful, |
---|
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
13 | * GNU General Public License for more details. |
---|
14 | * |
---|
15 | * You should have received a copy of the GNU General Public License |
---|
16 | * along with this program; if not, write to the Free Software |
---|
17 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
---|
18 | */ |
---|
19 | |
---|
20 | #if 0 |
---|
21 | #define DEBUG_INVALID 1 |
---|
22 | #define VALIDATE 1 |
---|
23 | #define DUMP_NETWORK 1 |
---|
24 | #endif |
---|
25 | |
---|
26 | #include <config.h> |
---|
27 | |
---|
28 | #include "validate.h" |
---|
29 | #include "debug.h" |
---|
30 | #include "cavern.h" |
---|
31 | #include "message.h" |
---|
32 | #include "netbits.h" |
---|
33 | #include "network.h" |
---|
34 | #include "out.h" |
---|
35 | |
---|
36 | /* type field isn't vital - join3 is unused except for deltastar, so |
---|
37 | * we can set its value to indicate which type this is: |
---|
38 | * join3 == NULL for noose, join3 == join1 for ||, otherwise D* */ |
---|
39 | #ifdef EXPLICIT_STACKRED_TYPE |
---|
40 | #define SET_NOOSE(SR) (SR)->type = 1 |
---|
41 | #define IS_NOOSE(SR) ((SR)->type == 1) |
---|
42 | #define SET_PARALLEL(SR) (SR)->type = 0 |
---|
43 | #define IS_PARALLEL(SR) ((SR)->type == 0) |
---|
44 | #define SET_DELTASTAR(SR) (SR)->type = 2 |
---|
45 | #define IS_DELTASTAR(SR) ((SR)->type == 2) |
---|
46 | #else |
---|
47 | #define IS_NOOSE(SR) ((SR)->join3 == NULL) |
---|
48 | #define SET_NOOSE(SR) (SR)->join3 = NULL |
---|
49 | #define IS_PARALLEL(SR) ((SR)->join3 == (SR)->join1) |
---|
50 | #define SET_PARALLEL(SR) (SR)->join3 = (SR)->join1 |
---|
51 | #define IS_DELTASTAR(SR) (!IS_NOOSE(SR) && !IS_PARALLEL(SR)) |
---|
52 | #define SET_DELTASTAR(SR) NOP |
---|
53 | #endif |
---|
54 | |
---|
55 | typedef struct StackRed { |
---|
56 | struct Link *join1, *join2, *join3; |
---|
57 | #ifdef EXPLICIT_STACKRED_TYPE |
---|
58 | int type; /* 1 => noose, 0 => parallel legs, 2 => delta-star */ |
---|
59 | #endif |
---|
60 | struct StackRed *next; |
---|
61 | } stackRed; |
---|
62 | |
---|
63 | static stackRed *ptrRed; /* Ptr to TRaverse linked list for C*-*< , -*=*- */ |
---|
64 | |
---|
65 | /* can be altered by -z<letters> on command line */ |
---|
66 | unsigned long optimize = BITA('l') | BITA('p') | BITA('d'); |
---|
67 | /* Lollipops, Parallel legs, Iterate mx, Delta* */ |
---|
68 | |
---|
69 | extern void |
---|
70 | remove_subnets(void) |
---|
71 | { |
---|
72 | node *stn, *stn2, *stn3, *stn4; |
---|
73 | int dirn, dirn2, dirn3, dirn4; |
---|
74 | stackRed *trav; |
---|
75 | linkfor *newleg, *newleg2; |
---|
76 | bool fMore = true; |
---|
77 | |
---|
78 | ptrRed = NULL; |
---|
79 | |
---|
80 | out_current_action(msg(/*Simplifying network*/129)); |
---|
81 | |
---|
82 | while (fMore) { |
---|
83 | fMore = false; |
---|
84 | if (optimize & BITA('l')) { |
---|
85 | #if PRINT_NETBITS |
---|
86 | printf("replacing lollipops\n"); |
---|
87 | #endif |
---|
88 | /* _ |
---|
89 | * ( ) |
---|
90 | * * stn |
---|
91 | * | |
---|
92 | * * stn2 |
---|
93 | * stn /| |
---|
94 | * 4 * * stn3 --> stn4 *-* stn3 |
---|
95 | * : : : : |
---|
96 | */ |
---|
97 | /* NB can have non-fixed 0 nodes */ |
---|
98 | FOR_EACH_STN(stn, stnlist) { |
---|
99 | if (!fixed(stn) && three_node(stn)) { |
---|
100 | dirn = -1; |
---|
101 | if (stn->leg[1]->l.to == stn) dirn++; |
---|
102 | if (stn->leg[0]->l.to == stn) dirn += 2; |
---|
103 | if (dirn < 0) continue; |
---|
104 | |
---|
105 | stn2 = stn->leg[dirn]->l.to; |
---|
106 | if (fixed(stn2)) continue; |
---|
107 | |
---|
108 | SVX_ASSERT(three_node(stn2)); |
---|
109 | |
---|
110 | dirn2 = reverse_leg_dirn(stn->leg[dirn]); |
---|
111 | dirn2 = (dirn2 + 1) % 3; |
---|
112 | stn3 = stn2->leg[dirn2]->l.to; |
---|
113 | if (stn2 == stn3) continue; /* dumb-bell - leave alone */ |
---|
114 | |
---|
115 | dirn3 = reverse_leg_dirn(stn2->leg[dirn2]); |
---|
116 | |
---|
117 | trav = osnew(stackRed); |
---|
118 | newleg2 = (linkfor*)osnew(linkrev); |
---|
119 | |
---|
120 | newleg = copy_link(stn3->leg[dirn3]); |
---|
121 | |
---|
122 | dirn2 = (dirn2 + 1) % 3; |
---|
123 | stn4 = stn2->leg[dirn2]->l.to; |
---|
124 | dirn4 = reverse_leg_dirn(stn2->leg[dirn2]); |
---|
125 | #if 0 |
---|
126 | printf("Noose found with stn...stn4 = \n"); |
---|
127 | print_prefix(stn->name); putnl(); |
---|
128 | print_prefix(stn2->name); putnl(); |
---|
129 | print_prefix(stn3->name); putnl(); |
---|
130 | print_prefix(stn4->name); putnl(); |
---|
131 | #endif |
---|
132 | |
---|
133 | addto_link(newleg, stn2->leg[dirn2]); |
---|
134 | |
---|
135 | /* remove stn and stn2 */ |
---|
136 | remove_stn_from_list(&stnlist, stn); |
---|
137 | remove_stn_from_list(&stnlist, stn2); |
---|
138 | |
---|
139 | /* stack noose and replace with a leg between stn3 and stn4 */ |
---|
140 | trav->join1 = stn3->leg[dirn3]; |
---|
141 | newleg->l.to = stn4; |
---|
142 | newleg->l.reverse = dirn4 | FLAG_DATAHERE | FLAG_REPLACEMENTLEG; |
---|
143 | |
---|
144 | trav->join2 = stn4->leg[dirn4]; |
---|
145 | newleg2->l.to = stn3; |
---|
146 | newleg2->l.reverse = dirn3 | FLAG_REPLACEMENTLEG; |
---|
147 | |
---|
148 | stn3->leg[dirn3] = newleg; |
---|
149 | stn4->leg[dirn4] = newleg2; |
---|
150 | |
---|
151 | trav->next = ptrRed; |
---|
152 | SET_NOOSE(trav); |
---|
153 | #if PRINT_NETBITS |
---|
154 | printf("remove noose\n"); |
---|
155 | #endif |
---|
156 | ptrRed = trav; |
---|
157 | fMore = true; |
---|
158 | } |
---|
159 | } |
---|
160 | } |
---|
161 | |
---|
162 | if (optimize & BITA('p')) { |
---|
163 | #if PRINT_NETBITS |
---|
164 | printf("replacing parallel legs\n"); |
---|
165 | #endif |
---|
166 | FOR_EACH_STN(stn, stnlist) { |
---|
167 | /* |
---|
168 | * : |
---|
169 | * * stn3 |
---|
170 | * | : |
---|
171 | * * stn * stn3 |
---|
172 | * ( ) -> | |
---|
173 | * * stn2 * stn4 |
---|
174 | * | : |
---|
175 | * * stn4 |
---|
176 | * : |
---|
177 | */ |
---|
178 | if (!fixed(stn) && three_node(stn)) { |
---|
179 | stn2 = stn->leg[0]->l.to; |
---|
180 | if (stn2 == stn->leg[1]->l.to) { |
---|
181 | dirn = 2; |
---|
182 | } else if (stn2 == stn->leg[2]->l.to) { |
---|
183 | dirn = 1; |
---|
184 | } else { |
---|
185 | if (stn->leg[1]->l.to != stn->leg[2]->l.to) continue; |
---|
186 | stn2 = stn->leg[1]->l.to; |
---|
187 | dirn = 0; |
---|
188 | } |
---|
189 | |
---|
190 | /* stn == stn2 => noose */ |
---|
191 | if (fixed(stn2) || stn == stn2) continue; |
---|
192 | |
---|
193 | SVX_ASSERT(three_node(stn2)); |
---|
194 | |
---|
195 | stn3 = stn->leg[dirn]->l.to; |
---|
196 | /* 3 parallel legs (=> nothing else) so leave */ |
---|
197 | if (stn3 == stn2) continue; |
---|
198 | |
---|
199 | dirn3 = reverse_leg_dirn(stn->leg[dirn]); |
---|
200 | dirn2 = (0 + 1 + 2 - reverse_leg_dirn(stn->leg[(dirn + 1) % 3]) |
---|
201 | - reverse_leg_dirn(stn->leg[(dirn + 2) % 3])); |
---|
202 | |
---|
203 | stn4 = stn2->leg[dirn2]->l.to; |
---|
204 | dirn4 = reverse_leg_dirn(stn2->leg[dirn2]); |
---|
205 | |
---|
206 | trav = osnew(stackRed); |
---|
207 | |
---|
208 | newleg = copy_link(stn->leg[(dirn + 1) % 3]); |
---|
209 | /* use newleg2 for scratch */ |
---|
210 | newleg2 = copy_link(stn->leg[(dirn + 2) % 3]); |
---|
211 | { |
---|
212 | #ifdef NO_COVARIANCES |
---|
213 | vars sum; |
---|
214 | var prod; |
---|
215 | delta temp, temp2; |
---|
216 | addss(&sum, &newleg->v, &newleg2->v); |
---|
217 | SVX_ASSERT2(!fZeros(&sum), "loop of zero variance found"); |
---|
218 | mulss(&prod, &newleg->v, &newleg2->v); |
---|
219 | mulsd(&temp, &newleg2->v, &newleg->d); |
---|
220 | mulsd(&temp2, &newleg->v, &newleg2->d); |
---|
221 | adddd(&temp, &temp, &temp2); |
---|
222 | divds(&newleg->d, &temp, &sum); |
---|
223 | sdivvs(&newleg->v, &prod, &sum); |
---|
224 | #else |
---|
225 | svar inv1, inv2, sum; |
---|
226 | delta temp, temp2; |
---|
227 | /* if leg one is an equate, we can just ignore leg two |
---|
228 | * whatever it is */ |
---|
229 | if (invert_svar(&inv1, &newleg->v)) { |
---|
230 | if (invert_svar(&inv2, &newleg2->v)) { |
---|
231 | addss(&sum, &inv1, &inv2); |
---|
232 | if (!invert_svar(&newleg->v, &sum)) { |
---|
233 | BUG("matrix singular in parallel legs replacement"); |
---|
234 | } |
---|
235 | |
---|
236 | mulsd(&temp, &inv1, &newleg->d); |
---|
237 | mulsd(&temp2, &inv2, &newleg2->d); |
---|
238 | adddd(&temp, &temp, &temp2); |
---|
239 | mulsd(&newleg->d, &newleg->v, &temp); |
---|
240 | } else { |
---|
241 | /* leg two is an equate, so just ignore leg 1 */ |
---|
242 | linkfor *tmpleg; |
---|
243 | tmpleg = newleg; |
---|
244 | newleg = newleg2; |
---|
245 | newleg2 = tmpleg; |
---|
246 | } |
---|
247 | } |
---|
248 | #endif |
---|
249 | } |
---|
250 | osfree(newleg2); |
---|
251 | newleg2 = (linkfor*)osnew(linkrev); |
---|
252 | |
---|
253 | addto_link(newleg, stn2->leg[dirn2]); |
---|
254 | addto_link(newleg, stn3->leg[dirn3]); |
---|
255 | |
---|
256 | #if 0 |
---|
257 | printf("Parallel found with stn...stn4 = \n"); |
---|
258 | (dump_node)(stn); (dump_node)(stn2); (dump_node)(stn3); (dump_node)(stn4); |
---|
259 | printf("dirns = %d %d %d %d\n", dirn, dirn2, dirn3, dirn4); |
---|
260 | #endif |
---|
261 | SVX_ASSERT2(stn3->leg[dirn3]->l.to == stn, "stn3 end of || doesn't recip"); |
---|
262 | SVX_ASSERT2(stn4->leg[dirn4]->l.to == stn2, "stn4 end of || doesn't recip"); |
---|
263 | SVX_ASSERT2(stn->leg[(dirn+1)%3]->l.to == stn2 && stn->leg[(dirn + 2) % 3]->l.to == stn2, "|| legs aren't"); |
---|
264 | |
---|
265 | /* remove stn and stn2 (already discarded triple parallel) */ |
---|
266 | /* so stn!=stn4 <=> stn2!=stn3 */ |
---|
267 | remove_stn_from_list(&stnlist, stn); |
---|
268 | remove_stn_from_list(&stnlist, stn2); |
---|
269 | |
---|
270 | /* stack parallel and replace with a leg between stn3 and stn4 */ |
---|
271 | trav->join1 = stn3->leg[dirn3]; |
---|
272 | newleg->l.to = stn4; |
---|
273 | newleg->l.reverse = dirn4 | FLAG_DATAHERE | FLAG_REPLACEMENTLEG; |
---|
274 | |
---|
275 | trav->join2 = stn4->leg[dirn4]; |
---|
276 | newleg2->l.to = stn3; |
---|
277 | newleg2->l.reverse = dirn3 | FLAG_REPLACEMENTLEG; |
---|
278 | |
---|
279 | stn3->leg[dirn3] = newleg; |
---|
280 | stn4->leg[dirn4] = newleg2; |
---|
281 | |
---|
282 | trav->next = ptrRed; |
---|
283 | SET_PARALLEL(trav); |
---|
284 | #if PRINT_NETBITS |
---|
285 | printf("remove parallel\n"); |
---|
286 | #endif |
---|
287 | ptrRed = trav; |
---|
288 | fMore = true; |
---|
289 | } |
---|
290 | } |
---|
291 | } |
---|
292 | |
---|
293 | if (optimize & BITA('d')) { |
---|
294 | node *stn5, *stn6; |
---|
295 | int dirn5, dirn6, dirn0; |
---|
296 | linkfor *legAB, *legBC, *legCA; |
---|
297 | #if PRINT_NETBITS |
---|
298 | printf("replacing deltas with stars\n"); |
---|
299 | #endif |
---|
300 | FOR_EACH_STN(stn, stnlist) { |
---|
301 | /* printf("*");*/ |
---|
302 | /* |
---|
303 | * : |
---|
304 | * * stn5 : |
---|
305 | * | * stn5 |
---|
306 | * * stn2 | |
---|
307 | * / \ -> O stnZ |
---|
308 | * stn *---* stn3 / \ |
---|
309 | * / \ stn4 * * stn6 |
---|
310 | * stn4 * * stn6 : : |
---|
311 | * : : |
---|
312 | */ |
---|
313 | if (!fixed(stn) && three_node(stn)) { |
---|
314 | for (dirn0 = 0; ; dirn0++) { |
---|
315 | if (dirn0 >= 3) goto nodeltastar; /* continue outer loop */ |
---|
316 | dirn = dirn0; |
---|
317 | stn2 = stn->leg[dirn]->l.to; |
---|
318 | if (fixed(stn2) || stn2 == stn) continue; |
---|
319 | dirn2 = reverse_leg_dirn(stn->leg[dirn]); |
---|
320 | dirn2 = (dirn2 + 1) % 3; |
---|
321 | stn3 = stn2->leg[dirn2]->l.to; |
---|
322 | if (fixed(stn3) || stn3 == stn || stn3 == stn2) |
---|
323 | goto nextdirn2; |
---|
324 | dirn3 = reverse_leg_dirn(stn2->leg[dirn2]); |
---|
325 | dirn3 = (dirn3 + 1) % 3; |
---|
326 | if (stn3->leg[dirn3]->l.to == stn) { |
---|
327 | legAB = copy_link(stn->leg[dirn]); |
---|
328 | legBC = copy_link(stn2->leg[dirn2]); |
---|
329 | legCA = copy_link(stn3->leg[dirn3]); |
---|
330 | dirn = 0 + 1 + 2 - dirn - reverse_leg_dirn(stn3->leg[dirn3]); |
---|
331 | dirn2 = (dirn2 + 1) % 3; |
---|
332 | dirn3 = (dirn3 + 1) % 3; |
---|
333 | } else if (stn3->leg[(dirn3 + 1) % 3]->l.to == stn) { |
---|
334 | legAB = copy_link(stn->leg[dirn]); |
---|
335 | legBC = copy_link(stn2->leg[dirn2]); |
---|
336 | legCA = copy_link(stn3->leg[(dirn3 + 1) % 3]); |
---|
337 | dirn = (0 + 1 + 2 - dirn |
---|
338 | - reverse_leg_dirn(stn3->leg[(dirn3 + 1) % 3])); |
---|
339 | dirn2 = (dirn2 + 1) % 3; |
---|
340 | break; |
---|
341 | } else { |
---|
342 | nextdirn2:; |
---|
343 | dirn2 = (dirn2 + 1) % 3; |
---|
344 | stn3 = stn2->leg[dirn2]->l.to; |
---|
345 | if (fixed(stn3) || stn3 == stn || stn3 == stn2) continue; |
---|
346 | dirn3 = reverse_leg_dirn(stn2->leg[dirn2]); |
---|
347 | dirn3 = (dirn3 + 1) % 3; |
---|
348 | if (stn3->leg[dirn3]->l.to == stn) { |
---|
349 | legAB = copy_link(stn->leg[dirn]); |
---|
350 | legBC = copy_link(stn2->leg[dirn2]); |
---|
351 | legCA = copy_link(stn3->leg[dirn3]); |
---|
352 | dirn = (0 + 1 + 2 - dirn |
---|
353 | - reverse_leg_dirn(stn3->leg[dirn3])); |
---|
354 | dirn2 = (dirn2 + 2) % 3; |
---|
355 | dirn3 = (dirn3 + 1) % 3; |
---|
356 | break; |
---|
357 | } else if (stn3->leg[(dirn3 + 1) % 3]->l.to == stn) { |
---|
358 | legAB = copy_link(stn->leg[dirn]); |
---|
359 | legBC = copy_link(stn2->leg[dirn2]); |
---|
360 | legCA = copy_link(stn3->leg[(dirn3 + 1) % 3]); |
---|
361 | dirn = (0 + 1 + 2 - dirn |
---|
362 | - reverse_leg_dirn(stn3->leg[(dirn3 + 1) % 3])); |
---|
363 | dirn2 = (dirn2 + 2) % 3; |
---|
364 | break; |
---|
365 | } |
---|
366 | } |
---|
367 | } |
---|
368 | |
---|
369 | SVX_ASSERT(three_node(stn2)); |
---|
370 | SVX_ASSERT(three_node(stn3)); |
---|
371 | |
---|
372 | stn4 = stn->leg[dirn]->l.to; |
---|
373 | stn5 = stn2->leg[dirn2]->l.to; |
---|
374 | stn6 = stn3->leg[dirn3]->l.to; |
---|
375 | |
---|
376 | if (stn4 == stn2 || stn4 == stn3 || stn5 == stn3) break; |
---|
377 | |
---|
378 | dirn4 = reverse_leg_dirn(stn->leg[dirn]); |
---|
379 | dirn5 = reverse_leg_dirn(stn2->leg[dirn2]); |
---|
380 | dirn6 = reverse_leg_dirn(stn3->leg[dirn3]); |
---|
381 | #if 0 |
---|
382 | printf("delta-star, stn ... stn6 are:\n"); |
---|
383 | (dump_node)(stn); |
---|
384 | (dump_node)(stn2); |
---|
385 | (dump_node)(stn3); |
---|
386 | (dump_node)(stn4); |
---|
387 | (dump_node)(stn5); |
---|
388 | (dump_node)(stn6); |
---|
389 | #endif |
---|
390 | SVX_ASSERT(stn4->leg[dirn4]->l.to == stn); |
---|
391 | SVX_ASSERT(stn5->leg[dirn5]->l.to == stn2); |
---|
392 | SVX_ASSERT(stn6->leg[dirn6]->l.to == stn3); |
---|
393 | |
---|
394 | trav = osnew(stackRed); |
---|
395 | { |
---|
396 | linkfor *legAZ, *legBZ, *legCZ; |
---|
397 | node *stnZ; |
---|
398 | prefix *nameZ; |
---|
399 | svar invAB, invBC, invCA, tmp, sum, inv; |
---|
400 | var vtmp; |
---|
401 | svar sumAZBZ, sumBZCZ, sumCZAZ; |
---|
402 | delta temp, temp2; |
---|
403 | |
---|
404 | /* FIXME: ought to handle cases when some legs are |
---|
405 | * equates, but handle as a special case maybe? */ |
---|
406 | if (!invert_svar(&invAB, &legAB->v)) break; |
---|
407 | if (!invert_svar(&invBC, &legBC->v)) break; |
---|
408 | if (!invert_svar(&invCA, &legCA->v)) break; |
---|
409 | |
---|
410 | addss(&sum, &legBC->v, &legCA->v); |
---|
411 | addss(&tmp, &sum, &legAB->v); |
---|
412 | if (!invert_svar(&inv, &tmp)) { |
---|
413 | /* impossible - loop of zero variance */ |
---|
414 | BUG("loop of zero variance found"); |
---|
415 | } |
---|
416 | |
---|
417 | legAZ = osnew(linkfor); |
---|
418 | legBZ = osnew(linkfor); |
---|
419 | legCZ = osnew(linkfor); |
---|
420 | |
---|
421 | /* AZBZ */ |
---|
422 | /* done above: addvv(&sum, &legBC->v, &legCA->v); */ |
---|
423 | mulss(&vtmp, &sum, &inv); |
---|
424 | smulvs(&sumAZBZ, &vtmp, &legAB->v); |
---|
425 | |
---|
426 | adddd(&temp, &legBC->d, &legCA->d); |
---|
427 | divds(&temp2, &temp, &sum); |
---|
428 | mulsd(&temp, &invAB, &legAB->d); |
---|
429 | subdd(&temp, &temp2, &temp); |
---|
430 | mulsd(&legBZ->d, &sumAZBZ, &temp); |
---|
431 | |
---|
432 | /* leg vectors after transform are determined up to |
---|
433 | * a constant addition, so arbitrarily fix AZ = 0 */ |
---|
434 | legAZ->d[2] = legAZ->d[1] = legAZ->d[0] = 0; |
---|
435 | |
---|
436 | /* BZCZ */ |
---|
437 | addss(&sum, &legCA->v, &legAB->v); |
---|
438 | mulss(&vtmp, &sum, &inv); |
---|
439 | smulvs(&sumBZCZ, &vtmp, &legBC->v); |
---|
440 | |
---|
441 | /* CZAZ */ |
---|
442 | addss(&sum, &legAB->v, &legBC->v); |
---|
443 | mulss(&vtmp, &sum, &inv); |
---|
444 | smulvs(&sumCZAZ, &vtmp, &legCA->v); |
---|
445 | |
---|
446 | adddd(&temp, &legAB->d, &legBC->d); |
---|
447 | divds(&temp2, &temp, &sum); |
---|
448 | mulsd(&temp, &invCA, &legCA->d); |
---|
449 | /* NB: swapped arguments to negate answer for legCZ->d */ |
---|
450 | subdd(&temp, &temp, &temp2); |
---|
451 | mulsd(&legCZ->d, &sumCZAZ, &temp); |
---|
452 | |
---|
453 | osfree(legAB); |
---|
454 | osfree(legBC); |
---|
455 | osfree(legCA); |
---|
456 | |
---|
457 | /* Now add two, subtract third, and scale by 0.5 */ |
---|
458 | addss(&sum, &sumAZBZ, &sumCZAZ); |
---|
459 | subss(&sum, &sum, &sumBZCZ); |
---|
460 | mulsc(&legAZ->v, &sum, 0.5); |
---|
461 | |
---|
462 | addss(&sum, &sumBZCZ, &sumAZBZ); |
---|
463 | subss(&sum, &sum, &sumCZAZ); |
---|
464 | mulsc(&legBZ->v, &sum, 0.5); |
---|
465 | |
---|
466 | addss(&sum, &sumCZAZ, &sumBZCZ); |
---|
467 | subss(&sum, &sum, &sumAZBZ); |
---|
468 | mulsc(&legCZ->v, &sum, 0.5); |
---|
469 | |
---|
470 | nameZ = osnew(prefix); |
---|
471 | nameZ->pos = osnew(pos); |
---|
472 | nameZ->ident = NULL; |
---|
473 | nameZ->shape = 3; |
---|
474 | stnZ = osnew(node); |
---|
475 | stnZ->name = nameZ; |
---|
476 | nameZ->stn = stnZ; |
---|
477 | nameZ->up = NULL; |
---|
478 | nameZ->min_export = nameZ->max_export = 0; |
---|
479 | unfix(stnZ); |
---|
480 | add_stn_to_list(&stnlist, stnZ); |
---|
481 | legAZ->l.to = stnZ; |
---|
482 | legAZ->l.reverse = 0 | FLAG_DATAHERE | FLAG_REPLACEMENTLEG; |
---|
483 | legBZ->l.to = stnZ; |
---|
484 | legBZ->l.reverse = 1 | FLAG_DATAHERE | FLAG_REPLACEMENTLEG; |
---|
485 | legCZ->l.to = stnZ; |
---|
486 | legCZ->l.reverse = 2 | FLAG_DATAHERE | FLAG_REPLACEMENTLEG; |
---|
487 | stnZ->leg[0] = (linkfor*)osnew(linkrev); |
---|
488 | stnZ->leg[1] = (linkfor*)osnew(linkrev); |
---|
489 | stnZ->leg[2] = (linkfor*)osnew(linkrev); |
---|
490 | stnZ->leg[0]->l.to = stn4; |
---|
491 | stnZ->leg[0]->l.reverse = dirn4; |
---|
492 | stnZ->leg[1]->l.to = stn5; |
---|
493 | stnZ->leg[1]->l.reverse = dirn5; |
---|
494 | stnZ->leg[2]->l.to = stn6; |
---|
495 | stnZ->leg[2]->l.reverse = dirn6; |
---|
496 | addto_link(legAZ, stn4->leg[dirn4]); |
---|
497 | addto_link(legBZ, stn5->leg[dirn5]); |
---|
498 | addto_link(legCZ, stn6->leg[dirn6]); |
---|
499 | /* stack stuff */ |
---|
500 | trav->join1 = stn4->leg[dirn4]; |
---|
501 | trav->join2 = stn5->leg[dirn5]; |
---|
502 | trav->join3 = stn6->leg[dirn6]; |
---|
503 | trav->next = ptrRed; |
---|
504 | SET_DELTASTAR(trav); |
---|
505 | #if PRINT_NETBITS |
---|
506 | printf("remove delta*\n"); |
---|
507 | #endif |
---|
508 | ptrRed = trav; |
---|
509 | fMore = true; |
---|
510 | |
---|
511 | remove_stn_from_list(&stnlist, stn); |
---|
512 | remove_stn_from_list(&stnlist, stn2); |
---|
513 | remove_stn_from_list(&stnlist, stn3); |
---|
514 | stn4->leg[dirn4] = legAZ; |
---|
515 | stn5->leg[dirn5] = legBZ; |
---|
516 | stn6->leg[dirn6] = legCZ; |
---|
517 | } |
---|
518 | |
---|
519 | } |
---|
520 | nodeltastar:; |
---|
521 | } |
---|
522 | } |
---|
523 | |
---|
524 | } |
---|
525 | } |
---|
526 | |
---|
527 | extern void |
---|
528 | replace_subnets(void) |
---|
529 | { |
---|
530 | stackRed *ptrOld; |
---|
531 | node *stn2, *stn3, *stn4; |
---|
532 | int dirn2, dirn3, dirn4; |
---|
533 | |
---|
534 | /* help to catch bad accesses */ |
---|
535 | stn2 = stn3 = stn4 = NULL; |
---|
536 | dirn2 = dirn3 = dirn4 = 0; |
---|
537 | |
---|
538 | out_current_action(msg(/*Calculating network*/130)); |
---|
539 | |
---|
540 | while (ptrRed != NULL) { |
---|
541 | /* printf("replace_subnets() type %d\n", ptrRed->type);*/ |
---|
542 | |
---|
543 | #if PRINT_NETBITS |
---|
544 | printf("replace_subnets\n"); |
---|
545 | if (IS_NOOSE(ptrRed)) printf("isnoose\n"); |
---|
546 | if (IS_PARALLEL(ptrRed)) printf("isparallel\n"); |
---|
547 | if (IS_DELTASTAR(ptrRed)) printf("isdelta*\n"); |
---|
548 | #endif |
---|
549 | |
---|
550 | if (!IS_DELTASTAR(ptrRed)) { |
---|
551 | linkfor *leg; |
---|
552 | leg = ptrRed->join1; leg = reverse_leg(leg); |
---|
553 | stn3 = leg->l.to; dirn3 = reverse_leg_dirn(leg); |
---|
554 | leg = ptrRed->join2; leg = reverse_leg(leg); |
---|
555 | stn4 = leg->l.to; dirn4 = reverse_leg_dirn(leg); |
---|
556 | |
---|
557 | SVX_ASSERT(fixed(stn3)); |
---|
558 | SVX_ASSERT(fixed(stn4)); |
---|
559 | SVX_ASSERT(data_here(stn3->leg[dirn3])); |
---|
560 | } |
---|
561 | |
---|
562 | if (IS_NOOSE(ptrRed)) { |
---|
563 | /* noose (hanging-loop) */ |
---|
564 | node *stn; |
---|
565 | delta e; |
---|
566 | linkfor *leg; |
---|
567 | int zero; |
---|
568 | |
---|
569 | SVX_ASSERT(fixed(stn3)); |
---|
570 | SVX_ASSERT(fixed(stn4)); |
---|
571 | |
---|
572 | leg = stn3->leg[dirn3]; |
---|
573 | stn2 = ptrRed->join1->l.to; |
---|
574 | dirn2 = reverse_leg_dirn(ptrRed->join1); |
---|
575 | |
---|
576 | zero = fZeros(&leg->v); |
---|
577 | if (!zero) { |
---|
578 | delta tmp; |
---|
579 | subdd(&e, &POSD(stn4), &POSD(stn3)); |
---|
580 | subdd(&tmp, &e, &leg->d); |
---|
581 | divds(&e, &tmp, &leg->v); |
---|
582 | } |
---|
583 | if (data_here(ptrRed->join1)) { |
---|
584 | adddd(&POSD(stn2), &POSD(stn3), &ptrRed->join1->d); |
---|
585 | if (!zero) { |
---|
586 | delta tmp; |
---|
587 | mulsd(&tmp, &ptrRed->join1->v, &e); |
---|
588 | adddd(&POSD(stn2), &POSD(stn2), &tmp); |
---|
589 | } |
---|
590 | } else { |
---|
591 | subdd(&POSD(stn2), &POSD(stn3), &stn2->leg[dirn2]->d); |
---|
592 | if (!zero) { |
---|
593 | delta tmp; |
---|
594 | mulsd(&tmp, &stn2->leg[dirn2]->v, &e); |
---|
595 | adddd(&POSD(stn2), &POSD(stn2), &tmp); |
---|
596 | } |
---|
597 | } |
---|
598 | fix(stn2); |
---|
599 | dirn2 = (dirn2 + 2) % 3; /* point back at stn again */ |
---|
600 | stn = stn2->leg[dirn2]->l.to; |
---|
601 | #if 0 |
---|
602 | printf("Replacing noose with stn...stn4 = \n"); |
---|
603 | print_prefix(stn->name); putnl(); |
---|
604 | print_prefix(stn2->name); putnl(); |
---|
605 | print_prefix(stn3->name); putnl(); |
---|
606 | print_prefix(stn4->name); putnl(); |
---|
607 | #endif |
---|
608 | if (data_here(stn2->leg[dirn2])) |
---|
609 | adddd(&POSD(stn), &POSD(stn2), &stn2->leg[dirn2]->d); |
---|
610 | else |
---|
611 | subdd(&POSD(stn), &POSD(stn2), &reverse_leg(stn2->leg[dirn2])->d); |
---|
612 | |
---|
613 | /* the "rope" of the noose is a new articulation */ |
---|
614 | stn2->leg[dirn2]->l.reverse |= FLAG_ARTICULATION; |
---|
615 | reverse_leg(stn2->leg[dirn2])->l.reverse |= FLAG_ARTICULATION; |
---|
616 | |
---|
617 | fix(stn); |
---|
618 | |
---|
619 | add_stn_to_list(&stnlist, stn); |
---|
620 | add_stn_to_list(&stnlist, stn2); |
---|
621 | |
---|
622 | osfree(stn3->leg[dirn3]); |
---|
623 | stn3->leg[dirn3] = ptrRed->join1; |
---|
624 | osfree(stn4->leg[dirn4]); |
---|
625 | stn4->leg[dirn4] = ptrRed->join2; |
---|
626 | } else if (IS_PARALLEL(ptrRed)) { |
---|
627 | /* parallel legs */ |
---|
628 | node *stn; |
---|
629 | delta e, e2; |
---|
630 | linkfor *leg; |
---|
631 | int dirn; |
---|
632 | |
---|
633 | stn = ptrRed->join1->l.to; |
---|
634 | stn2 = ptrRed->join2->l.to; |
---|
635 | SVX_ASSERT(fixed(stn3)); |
---|
636 | SVX_ASSERT(fixed(stn4)); |
---|
637 | |
---|
638 | dirn = reverse_leg_dirn(ptrRed->join1); |
---|
639 | dirn2 = reverse_leg_dirn(ptrRed->join2); |
---|
640 | |
---|
641 | leg = stn3->leg[dirn3]; |
---|
642 | |
---|
643 | if (leg->l.reverse & FLAG_ARTICULATION) { |
---|
644 | ptrRed->join1->l.reverse |= FLAG_ARTICULATION; |
---|
645 | stn->leg[dirn]->l.reverse |= FLAG_ARTICULATION; |
---|
646 | ptrRed->join2->l.reverse |= FLAG_ARTICULATION; |
---|
647 | stn2->leg[dirn2]->l.reverse |= FLAG_ARTICULATION; |
---|
648 | } |
---|
649 | |
---|
650 | if (fZeros(&leg->v)) |
---|
651 | e[0] = e[1] = e[2] = 0.0; |
---|
652 | else { |
---|
653 | delta tmp; |
---|
654 | subdd(&e, &POSD(stn4), &POSD(stn3)); |
---|
655 | subdd(&tmp, &e, &leg->d); |
---|
656 | divds(&e, &tmp, &leg->v); |
---|
657 | } |
---|
658 | |
---|
659 | if (data_here(ptrRed->join1)) { |
---|
660 | leg = ptrRed->join1; |
---|
661 | adddd(&POSD(stn), &POSD(stn3), &leg->d); |
---|
662 | } else { |
---|
663 | leg = stn->leg[dirn]; |
---|
664 | subdd(&POSD(stn), &POSD(stn3), &leg->d); |
---|
665 | } |
---|
666 | mulsd(&e2, &leg->v, &e); |
---|
667 | adddd(&POSD(stn), &POSD(stn), &e2); |
---|
668 | |
---|
669 | if (data_here(ptrRed->join2)) { |
---|
670 | leg = ptrRed->join2; |
---|
671 | adddd(&POSD(stn2), &POSD(stn4), &leg->d); |
---|
672 | } else { |
---|
673 | leg = stn2->leg[dirn2]; |
---|
674 | subdd(&POSD(stn2), &POSD(stn4), &leg->d); |
---|
675 | } |
---|
676 | mulsd(&e2, &leg->v, &e); |
---|
677 | subdd(&POSD(stn2), &POSD(stn2), &e2); |
---|
678 | fix(stn); |
---|
679 | fix(stn2); |
---|
680 | #if 0 |
---|
681 | printf("Replacing parallel with stn...stn4 = \n"); |
---|
682 | print_prefix(stn->name); putnl(); |
---|
683 | print_prefix(stn2->name); putnl(); |
---|
684 | print_prefix(stn3->name); putnl(); |
---|
685 | print_prefix(stn4->name); putnl(); |
---|
686 | #endif |
---|
687 | |
---|
688 | add_stn_to_list(&stnlist, stn); |
---|
689 | add_stn_to_list(&stnlist, stn2); |
---|
690 | |
---|
691 | osfree(stn3->leg[dirn3]); |
---|
692 | stn3->leg[dirn3] = ptrRed->join1; |
---|
693 | osfree(stn4->leg[dirn4]); |
---|
694 | stn4->leg[dirn4] = ptrRed->join2; |
---|
695 | } else if (IS_DELTASTAR(ptrRed)) { |
---|
696 | node *stnZ; |
---|
697 | node *stn[3]; |
---|
698 | int dirn[3]; |
---|
699 | linkfor *legs[3]; |
---|
700 | int i; |
---|
701 | linkfor *leg; |
---|
702 | |
---|
703 | legs[0] = ptrRed->join1; |
---|
704 | legs[1] = ptrRed->join2; |
---|
705 | legs[2] = ptrRed->join3; |
---|
706 | |
---|
707 | /* work out ends as we don't bother stacking them */ |
---|
708 | leg = reverse_leg(legs[0]); |
---|
709 | stn[0] = leg->l.to; |
---|
710 | dirn[0] = reverse_leg_dirn(leg); |
---|
711 | stnZ = stn[0]->leg[dirn[0]]->l.to; |
---|
712 | SVX_ASSERT(fixed(stnZ)); |
---|
713 | stn[1] = stnZ->leg[1]->l.to; |
---|
714 | dirn[1] = reverse_leg_dirn(stnZ->leg[1]); |
---|
715 | stn[2] = stnZ->leg[2]->l.to; |
---|
716 | dirn[2] = reverse_leg_dirn(stnZ->leg[2]); |
---|
717 | /*print_prefix(stnZ->name);printf(" %p\n",(void*)stnZ);*/ |
---|
718 | |
---|
719 | for (i = 0; i < 3; i++) { |
---|
720 | SVX_ASSERT2(fixed(stn[i]), "stn not fixed for D*"); |
---|
721 | |
---|
722 | leg = stn[i]->leg[dirn[i]]; |
---|
723 | |
---|
724 | SVX_ASSERT2(data_here(leg), "data not on leg for D*"); |
---|
725 | SVX_ASSERT2(leg->l.to == stnZ, "bad sub-network for D*"); |
---|
726 | |
---|
727 | stn2 = legs[i]->l.to; |
---|
728 | |
---|
729 | if (data_here(legs[i])) { |
---|
730 | adddd(&POSD(stn2), &POSD(stn[i]), &legs[i]->d); |
---|
731 | } else { |
---|
732 | subdd(&POSD(stn2), &POSD(stn[i]), &reverse_leg(legs[i])->d); |
---|
733 | } |
---|
734 | |
---|
735 | if (!fZeros(&leg->v)) { |
---|
736 | delta e, tmp; |
---|
737 | subdd(&e, &POSD(stnZ), &POSD(stn[i])); |
---|
738 | subdd(&e, &e, &leg->d); |
---|
739 | divds(&tmp, &e, &leg->v); |
---|
740 | if (data_here(legs[i])) { |
---|
741 | mulsd(&e, &legs[i]->v, &tmp); |
---|
742 | } else { |
---|
743 | mulsd(&e, &reverse_leg(legs[i])->v, &tmp); |
---|
744 | } |
---|
745 | adddd(&POSD(stn2), &POSD(stn2), &e); |
---|
746 | } |
---|
747 | fix(stn2); |
---|
748 | add_stn_to_list(&stnlist, stn2); |
---|
749 | osfree(leg); |
---|
750 | stn[i]->leg[dirn[i]] = legs[i]; |
---|
751 | /* transfer the articulation status of the radial legs */ |
---|
752 | if (stnZ->leg[i]->l.reverse & FLAG_ARTICULATION) { |
---|
753 | legs[i]->l.reverse |= FLAG_ARTICULATION; |
---|
754 | reverse_leg(legs[i])->l.reverse |= FLAG_ARTICULATION; |
---|
755 | } |
---|
756 | osfree(stnZ->leg[i]); |
---|
757 | stnZ->leg[i] = NULL; |
---|
758 | } |
---|
759 | /*printf("---%f %f %f\n",POS(stnZ, 0), POS(stnZ, 1), POS(stnZ, 2));*/ |
---|
760 | remove_stn_from_list(&stnlist, stnZ); |
---|
761 | osfree(stnZ->name); |
---|
762 | osfree(stnZ); |
---|
763 | } else { |
---|
764 | BUG("ptrRed has unknown type"); |
---|
765 | } |
---|
766 | |
---|
767 | ptrOld = ptrRed; |
---|
768 | ptrRed = ptrRed->next; |
---|
769 | osfree(ptrOld); |
---|
770 | } |
---|
771 | } |
---|