1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15/* TODO:
16 * In dot, prefer bottom or top routing
17 * In general, prefer closest side to closest side routing.
18 * Edge labels
19 * Ports/compass points
20 * ordering attribute
21 * Weights on edges in nodes
22 * Edge concentrators?
23 */
24
25#include "config.h"
26
27#define DEBUG
28#include <stddef.h>
29#include <setjmp.h>
30#include <maze.h>
31#include "fPQ.h"
32#include "memory.h"
33#include "geomprocs.h"
34#include "globals.h"
35#include "render.h"
36#include "pointset.h"
37typedef struct {
38 int d;
39 Agedge_t* e;
40} epair_t;
41
42static jmp_buf jbuf;
43
44#ifdef DEBUG
45static void emitSearchGraph (FILE* fp, sgraph* sg);
46static void emitGraph (FILE* fp, maze* mp, int n_edges, route* route_list, epair_t[]);
47int odb_flags;
48#endif
49
50#define CELL(n) ((cell*)ND_alg(n))
51#define MID(a,b) (((a)+(b))/2.0)
52#define SC 1
53
54/* cellOf:
55 * Given 2 snodes sharing a cell, return the cell.
56 */
57static cell*
58cellOf (snode* p, snode* q)
59{
60 cell* cp = p->cells[0];
61 if ((cp == q->cells[0]) || (cp == q->cells[1])) return cp;
62 else return p->cells[1];
63}
64
65static pointf
66midPt (cell* cp)
67{
68 pointf p;
69 p.x = MID(cp->bb.LL.x,cp->bb.UR.x);
70 p.y = MID(cp->bb.LL.y,cp->bb.UR.y);
71 return p;
72}
73
74/* sidePt:
75 * Given a cell and an snode on one of its sides, return the
76 * midpoint of the side.
77 */
78static pointf
79sidePt (snode* ptr, cell* cp)
80{
81 pointf pt;
82 if (cp == ptr->cells[1]) {
83 if (ptr->isVert) {
84 pt.x = cp->bb.LL.x;
85 pt.y = MID(cp->bb.LL.y,cp->bb.UR.y);
86 }
87 else {
88 pt.x = MID(cp->bb.LL.x,cp->bb.UR.x);
89 pt.y = cp->bb.LL.y;
90 }
91 }
92 else {
93 if (ptr->isVert) {
94 pt.x = cp->bb.UR.x;
95 pt.y = MID(cp->bb.LL.y,cp->bb.UR.y);
96 }
97 else {
98 pt.x = MID(cp->bb.LL.x,cp->bb.UR.x);
99 pt.y = cp->bb.UR.y;
100 }
101 }
102 return pt;
103}
104
105/* setSet:
106 * Initialize and normalize segments.
107 * p1 stores smaller value
108 * Assume b1 != b2
109 */
110static void
111setSeg (segment* sp, int dir, double fix, double b1, double b2, int l1, int l2)
112{
113 sp->isVert = dir;
114 sp->comm_coord = fix;
115 if (b1 < b2) {
116 sp->p.p1 = b1;
117 sp->p.p2 = b2;
118 sp->l1 = l1;
119 sp->l2 = l2;
120 sp->flipped = 0;
121 }
122 else {
123 sp->p.p2 = b1;
124 sp->p.p1 = b2;
125 sp->l2 = l1;
126 sp->l1 = l2;
127 sp->flipped = 1;
128 }
129}
130
131/* Convert route in shortest path graph to route
132 * of segments. This records the first and last cells,
133 * plus cells where the path bends.
134 * Note that the shortest path will always have at least 4 nodes:
135 * the two dummy nodes representing the center of the two real nodes,
136 * and the two nodes on the boundary of the two real nodes.
137 */
138#define PUSH(rte,P) (rte.p[rte.n++] = P)
139
140static route
141convertSPtoRoute (sgraph* g, snode* fst, snode* lst)
142{
143 route rte;
144 snode* ptr;
145 snode* next;
146 snode* prev; /* node in shortest path just previous to next */
147 int i, sz = 0;
148 cell* cp;
149 cell* ncp;
150 segment seg;
151 double fix, b1, b2;
152 int l1, l2;
153 pointf bp1, bp2, prevbp = {0.0,0.0}; /* bend points */
154
155 /* count no. of nodes in shortest path */
156 for (ptr = fst; ptr; ptr = N_DAD(ptr)) sz++;
157 rte.n = 0;
158 rte.segs = N_NEW(sz-2, segment); /* at most sz-2 segments */
159
160 seg.prev = seg.next = 0;
161 ptr = prev = N_DAD(fst);
162 next = N_DAD(ptr);
163 if (IsNode(ptr->cells[0]))
164 cp = ptr->cells[1];
165 else
166 cp = ptr->cells[0];
167 bp1 = sidePt (ptr, cp);
168 while (N_DAD(next)!=NULL) {
169 ncp = cellOf (prev, next);
170 updateWts (g, ncp, N_EDGE(ptr));
171
172 /* add seg if path bends or at end */
173 if ((ptr->isVert != next->isVert) || (N_DAD(next) == lst)) {
174 if (ptr->isVert != next->isVert)
175 bp2 = midPt (ncp);
176 else
177 bp2 = sidePt(next, ncp);
178 if (ptr->isVert) { /* horizontal segment */
179 if (ptr == N_DAD(fst)) l1 = B_NODE;
180 else if (prevbp.y > bp1.y) l1 = B_UP;
181 else l1 = B_DOWN;
182 if (ptr->isVert != next->isVert) {
183 if (next->cells[0] == ncp) l2 = B_UP;
184 else l2 = B_DOWN;
185 }
186 else l2 = B_NODE;
187 fix = cp->bb.LL.y;
188 b1 = cp->bb.LL.x;
189 b2 = ncp->bb.LL.x;
190 }
191 else { /* vertical segment */
192 if (ptr == N_DAD(fst)) l1 = B_NODE;
193 else if (prevbp.x > bp1.x) l1 = B_RIGHT;
194 else l1 = B_LEFT;
195 if (ptr->isVert != next->isVert) {
196 if (next->cells[0] == ncp) l2 = B_RIGHT;
197 else l2 = B_LEFT;
198 }
199 else l2 = B_NODE;
200 fix = cp->bb.LL.x;
201 b1 = cp->bb.LL.y;
202 b2 = ncp->bb.LL.y;
203 }
204 setSeg (&seg, !ptr->isVert, fix, b1, b2, l1, l2);
205 rte.segs[rte.n++] = seg;
206 cp = ncp;
207 prevbp = bp1;
208 bp1 = bp2;
209 if ((ptr->isVert != next->isVert) && (N_DAD(next) == lst)) {
210 bp2 = sidePt(next, ncp);
211 l2 = B_NODE;
212 if (next->isVert) { /* horizontal segment */
213 if (prevbp.y > bp1.y) l1 = B_UP;
214 else l1 = B_DOWN;
215 fix = cp->bb.LL.y;
216 b1 = cp->bb.LL.x;
217 b2 = ncp->bb.LL.x;
218 }
219 else {
220 if (prevbp.x > bp1.x) l1 = B_RIGHT;
221 else l1 = B_LEFT;
222 fix = cp->bb.LL.x;
223 b1 = cp->bb.LL.y;
224 b2 = ncp->bb.LL.y;
225 }
226 setSeg (&seg, !next->isVert, fix, b1, b2, l1, l2);
227 rte.segs[rte.n++] = seg;
228 }
229 ptr = next;
230 }
231 prev = next;
232 next = N_DAD(next);
233 }
234
235 rte.segs = realloc (rte.segs, rte.n*sizeof(segment));
236 for (i=0; i<rte.n; i++) {
237 if (i > 0)
238 rte.segs[i].prev = rte.segs + (i-1);
239 if (i < rte.n-1)
240 rte.segs[i].next = rte.segs + (i+1);
241 }
242
243 return rte;
244}
245
246typedef struct {
247 Dtlink_t link;
248 double v;
249 Dt_t* chans;
250} chanItem;
251
252static void
253freeChannel (Dt_t* d, channel* cp, Dtdisc_t* disc)
254{
255 free_graph (cp->G);
256 free (cp->seg_list);
257 free (cp);
258}
259
260static void
261freeChanItem (Dt_t* d, chanItem* cp, Dtdisc_t* disc)
262{
263 dtclose (cp->chans);
264 free (cp);
265}
266
267/* chancmpid:
268 * Compare intervals. Two intervals are equal if one contains
269 * the other. Otherwise, the one with the smaller p1 value is
270 * less.
271 * This combines two separate functions into one. Channels are
272 * disjoint, so we really only need to key on p1.
273 * When searching for a channel containing a segment, we rely on
274 * interval containment to return the correct channel.
275 */
276static int
277chancmpid(Dt_t* d, paird* key1, paird* key2, Dtdisc_t* disc)
278{
279 if (key1->p1 > key2->p1) {
280 if (key1->p2 <= key2->p2) return 0;
281 else return 1;
282 }
283 else if (key1->p1 < key2->p1) {
284 if (key1->p2 >= key2->p2) return 0;
285 else return -1;
286 }
287 else return 0;
288}
289
290static int
291dcmpid(Dt_t* d, double* key1, double* key2, Dtdisc_t* disc)
292{
293 if (*key1 > *key2) return 1;
294 else if (*key1 < *key2) return -1;
295 else return 0;
296}
297
298static Dtdisc_t chanDisc = {
299 offsetof(channel,p),
300 sizeof(paird),
301 offsetof(channel,link),
302 0,
303 (Dtfree_f)freeChannel,
304 (Dtcompar_f)chancmpid,
305 0,
306 0,
307 0
308};
309
310static Dtdisc_t chanItemDisc = {
311 offsetof(chanItem,v),
312 sizeof(double),
313 offsetof(chanItem,link),
314 0,
315 (Dtfree_f)freeChanItem,
316 (Dtcompar_f)dcmpid,
317 0,
318 0,
319 0
320};
321
322static void
323addChan (Dt_t* chdict, channel* cp, double j)
324{
325 chanItem* subd = dtmatch (chdict, &j);
326
327 if (!subd) {
328 subd = NEW (chanItem);
329 subd->v = j;
330 subd->chans = dtopen (&chanDisc, Dtoset);
331 dtinsert (chdict, subd);
332 }
333 dtinsert (subd->chans, cp);
334}
335
336static Dt_t*
337extractHChans (maze* mp)
338{
339 int i;
340 snode* np;
341 Dt_t* hchans = dtopen (&chanItemDisc, Dtoset);
342
343 for (i = 0; i < mp->ncells; i++) {
344 channel* chp;
345 cell* cp = mp->cells+i;
346 cell* nextcp;
347 if (IsHScan(cp)) continue;
348
349 /* move left */
350 while ((np = cp->sides[M_LEFT]) && (nextcp = np->cells[0]) &&
351 !IsNode(nextcp)) {
352 cp = nextcp;
353 }
354
355 chp = NEW(channel);
356 chp->cp = cp;
357 chp->p.p1 = cp->bb.LL.x;
358
359 /* move right */
360 cp->flags |= MZ_HSCAN;
361 while ((np = cp->sides[M_RIGHT]) && (nextcp = np->cells[1]) &&
362 !IsNode(nextcp)) {
363 cp = nextcp;
364 cp->flags |= MZ_HSCAN;
365 }
366
367 chp->p.p2 = cp->bb.UR.x;
368 addChan (hchans, chp, chp->cp->bb.LL.y);
369 }
370 return hchans;
371}
372
373static Dt_t*
374extractVChans (maze* mp)
375{
376 int i;
377 snode* np;
378 Dt_t* vchans = dtopen (&chanItemDisc, Dtoset);
379
380 for (i = 0; i < mp->ncells; i++) {
381 channel* chp;
382 cell* cp = mp->cells+i;
383 cell* nextcp;
384 if (IsVScan(cp)) continue;
385
386 /* move down */
387 while ((np = cp->sides[M_BOTTOM]) && (nextcp = np->cells[0]) &&
388 !IsNode(nextcp)) {
389 cp = nextcp;
390 }
391
392 chp = NEW(channel);
393 chp->cp = cp;
394 chp->p.p1 = cp->bb.LL.y;
395
396 /* move up */
397 cp->flags |= MZ_VSCAN;
398 while ((np = cp->sides[M_TOP]) && (nextcp = np->cells[1]) &&
399 !IsNode(nextcp)) {
400 cp = nextcp;
401 cp->flags |= MZ_VSCAN;
402 }
403
404 chp->p.p2 = cp->bb.UR.y;
405 addChan (vchans, chp, chp->cp->bb.LL.x);
406 }
407 return vchans;
408}
409
410static void
411insertChan (channel* chan, segment* seg)
412{
413 seg->ind_no = chan->cnt++;
414 chan->seg_list = ALLOC(chan->cnt, chan->seg_list, segment*);
415 chan->seg_list[chan->cnt-1] = seg;
416}
417
418static channel*
419chanSearch (Dt_t* chans, segment* seg)
420{
421 channel* cp;
422 chanItem* chani = dtmatch (chans, &seg->comm_coord);
423 assert (chani);
424 cp = dtmatch (chani->chans, &seg->p);
425 assert (cp);
426 return cp;
427}
428
429static void
430assignSegs (int nrtes, route* route_list, maze* mp)
431{
432 channel* chan;
433 int i, j;
434
435 for (i=0;i<nrtes;i++) {
436 route rte = route_list[i];
437 for (j=0;j<rte.n;j++) {
438 segment* seg = rte.segs+j;
439 if (seg->isVert)
440 chan = chanSearch(mp->vchans, seg);
441 else
442 chan = chanSearch(mp->hchans, seg);
443 insertChan (chan, seg);
444 }
445 }
446}
447
448/* addLoop:
449 * Add two temporary nodes to sgraph corresponding to two ends of a loop at cell cp, i
450 * represented by dp and sp.
451 */
452static void
453addLoop (sgraph* sg, cell* cp, snode* dp, snode* sp)
454{
455 int i;
456 int onTop;
457 pointf midp = midPt (cp);
458
459 for (i = 0; i < cp->nsides; i++) {
460 cell* ocp;
461 pointf p;
462 double wt;
463 snode* onp = cp->sides[i];
464
465 if (onp->isVert) continue;
466 if (onp->cells[0] == cp) {
467 onTop = 1;
468 ocp = onp->cells[1];
469 }
470 else {
471 onTop = 0;
472 ocp = onp->cells[0];
473 }
474 p = sidePt (onp, ocp);
475 wt = fabs(p.x - midp.x) + fabs(p.y - midp.y);
476 if (onTop)
477 createSEdge (sg, sp, onp, 0); /* FIX weight */
478 else
479 createSEdge (sg, dp, onp, 0); /* FIX weight */
480 }
481 sg->nnodes += 2;
482}
483
484/* addNodeEdges:
485 * Add temporary node to sgraph corresponding to cell cp, represented
486 * by np.
487 */
488static void
489addNodeEdges (sgraph* sg, cell* cp, snode* np)
490{
491 int i;
492 pointf midp = midPt (cp);
493
494 for (i = 0; i < cp->nsides; i++) {
495 snode* onp = cp->sides[i];
496 cell* ocp;
497 pointf p;
498 double wt;
499
500 if (onp->cells[0] == cp)
501 ocp = onp->cells[1];
502 else
503 ocp = onp->cells[0];
504 p = sidePt (onp, ocp);
505 wt = fabs(p.x - midp.x) + fabs(p.y - midp.y);
506 createSEdge (sg, np, onp, 0); /* FIX weight */
507 }
508 sg->nnodes++;
509#ifdef DEBUG
510 np->cells[0] = np->cells[1] = cp;
511#endif
512}
513
514#ifdef DEBUG
515
516#include <intset.h>
517static char* bendToStr (bend b)
518{
519 char* s = NULL;
520 switch (b) {
521 case B_NODE :
522 s = "B_NODE";
523 break;
524 case B_UP :
525 s = "B_UP";
526 break;
527 case B_LEFT :
528 s = "B_LEFT";
529 break;
530 case B_DOWN :
531 s = "B_DOWN";
532 break;
533 case B_RIGHT :
534 s = "B_RIGHT";
535 break;
536 }
537 return s;
538}
539
540static void putSeg (FILE* fp, segment* seg)
541{
542 if (seg->isVert)
543 fprintf (fp, "((%f,%f),(%f,%f)) %s %s", seg->comm_coord, seg->p.p1,
544 seg->comm_coord, seg->p.p2, bendToStr (seg->l1), bendToStr (seg->l2));
545 else
546 fprintf (fp, "((%f,%f),(%f,%f)) %s %s", seg->p.p1,seg->comm_coord,
547 seg->p.p2, seg->comm_coord, bendToStr (seg->l1), bendToStr (seg->l2));
548}
549
550static void
551dumpChanG (channel* cp, int v)
552{
553 int k;
554 intitem* ip;
555 Dt_t* adj;
556
557 if (cp->cnt < 2) return;
558 fprintf (stderr, "channel %d (%f,%f)\n", v, cp->p.p1, cp->p.p2);
559 for (k=0;k<cp->cnt;k++) {
560 adj = cp->G->vertices[k].adj_list;
561 if (dtsize(adj) == 0) continue;
562 putSeg (stderr, cp->seg_list[k]);
563 fputs (" ->\n", stderr);
564 for (ip = (intitem*)dtfirst(adj); ip; ip = (intitem*)dtnext(adj, ip)) {
565 fputs (" ", stderr);
566 putSeg (stderr, cp->seg_list[ip->id]);
567 fputs ("\n", stderr);
568 }
569 }
570}
571#endif
572
573static void
574assignTrackNo (Dt_t* chans)
575{
576 Dt_t* lp;
577 Dtlink_t* l1;
578 Dtlink_t* l2;
579 channel* cp;
580 int k;
581
582 for (l1 = dtflatten (chans); l1; l1 = dtlink(chans,l1)) {
583 lp = ((chanItem*)l1)->chans;
584 for (l2 = dtflatten (lp); l2; l2 = dtlink(lp,l2)) {
585 cp = (channel*)l2;
586 if (cp->cnt) {
587#ifdef DEBUG
588 if (odb_flags & ODB_CHANG) dumpChanG (cp, ((chanItem*)l1)->v);
589#endif
590 top_sort (cp->G);
591 for (k=0;k<cp->cnt;k++)
592 cp->seg_list[k]->track_no = cp->G->vertices[k].topsort_order+1;
593 }
594 }
595 }
596}
597
598static void
599create_graphs(Dt_t* chans)
600{
601 Dt_t* lp;
602 Dtlink_t* l1;
603 Dtlink_t* l2;
604 channel* cp;
605
606 for (l1 = dtflatten (chans); l1; l1 = dtlink(chans,l1)) {
607 lp = ((chanItem*)l1)->chans;
608 for (l2 = dtflatten (lp); l2; l2 = dtlink(lp,l2)) {
609 cp = (channel*)l2;
610 cp->G = make_graph (cp->cnt);
611 }
612 }
613}
614
615static int
616eqEndSeg (bend S1l2, bend S2l2, bend T1, bend T2)
617{
618 if (((S1l2==T2)&&(S2l2=!T2))
619 || ((S1l2==B_NODE)&&(S2l2==T1)))
620 return(0);
621 else
622 return(-1);
623}
624
625static int
626overlapSeg (segment* S1, segment* S2, bend T1, bend T2)
627{
628 if(S1->p.p2<S2->p.p2) {
629 if(S1->l2==T1&&S2->l1==T2) return(-1);
630 else if(S1->l2==T2&&S2->l1==T1) return(1);
631 else return(0);
632 }
633 else if(S1->p.p2==S2->p.p2) {
634 if(S2->l1==T2) return eqEndSeg (S1->l2, S2->l2, T1, T2);
635 else return -1*eqEndSeg (S2->l2, S1->l2, T1, T2);
636 }
637 else { /* S1->p.p2>S2->p.p2 */
638 if(S2->l1==T2&&S2->l2==T2) return(-1);
639 else if (S2->l1==T1&&S2->l2==T1) return(1);
640 else return(0);
641 }
642}
643
644static int
645ellSeg (bend S1l1, bend S1l2, bend T)
646{
647 if (S1l1 == T) {
648 if (S1l2== T) return -1;
649 else return 0;
650 }
651 else return 1;
652}
653
654static int
655segCmp (segment* S1, segment* S2, bend T1, bend T2)
656{
657 /* no overlap */
658 if((S1->p.p2<S2->p.p1)||(S1->p.p1>S2->p.p2)) return(0);
659 /* left endpoint of S2 inside S1 */
660 if(S1->p.p1<S2->p.p1&&S2->p.p1<S1->p.p2)
661 return overlapSeg (S1, S2, T1, T2);
662 /* left endpoint of S1 inside S2 */
663 else if(S2->p.p1<S1->p.p1&&S1->p.p1<S2->p.p2)
664 return -1*overlapSeg (S2, S1, T1, T2);
665 else if(S1->p.p1==S2->p.p1) {
666 if(S1->p.p2==S2->p.p2) {
667 if((S1->l1==S2->l1)&&(S1->l2==S2->l2))
668 return(0);
669 else if (S2->l1==S2->l2) {
670 if(S2->l1==T1) return(1);
671 else if(S2->l1==T2) return(-1);
672 else if ((S1->l1!=T1)&&(S1->l2!=T1)) return (1);
673 else if ((S1->l1!=T2)&&(S1->l2!=T2)) return (-1);
674 else return 0;
675 }
676 else if ((S2->l1==T1)&&(S2->l2==T2)) {
677 if ((S1->l1!=T1)&&(S1->l2==T2)) return 1;
678 else if ((S1->l1==T1)&&(S1->l2!=T2)) return -1;
679 else return 0;
680 }
681 else if ((S2->l2==T1)&&(S2->l1==T2)) {
682 if ((S1->l2!=T1)&&(S1->l1==T2)) return 1;
683 else if ((S1->l2==T1)&&(S1->l1!=T2)) return -1;
684 else return 0;
685 }
686 else if ((S2->l1==B_NODE)&&(S2->l2==T1)) {
687 return ellSeg (S1->l1, S1->l2, T1);
688 }
689 else if ((S2->l1==B_NODE)&&(S2->l2==T2)) {
690 return -1*ellSeg (S1->l1, S1->l2, T2);
691 }
692 else if ((S2->l1==T1)&&(S2->l2==B_NODE)) {
693 return ellSeg (S1->l2, S1->l1, T1);
694 }
695 else { /* ((S2->l1==T2)&&(S2->l2==B_NODE)) */
696 return -1*ellSeg (S1->l2, S1->l1, T2);
697 }
698 }
699 else if(S1->p.p2<S2->p.p2) {
700 if(S1->l2==T1)
701 return eqEndSeg (S2->l1, S1->l1, T1, T2);
702 else
703 return -1*eqEndSeg (S2->l1, S1->l1, T1, T2);
704 }
705 else { /* S1->p.p2>S2->p.p2 */
706 if(S2->l2==T2)
707 return eqEndSeg (S1->l1, S2->l1, T1, T2);
708 else
709 return -1*eqEndSeg (S1->l1, S2->l1, T1, T2);
710 }
711 }
712 else if(S1->p.p2==S2->p.p1) {
713 if(S1->l2==S2->l1) return(0);
714 else if(S1->l2==T2) return(1);
715 else return(-1);
716 }
717 else { /* S1->p.p1==S2->p.p2 */
718 if(S1->l1==S2->l2) return(0);
719 else if(S1->l1==T2) return(1);
720 else return(-1);
721 }
722 assert(0);
723 return 0;
724}
725
726/* Function seg_cmp returns
727 * -1 if S1 HAS TO BE to the right/below S2 to avoid a crossing,
728 * 0 if a crossing is unavoidable or there is no crossing at all or
729 * the segments are parallel,
730 * 1 if S1 HAS TO BE to the left/above S2 to avoid a crossing
731 *
732 * Note: This definition means horizontal segments have track numbers
733 * increasing as y decreases, while vertical segments have track numbers
734 * increasing as x increases. It would be good to make this consistent,
735 * with horizontal track numbers increasing with y. This can be done by
736 * switching B_DOWN and B_UP in the first call to segCmp. At present,
737 * though, I'm not sure what assumptions are made in handling parallel
738 * segments, so we leave the code alone for the time being.
739 */
740static int
741seg_cmp(segment* S1, segment* S2)
742{
743 if(S1->isVert!=S2->isVert||S1->comm_coord!=S2->comm_coord) {
744 agerr (AGERR, "incomparable segments !! -- Aborting\n");
745 longjmp(jbuf, 1);
746 }
747 if(S1->isVert)
748 return segCmp (S1, S2, B_RIGHT, B_LEFT);
749 else
750 return segCmp (S1, S2, B_DOWN, B_UP);
751}
752
753static void
754add_edges_in_G(channel* cp)
755{
756 int x,y;
757 segment** seg_list = cp->seg_list;
758 int size = cp->cnt;
759 rawgraph* G = cp->G;
760
761 for(x=0;x+1<size;x++) {
762 for(y=x+1;y<size;y++) {
763 switch (seg_cmp(seg_list[x],seg_list[y])) {
764 case 1:
765 insert_edge(G,x,y);
766 break;
767 case 0:
768 break;
769 case -1:
770 insert_edge(G,y,x);
771 break;
772 }
773 }
774 }
775}
776
777static void
778add_np_edges (Dt_t* chans)
779{
780 Dt_t* lp;
781 Dtlink_t* l1;
782 Dtlink_t* l2;
783 channel* cp;
784
785 for (l1 = dtflatten (chans); l1; l1 = dtlink(chans,l1)) {
786 lp = ((chanItem*)l1)->chans;
787 for (l2 = dtflatten (lp); l2; l2 = dtlink(lp,l2)) {
788 cp = (channel*)l2;
789 if (cp->cnt)
790 add_edges_in_G(cp);
791 }
792 }
793}
794
795static segment*
796next_seg(segment* seg, int dir)
797{
798 assert(seg);
799 if (!dir)
800 return(seg->prev);
801 else
802 return(seg->next);
803}
804
805/* propagate_prec propagates the precedence relationship along
806 * a series of parallel segments on 2 edges
807 */
808static int
809propagate_prec(segment* seg, int prec, int hops, int dir)
810{
811 int x;
812 int ans=prec;
813 segment* next;
814 segment* current;
815
816 current = seg;
817 for(x=1;x<=hops;x++) {
818 next = next_seg(current, dir);
819 if(!current->isVert) {
820 if(next->comm_coord==current->p.p1) {
821 if(current->l1==B_UP) ans *= -1;
822 }
823 else {
824 if(current->l2==B_DOWN) ans *= -1;
825 }
826 }
827 else {
828 if(next->comm_coord==current->p.p1) {
829 if(current->l1==B_RIGHT) ans *= -1;
830 }
831 else {
832 if(current->l2==B_LEFT) ans *= -1;
833 }
834 }
835 current = next;
836 }
837 return(ans);
838}
839
840static int
841is_parallel(segment* s1, segment* s2)
842{
843 assert (s1->comm_coord==s2->comm_coord);
844 return ((s1->p.p1==s2->p.p1)&&
845 (s1->p.p2==s2->p.p2)&&
846 (s1->l1==s2->l1)&&
847 (s1->l2==s2->l2));
848}
849
850/* decide_point returns the number of hops needed in the given directions
851 * along the 2 edges to get to a deciding point (or NODES) and also puts
852 * into prec the appropriate dependency (follows same convention as seg_cmp)
853 */
854static pair
855decide_point(segment* si, segment* sj, int dir1, int dir2)
856{
857 int prec, ans = 0, temp;
858 pair ret;
859 segment* np1;
860 segment* np2;
861
862 while ((np1 = next_seg(si,dir1)) && (np2 = next_seg(sj,dir2)) &&
863 is_parallel(np1, np2)) {
864 ans++;
865 si = np1;
866 sj = np2;
867 }
868 if (!np1)
869 prec = 0;
870 else if (!np2)
871 assert(0); /* FIXME */
872 else {
873 temp = seg_cmp(np1, np2);
874 prec = propagate_prec(np1, temp, ans+1, 1-dir1);
875 }
876
877 ret.a = ans;
878 ret.b = prec;
879 return(ret);
880}
881
882/* sets the edges for a series of parallel segments along two edges starting
883 * from segment i, segment j. It is assumed that the edge should be from
884 * segment i to segment j - the dependency is appropriately propagated
885 */
886static void
887set_parallel_edges (segment* seg1, segment* seg2, int dir1, int dir2, int hops,
888 maze* mp)
889{
890 int x;
891 channel* chan;
892 channel* nchan;
893 segment* prev1;
894 segment* prev2;
895
896 if (seg1->isVert)
897 chan = chanSearch(mp->vchans, seg1);
898 else
899 chan = chanSearch(mp->hchans, seg1);
900 insert_edge(chan->G, seg1->ind_no, seg2->ind_no);
901
902 for (x=1;x<=hops;x++) {
903 prev1 = next_seg(seg1, dir1);
904 prev2 = next_seg(seg2, dir2);
905 if(!seg1->isVert) {
906 nchan = chanSearch(mp->vchans, prev1);
907 if(prev1->comm_coord==seg1->p.p1) {
908 if(seg1->l1==B_UP) {
909 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
910 insert_edge(nchan->G, prev2->ind_no, prev1->ind_no);
911 else
912 insert_edge(nchan->G, prev1->ind_no, prev2->ind_no);
913 }
914 else {
915 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
916 insert_edge(nchan->G, prev1->ind_no, prev2->ind_no);
917 else
918 insert_edge(nchan->G, prev2->ind_no, prev1->ind_no);
919 }
920 }
921 else {
922 if(seg1->l2==B_UP) {
923 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
924 insert_edge(nchan->G,prev1->ind_no, prev2->ind_no);
925 else
926 insert_edge(nchan->G,prev2->ind_no, prev1->ind_no);
927 }
928 else {
929 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
930 insert_edge(nchan->G, prev2->ind_no, prev1->ind_no);
931 else
932 insert_edge(nchan->G, prev1->ind_no, prev2->ind_no);
933 }
934 }
935 }
936 else {
937 nchan = chanSearch(mp->hchans, prev1);
938 if(prev1->comm_coord==seg1->p.p1) {
939 if(seg1->l1==B_LEFT) {
940 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
941 insert_edge(nchan->G, prev1->ind_no, prev2->ind_no);
942 else
943 insert_edge(nchan->G, prev2->ind_no, prev1->ind_no);
944 }
945 else {
946 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
947 insert_edge(nchan->G, prev2->ind_no, prev1->ind_no);
948 else
949 insert_edge(nchan->G, prev1->ind_no, prev2->ind_no);
950 }
951 }
952 else {
953 if(seg1->l2==B_LEFT) {
954 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
955 insert_edge(nchan->G, prev2->ind_no, prev1->ind_no);
956 else
957 insert_edge(nchan->G, prev1->ind_no, prev2->ind_no);
958 }
959 else {
960 if(edge_exists(chan->G, seg1->ind_no, seg2->ind_no))
961 insert_edge(nchan->G, prev1->ind_no, prev2->ind_no);
962 else
963 insert_edge(nchan->G, prev2->ind_no, prev1->ind_no);
964 }
965 }
966 }
967 chan = nchan;
968 seg1 = prev1;
969 seg2 = prev2;
970 }
971}
972
973/* removes the edge between segments after the resolution of a conflict
974 */
975static void
976removeEdge(segment* seg1, segment* seg2, int dir, maze* mp)
977{
978 segment* ptr1;
979 segment* ptr2;
980 channel* chan;
981
982 ptr1 = seg1;
983 ptr2 = seg2;
984 while(is_parallel(ptr1, ptr2)) {
985 ptr1 = next_seg(ptr1, 1);
986 ptr2 = next_seg(ptr2, dir);
987 }
988 if(ptr1->isVert)
989 chan = chanSearch(mp->vchans, ptr1);
990 else
991 chan = chanSearch(mp->hchans, ptr1);
992 remove_redge (chan->G, ptr1->ind_no, ptr2->ind_no);
993}
994
995static void
996addPEdges (channel* cp, maze* mp)
997{
998 int i,j;
999 /* dir[1,2] are used to figure out whether we should use prev
1000 * pointers or next pointers -- 0 : decrease, 1 : increase
1001 */
1002 int dir;
1003 /* number of hops along the route to get to the deciding points */
1004 pair hops;
1005 /* precedences of the deciding points : same convention as
1006 * seg_cmp function
1007 */
1008 int prec1, prec2;
1009 pair p;
1010 rawgraph* G = cp->G;
1011 segment** segs = cp->seg_list;
1012
1013 for(i=0;i+1<cp->cnt;i++) {
1014 for(j=i+1;j<cp->cnt;j++) {
1015 if (!edge_exists(G,i,j) && !edge_exists(G,j,i)) {
1016 if (is_parallel(segs[i], segs[j])) {
1017 /* get_directions */
1018 if(segs[i]->prev==0) {
1019 if(segs[j]->prev==0)
1020 dir = 0;
1021 else
1022 dir = 1;
1023 }
1024 else if(segs[j]->prev==0) {
1025 dir = 1;
1026 }
1027 else {
1028 if(segs[i]->prev->comm_coord==segs[j]->prev->comm_coord)
1029 dir = 0;
1030 else
1031 dir = 1;
1032 }
1033
1034 p = decide_point(segs[i], segs[j], 0, dir);
1035 hops.a = p.a;
1036 prec1 = p.b;
1037 p = decide_point(segs[i], segs[j], 1, 1-dir);
1038 hops.b = p.a;
1039 prec2 = p.b;
1040
1041 switch(prec1) {
1042 case -1 :
1043 set_parallel_edges (segs[j], segs[i], dir, 0, hops.a, mp);
1044 set_parallel_edges (segs[j], segs[i], 1-dir, 1, hops.b, mp);
1045 if(prec2==1)
1046 removeEdge (segs[i], segs[j], 1-dir, mp);
1047 break;
1048 case 0 :
1049 switch(prec2) {
1050 case -1:
1051 set_parallel_edges (segs[j], segs[i], dir, 0, hops.a, mp);
1052 set_parallel_edges (segs[j], segs[i], 1-dir, 1, hops.b, mp);
1053 break;
1054 case 0 :
1055 set_parallel_edges (segs[i], segs[j], 0, dir, hops.a, mp);
1056 set_parallel_edges (segs[i], segs[j], 1, 1-dir, hops.b, mp);
1057 break;
1058 case 1:
1059 set_parallel_edges (segs[i], segs[j], 0, dir, hops.a, mp);
1060 set_parallel_edges (segs[i], segs[j], 1, 1-dir, hops.b, mp);
1061 break;
1062 }
1063 break;
1064 case 1 :
1065 set_parallel_edges (segs[i], segs[j], 0, dir, hops.a, mp);
1066 set_parallel_edges (segs[i], segs[j], 1, 1-dir, hops.b, mp);
1067 if(prec2==-1)
1068 removeEdge (segs[i], segs[j], 1-dir, mp);
1069 break;
1070 }
1071 }
1072 }
1073 }
1074 }
1075}
1076
1077static void
1078add_p_edges (Dt_t* chans, maze* mp)
1079{
1080 Dt_t* lp;
1081 Dtlink_t* l1;
1082 Dtlink_t* l2;
1083
1084 for (l1 = dtflatten (chans); l1; l1 = dtlink(chans,l1)) {
1085 lp = ((chanItem*)l1)->chans;
1086 for (l2 = dtflatten (lp); l2; l2 = dtlink(lp,l2)) {
1087 addPEdges ((channel*)l2, mp);
1088 }
1089 }
1090}
1091
1092static void
1093assignTracks (int nrtes, route* route_list, maze* mp)
1094{
1095 /* Create the graphs for each channel */
1096 create_graphs(mp->hchans);
1097 create_graphs(mp->vchans);
1098
1099 /* add edges between non-parallel segments */
1100 add_np_edges(mp->hchans);
1101 add_np_edges(mp->vchans);
1102
1103 /* add edges between parallel segments + remove appropriate edges */
1104 add_p_edges(mp->hchans, mp);
1105 add_p_edges(mp->vchans, mp);
1106
1107 /* Assign the tracks after a top sort */
1108 assignTrackNo (mp->hchans);
1109 assignTrackNo (mp->vchans);
1110}
1111
1112static double
1113vtrack (segment* seg, maze* m)
1114{
1115 channel* chp = chanSearch(m->vchans, seg);
1116 double f = ((double)seg->track_no)/(chp->cnt+1);
1117 double left = chp->cp->bb.LL.x;
1118 double right = chp->cp->bb.UR.x;
1119 return left + f*(right-left);
1120}
1121
1122static int
1123htrack (segment* seg, maze* m)
1124{
1125 channel* chp = chanSearch(m->hchans, seg);
1126 double f = 1.0 - ((double)seg->track_no)/(chp->cnt+1);
1127 double lo = chp->cp->bb.LL.y;
1128 double hi = chp->cp->bb.UR.y;
1129 return lo + f*(hi-lo);
1130}
1131
1132static pointf
1133addPoints(pointf p0, pointf p1)
1134{
1135 p0.x += p1.x;
1136 p0.y += p1.y;
1137 return p0;
1138}
1139
1140static void
1141attachOrthoEdges (Agraph_t* g, maze* mp, int n_edges, route* route_list, splineInfo *sinfo, epair_t es[], int doLbls)
1142{
1143 int irte = 0;
1144 int i, ipt, npts;
1145 pointf* ispline = 0;
1146 int splsz = 0;
1147 pointf p, p1, q1;
1148 route rte;
1149 segment* seg;
1150 Agedge_t* e;
1151 textlabel_t* lbl;
1152
1153 for (; irte < n_edges; irte++) {
1154 e = es[irte].e;
1155 p1 = addPoints(ND_coord(agtail(e)), ED_tail_port(e).p);
1156 q1 = addPoints(ND_coord(aghead(e)), ED_head_port(e).p);
1157
1158 rte = route_list[irte];
1159 npts = 1 + 3*rte.n;
1160 if (npts > splsz) {
1161 if (ispline) free (ispline);
1162 ispline = N_GNEW(npts, pointf);
1163 splsz = npts;
1164 }
1165
1166 seg = rte.segs;
1167 if (seg->isVert) {
1168 p.x = vtrack(seg, mp);
1169 p.y = p1.y;
1170 }
1171 else {
1172 p.y = htrack(seg, mp);
1173 p.x = p1.x;
1174 }
1175 ispline[0] = ispline[1] = p;
1176 ipt = 2;
1177
1178 for (i = 1;i<rte.n;i++) {
1179 seg = rte.segs+i;
1180 if (seg->isVert)
1181 p.x = vtrack(seg, mp);
1182 else
1183 p.y = htrack(seg, mp);
1184 ispline[ipt+2] = ispline[ipt+1] = ispline[ipt] = p;
1185 ipt += 3;
1186 }
1187
1188 if (seg->isVert) {
1189 p.x = vtrack(seg, mp);
1190 p.y = q1.y;
1191 }
1192 else {
1193 p.y = htrack(seg, mp);
1194 p.x = q1.x;
1195 }
1196 ispline[ipt] = ispline[ipt+1] = p;
1197 if (Verbose > 1)
1198 fprintf(stderr, "ortho %s %s\n", agnameof(agtail(e)),agnameof(aghead(e)));
1199 clip_and_install(e, aghead(e), ispline, npts, sinfo);
1200 if (doLbls && (lbl = ED_label(e)) && !lbl->set)
1201 addEdgeLabels(g, e, p1, q1);
1202 }
1203 free(ispline);
1204}
1205
1206static int
1207edgeLen (Agedge_t* e)
1208{
1209 pointf p = ND_coord(agtail(e));
1210 pointf q = ND_coord(aghead(e));
1211 return (int)DIST2(p,q);
1212}
1213
1214static int edgecmp(epair_t* e0, epair_t* e1)
1215{
1216 return (e0->d - e1->d);
1217}
1218
1219static boolean spline_merge(node_t * n)
1220{
1221 return FALSE;
1222}
1223
1224static boolean swap_ends_p(edge_t * e)
1225{
1226 return FALSE;
1227}
1228
1229static splineInfo sinfo = { swap_ends_p, spline_merge, 1, 1 };
1230
1231/* orthoEdges:
1232 * For edges without position information, construct an orthogonal routing.
1233 * If doLbls is true, use edge label info when available to guide routing,
1234 * and set label pos for those edges for which this info is not available.
1235 */
1236void
1237orthoEdges (Agraph_t* g, int doLbls)
1238{
1239 sgraph* sg;
1240 maze* mp;
1241 int n_edges;
1242 route* route_list;
1243 int i, gstart;
1244 Agnode_t* n;
1245 Agedge_t* e;
1246 snode* sn;
1247 snode* dn;
1248 epair_t* es = N_GNEW(agnedges(g), epair_t);
1249 cell* start;
1250 cell* dest;
1251 PointSet* ps;
1252 textlabel_t* lbl;
1253
1254 if (Concentrate)
1255 ps = newPS();
1256
1257#ifdef DEBUG
1258 {
1259 char* s = agget(g, "odb");
1260 char c;
1261 odb_flags = 0;
1262 if (s && (*s != '\0')) {
1263 while ((c = *s++)) {
1264 switch (c) {
1265 case 'c' :
1266 odb_flags |= ODB_CHANG; // emit channel graph
1267 break;
1268 case 'i' :
1269 odb_flags |= (ODB_SGRAPH|ODB_IGRAPH); // emit search graphs
1270 break;
1271 case 'm' :
1272 odb_flags |= ODB_MAZE; // emit maze
1273 break;
1274 case 'r' :
1275 odb_flags |= ODB_ROUTE; // emit routes in maze
1276 break;
1277 case 's' :
1278 odb_flags |= ODB_SGRAPH; // emit search graph
1279 break;
1280 }
1281 }
1282 }
1283 }
1284#endif
1285 if (doLbls) {
1286 agerr(AGWARN, "Orthogonal edges do not currently handle edge labels. Try using xlabels.\n");
1287 doLbls = 0;
1288 }
1289 mp = mkMaze (g, doLbls);
1290 sg = mp->sg;
1291#ifdef DEBUG
1292 if (odb_flags & ODB_SGRAPH) emitSearchGraph (stderr, sg);
1293#endif
1294
1295 /* store edges to be routed in es, along with their lengths */
1296 n_edges = 0;
1297 for (n = agfstnode (g); n; n = agnxtnode(g, n)) {
1298 for (e = agfstout(g, n); e; e = agnxtout(g,e)) {
1299 if ((Nop == 2) && ED_spl(e)) continue;
1300 if (Concentrate) {
1301 int ti = AGSEQ(agtail(e));
1302 int hi = AGSEQ(aghead(e));
1303 if (ti <= hi) {
1304 if (isInPS (ps,ti,hi)) continue;
1305 else addPS (ps,ti,hi);
1306 }
1307 else {
1308 if (isInPS (ps,hi,ti)) continue;
1309 else addPS (ps,hi,ti);
1310 }
1311 }
1312 es[n_edges].e = e;
1313 es[n_edges].d = edgeLen (e);
1314 n_edges++;
1315 }
1316 }
1317
1318 route_list = N_NEW (n_edges, route);
1319
1320 qsort((char *)es, n_edges, sizeof(epair_t), (qsort_cmpf) edgecmp);
1321
1322 gstart = sg->nnodes;
1323 PQgen (sg->nnodes+2);
1324 sn = &sg->nodes[gstart];
1325 dn = &sg->nodes[gstart+1];
1326 for (i = 0; i < n_edges; i++) {
1327#ifdef DEBUG
1328 if ((i > 0) && (odb_flags & ODB_IGRAPH)) emitSearchGraph (stderr, sg);
1329#endif
1330 e = es[i].e;
1331 start = CELL(agtail(e));
1332 dest = CELL(aghead(e));
1333
1334 if (doLbls && (lbl = ED_label(e)) && lbl->set) {
1335 }
1336 else {
1337 if (start == dest)
1338 addLoop (sg, start, dn, sn);
1339 else {
1340 addNodeEdges (sg, dest, dn);
1341 addNodeEdges (sg, start, sn);
1342 }
1343 if (shortPath (sg, dn, sn)) goto orthofinish;
1344 }
1345
1346 route_list[i] = convertSPtoRoute(sg, sn, dn);
1347 reset (sg);
1348 }
1349 PQfree ();
1350
1351 mp->hchans = extractHChans (mp);
1352 mp->vchans = extractVChans (mp);
1353 assignSegs (n_edges, route_list, mp);
1354 if (setjmp(jbuf))
1355 goto orthofinish;
1356 assignTracks (n_edges, route_list, mp);
1357#ifdef DEBUG
1358 if (odb_flags & ODB_ROUTE) emitGraph (stderr, mp, n_edges, route_list, es);
1359#endif
1360 attachOrthoEdges (g, mp, n_edges, route_list, &sinfo, es, doLbls);
1361
1362orthofinish:
1363 if (Concentrate)
1364 freePS (ps);
1365
1366 for (i=0; i < n_edges; i++)
1367 free (route_list[i].segs);
1368 free (route_list);
1369 freeMaze (mp);
1370 free (es);
1371}
1372
1373#ifdef DEBUG
1374#include <arith.h>
1375/* #include <values.h> */
1376#define TRANS 10
1377
1378static char* prolog2 =
1379"%%!PS-Adobe-2.0\n\
1380%%%%BoundingBox: (atend)\n\
1381/point {\n\
1382 /Y exch def\n\
1383 /X exch def\n\
1384 newpath\n\
1385 X Y 3 0 360 arc fill\n\
1386} def\n\
1387/cell {\n\
1388 /Y exch def\n\
1389 /X exch def\n\
1390 /y exch def\n\
1391 /x exch def\n\
1392 newpath\n\
1393 x y moveto\n\
1394 x Y lineto\n\
1395 X Y lineto\n\
1396 X y lineto\n\
1397 closepath stroke\n\
1398} def\n\
1399/node {\n\
1400 /u exch def\n\
1401 /r exch def\n\
1402 /d exch def\n\
1403 /l exch def\n\
1404 newpath l d moveto\n\
1405 r d lineto r u lineto l u lineto\n\
1406 closepath fill\n\
1407} def\n\
1408\n";
1409
1410static char* epilog2 =
1411"showpage\n\
1412%%%%Trailer\n\
1413%%%%BoundingBox: %d %d %d %d\n";
1414
1415static point
1416coordOf (cell* cp, snode* np)
1417{
1418 point p;
1419 if (cp->sides[M_TOP] == np) {
1420 p.x = (cp->bb.LL.x + cp->bb.UR.x)/2;
1421 p.y = cp->bb.UR.y;
1422 }
1423 else if (cp->sides[M_BOTTOM] == np) {
1424 p.x = (cp->bb.LL.x + cp->bb.UR.x)/2;
1425 p.y = cp->bb.LL.y;
1426 }
1427 else if (cp->sides[M_LEFT] == np) {
1428 p.y = (cp->bb.LL.y + cp->bb.UR.y)/2;
1429 p.x = cp->bb.LL.x;
1430 }
1431 else if (cp->sides[M_RIGHT] == np) {
1432 p.y = (cp->bb.LL.y + cp->bb.UR.y)/2;
1433 p.x = cp->bb.UR.x;
1434 }
1435 return p;
1436}
1437
1438static boxf
1439emitEdge (FILE* fp, Agedge_t* e, route rte, maze* m, int ix, boxf bb)
1440{
1441 int i, x, y;
1442 boxf n = CELL(agtail(e))->bb;
1443 segment* seg = rte.segs;
1444 if (seg->isVert) {
1445 x = vtrack(seg, m);
1446 y = (n.UR.y + n.LL.y)/2;
1447 }
1448 else {
1449 y = htrack(seg, m);
1450 x = (n.UR.x + n.LL.x)/2;
1451 }
1452 bb.LL.x = MIN(bb.LL.x, SC*x);
1453 bb.LL.y = MIN(bb.LL.y, SC*y);
1454 bb.UR.x = MAX(bb.UR.x, SC*x);
1455 bb.UR.y = MAX(bb.UR.y, SC*y);
1456 fprintf (fp, "newpath %d %d moveto\n", SC*x, SC*y);
1457
1458 for (i = 1;i<rte.n;i++) {
1459 seg = rte.segs+i;
1460 if (seg->isVert) {
1461 x = vtrack(seg, m);
1462 }
1463 else {
1464 y = htrack(seg, m);
1465 }
1466 bb.LL.x = MIN(bb.LL.x, SC*x);
1467 bb.LL.y = MIN(bb.LL.y, SC*y);
1468 bb.UR.x = MAX(bb.UR.x, SC*x);
1469 bb.UR.y = MAX(bb.UR.y, SC*y);
1470 fprintf (fp, "%d %d lineto\n", SC*x, SC*y);
1471 }
1472
1473 n = CELL(aghead(e))->bb;
1474 if (seg->isVert) {
1475 x = vtrack(seg, m);
1476 y = (n.UR.y + n.LL.y)/2;
1477 }
1478 else {
1479 y = htrack(seg, m);
1480 x = (n.LL.x + n.UR.x)/2;
1481 }
1482 bb.LL.x = MIN(bb.LL.x, SC*x);
1483 bb.LL.y = MIN(bb.LL.y, SC*y);
1484 bb.UR.x = MAX(bb.UR.x, SC*x);
1485 bb.UR.y = MAX(bb.UR.y, SC*y);
1486 fprintf (fp, "%d %d lineto stroke\n", SC*x, SC*y);
1487
1488 return bb;
1489}
1490
1491static void
1492emitSearchGraph (FILE* fp, sgraph* sg)
1493{
1494 cell* cp;
1495 snode* np;
1496 sedge* ep;
1497 point p;
1498 int i;
1499 fputs ("graph G {\n", fp);
1500 fputs (" node[shape=point]\n", fp);
1501 for (i = 0; i < sg->nnodes; i++) {
1502 np = sg->nodes+i;
1503 cp = np->cells[0];
1504 if (cp == np->cells[1]) {
1505 pointf pf = midPt (cp);
1506 p.x = pf.x;
1507 p.y = pf.y;
1508 }
1509 else {
1510 if (IsNode(cp)) cp = np->cells[1];
1511 p = coordOf (cp, np);
1512 }
1513 fprintf (fp, " %d [pos=\"%d,%d\"]\n", i, p.x, p.y);
1514 }
1515 for (i = 0; i < sg->nedges; i++) {
1516 ep = sg->edges+i;
1517 fprintf (fp, " %d -- %d[len=\"%f\"]\n", ep->v1, ep->v2, ep->weight);
1518 }
1519 fputs ("}\n", fp);
1520}
1521
1522static void
1523emitGraph (FILE* fp, maze* mp, int n_edges, route* route_list, epair_t es[])
1524{
1525 int i;
1526 boxf bb, absbb;
1527 box bbox;
1528
1529 absbb.LL.x = absbb.LL.y = MAXDOUBLE;
1530 absbb.UR.x = absbb.UR.y = -MAXDOUBLE;
1531
1532 fprintf (fp, "%s", prolog2);
1533 fprintf (fp, "%d %d translate\n", TRANS, TRANS);
1534
1535 fputs ("0 0 1 setrgbcolor\n", fp);
1536 for (i = 0; i < mp->ngcells; i++) {
1537 bb = mp->gcells[i].bb;
1538 fprintf (fp, "%f %f %f %f node\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
1539 }
1540
1541 for (i = 0; i < n_edges; i++) {
1542 absbb = emitEdge (fp, es[i].e, route_list[i], mp, i, absbb);
1543 }
1544
1545 fputs ("0.8 0.8 0.8 setrgbcolor\n", fp);
1546 for (i = 0; i < mp->ncells; i++) {
1547 bb = mp->cells[i].bb;
1548 fprintf (fp, "%f %f %f %f cell\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
1549 absbb.LL.x = MIN(absbb.LL.x, bb.LL.x);
1550 absbb.LL.y = MIN(absbb.LL.y, bb.LL.y);
1551 absbb.UR.x = MAX(absbb.UR.x, bb.UR.x);
1552 absbb.UR.y = MAX(absbb.UR.y, bb.UR.y);
1553 }
1554
1555 bbox.LL.x = absbb.LL.x + TRANS;
1556 bbox.LL.y = absbb.LL.y + TRANS;
1557 bbox.UR.x = absbb.UR.x + TRANS;
1558 bbox.UR.y = absbb.UR.y + TRANS;
1559 fprintf (fp, epilog2, bbox.LL.x, bbox.LL.y, bbox.UR.x, bbox.UR.y);
1560}
1561#endif
1562