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