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