From 0b6942d21edefbb42f3b7d2f3b56d63d786c133a Mon Sep 17 00:00:00 2001 From: erg Date: Fri, 25 Jun 2010 15:37:49 +0000 Subject: [PATCH] Add code to support loops drawn orthogonally; put in more flexible debugging support; fix problem when nodes have too small width or height; differentiate between cells that are small due to small nodes, and small cells due to near nodes. Only discourage routing in the second case. --- lib/ortho/maze.c | 86 ++++++++++++++++++++++++++++++++++++++++---- lib/ortho/maze.h | 22 +++++++++--- lib/ortho/ortho.c | 90 ++++++++++++++++++++++++++++++++++++++--------- 3 files changed, 172 insertions(+), 26 deletions(-) diff --git a/lib/ortho/maze.c b/lib/ortho/maze.c index 6e0d2641b..a8bd40078 100644 --- a/lib/ortho/maze.c +++ b/lib/ortho/maze.c @@ -19,6 +19,8 @@ #include "config.h" #endif +#define DEBUG + #include #include #include @@ -145,6 +147,7 @@ static Dtdisc_t hdictDisc = { #define HORZ(g,e) ((g->nodes + e->v1)->isVert) #define BIG 16384 #define CHANSZ(w) (((w)-3)/2) +#define IS_SMALL(v) (CHANSZ(v) < 2) /* #define CHANSZ(w) (w) */ static void @@ -178,7 +181,7 @@ updateWts (sgraph* g, cell* cp, sedge* ep) e = cp->edges[i]; if (!BEND(g,e)) break; updateWt (cp, e, minsz); - } +} for (; i < cp->nedges; i++) { e = cp->edges[i]; @@ -186,6 +189,64 @@ updateWts (sgraph* g, cell* cp, sedge* ep) } } +/* markSmall: + * cp corresponds to a real node. If it is small, its associated cells should + * be marked as usable. + */ +static void +markSmall (cell* cp, sgraph* g) +{ + int i; + snode* onp; + cell* ocp; + + if (IS_SMALL(cp->bb.UR.y-cp->bb.LL.y)) { + for (i = 0; i < cp->nsides; i++) { + onp = cp->sides[i]; + if (!onp->isVert) continue; + if (onp->cells[0] == cp) { /* onp on the right of cp */ + ocp = onp->cells[1]; + ocp->flags |= MZ_SMALLV; + while ((onp = ocp->sides[M_RIGHT]) && !IsNode(onp->cells[1])) { + ocp = onp->cells[1]; + ocp->flags |= MZ_SMALLV; + } + } + else { /* onp on the left of cp */ + ocp = onp->cells[0]; + ocp->flags |= MZ_SMALLV; + while ((onp = ocp->sides[M_LEFT]) && !IsNode(onp->cells[0])) { + ocp = onp->cells[0]; + ocp->flags |= MZ_SMALLV; + } + } + } + } + + if (IS_SMALL(cp->bb.UR.x-cp->bb.LL.x)) { + for (i = 0; i < cp->nsides; i++) { + onp = cp->sides[i]; + if (onp->isVert) continue; + if (onp->cells[0] == cp) { /* onp on the top of cp */ + ocp = onp->cells[1]; + ocp->flags |= MZ_SMALLH; + while ((onp = ocp->sides[M_TOP]) && !IsNode(onp->cells[1])) { + ocp = onp->cells[1]; + ocp->flags |= MZ_SMALLH; + } + } + else { /* onp on the bottom of cp */ + ocp = onp->cells[0]; + ocp->flags |= MZ_SMALLH; + while ((onp = ocp->sides[M_BOTTOM]) && !IsNode(onp->cells[0])) { + ocp = onp->cells[0]; + ocp->flags |= MZ_SMALLH; + } + } + } + } +} + static void createSEdges (cell* cp, sgraph* g) { @@ -194,11 +255,14 @@ createSEdges (cell* cp, sgraph* g) double vwt = delta*(bb.UR.y-bb.LL.y); double wt = (hwt + vwt)/2.0 + mu; - if (CHANSZ(bb.UR.y-bb.LL.y) < 2) { + /* We automatically make small channels have high cost to guide routes to + * more spacious channels. + */ + if (IS_SMALL(bb.UR.y-bb.LL.y) && !IsSmallV(cp)) { hwt = BIG; wt = BIG; } - if (CHANSZ(bb.UR.x-bb.LL.x) < 2) { + if (IS_SMALL(bb.UR.x-bb.LL.x) && !IsSmallH(cp)) { vwt = BIG; wt = BIG; } @@ -235,10 +299,10 @@ findSVert (sgraph* g, Dt_t* cdt, pointf p, snodeitem* ditems, boolean isVert) return n->np; } -void +static void chkSgraph (sgraph* g) { - int j, i; + int i; snode* np; for (i = 0; i < g->nnodes; i++) { @@ -344,6 +408,14 @@ mkMazeGraph (maze* mp, boxf bb) } RALLOC (nsides, sides, snode*); + /* Mark cells that are small because of a small node, not because of the close + * alignment of two rectangles. + */ + for (i = 0; i < mp->ngcells; i++) { + cell* cp = mp->gcells+i; + markSmall (cp, g); + } + /* Set index of two dummy nodes used for real nodes */ g->nodes[g->nnodes].index = g->nnodes; g->nodes[g->nnodes+1].index = g->nnodes+1; @@ -392,7 +464,9 @@ mkMaze (graph_t* g) BB.UR.x = BB.UR.y = -MAXDOUBLE; for (n = agfstnode (g); n; n = agnxtnode(g,n)) { w2 = ND_xsize(n)/2.0; + if (w2 < 1) w2 = 1; h2 = ND_ysize(n)/2.0; + if (h2 < 1) h2 = 1; bb.LL.x = ND_coord(n).x - w2; bb.UR.x = ND_coord(n).x + w2; bb.LL.y = ND_coord(n).y - h2; @@ -414,7 +488,7 @@ mkMaze (graph_t* g) rects = partition (mp->gcells, mp->ngcells, &nrect, BB); #ifdef DEBUG - psdump (mp->gcells, mp->ngcells, BB, rects, nrect); + if (odb_flags & ODB_MAZE) psdump (mp->gcells, mp->ngcells, BB, rects, nrect); #endif mp->cells = N_NEW(nrect, cell); mp->ncells = nrect; diff --git a/lib/ortho/maze.h b/lib/ortho/maze.h index 69702d64f..7000763b7 100644 --- a/lib/ortho/maze.h +++ b/lib/ortho/maze.h @@ -21,15 +21,22 @@ enum {M_RIGHT=0, M_TOP, M_LEFT, M_BOTTOM}; -#define MZ_ISNODE 1 -#define MZ_VSCAN 2 -#define MZ_HSCAN 4 +#define MZ_ISNODE 1 +#define MZ_VSCAN 2 +#define MZ_HSCAN 4 +#define MZ_SMALLV 8 +#define MZ_SMALLH 16 -#define IsNode(cp) (cp->flags & MZ_ISNODE) /* cell corresponds to node */ + /* cell corresponds to node */ +#define IsNode(cp) (cp->flags & MZ_ISNODE) /* cell already inserted in vertical channel */ #define IsVScan(cp) (cp->flags & MZ_VSCAN) /* cell already inserted in horizontal channel */ #define IsHScan(cp) (cp->flags & MZ_HSCAN) + /* cell has small height corresponding to a small height node */ +#define IsSmallV(cp) (cp->flags & MZ_SMALLV) + /* cell has small width corresponding to a small width node */ +#define IsSmallH(cp) (cp->flags & MZ_SMALLH) typedef struct cell { int flags; @@ -52,4 +59,11 @@ typedef struct { extern maze* mkMaze (graph_t*); extern void freeMaze (maze*); void updateWts (sgraph* g, cell* cp, sedge* ep); +#ifdef DEBUG +extern int odb_flags; +#define ODB_MAZE 1 +#define ODB_SGRAPH 2 +#define ODB_ROUTE 4 +#define ODB_CHANG 8 +#endif #endif diff --git a/lib/ortho/ortho.c b/lib/ortho/ortho.c index 2c3582d97..2978a1b18 100644 --- a/lib/ortho/ortho.c +++ b/lib/ortho/ortho.c @@ -18,10 +18,10 @@ /* TODO: * In dot, prefer bottom or top routing * In general, prefer closest side to closest side routing. - * Fix arrowheads - * Ports/compass points + * >Fix arrowheads * Edge labels * Loops + * Ports/compass points * Weights on edges in nodes * Edge concentrators? */ @@ -30,6 +30,7 @@ #include "config.h" #endif +#define DEBUG #include #include #include "fPQ.h" @@ -42,6 +43,7 @@ #ifdef DEBUG static void emitSearchGraph (FILE* fp, sgraph* sg); static void emitGraph (FILE* fp, maze* mp, Agraph_t* g, route* route_list); +int odb_flags; #endif #define CELL(n) ((cell*)ND_alg(n)) @@ -443,13 +445,41 @@ assignSegs (int nrtes, route* route_list, maze* mp) } /* addLoop: - * Add temporary nodes to sgraph corresponding to cell cp, represented - * by np. + * Add two temporary nodes to sgraph corresponding to two ends of a loop at cell cp, i + * represented by dp and sp. */ static void -addLoop (sgraph* sg, cell* cp, snode* np) +addLoop (sgraph* sg, cell* cp, snode* dp, snode* sp) { + int i; + int onTop; + pointf midp = midPt (cp); + + for (i = 0; i < cp->nsides; i++) { + cell* ocp; + pointf p; + double wt; + snode* onp = cp->sides[i]; + + if (onp->isVert) continue; + if (onp->cells[0] == cp) { + onTop = 1; + ocp = onp->cells[1]; + } + else { + onTop = 0; + ocp = onp->cells[0]; + } + p = sidePt (onp, ocp); + wt = abs(p.x - midp.x) + abs(p.y - midp.y); + if (onTop) + createSEdge (sg, sp, onp, 0); /* FIX weight */ + else + createSEdge (sg, dp, onp, 0); /* FIX weight */ + } + sg->nnodes += 2; } + /* addNodeEdges: * Add temporary node to sgraph corresponding to cell cp, represented * by np. @@ -458,17 +488,19 @@ static void addNodeEdges (sgraph* sg, cell* cp, snode* np) { int i; + pointf midp = midPt (cp); + for (i = 0; i < cp->nsides; i++) { snode* onp = cp->sides[i]; cell* ocp; - pointf midp, p; + pointf p; double wt; + if (onp->cells[0] == cp) ocp = onp->cells[1]; else ocp = onp->cells[0]; p = sidePt (onp, ocp); - midp = midPt (cp); wt = abs(p.x - midp.x) + abs(p.y - midp.y); createSEdge (sg, np, onp, 0); /* FIX weight */ } @@ -552,7 +584,7 @@ assignTrackNo (Dt_t* chans) cp = (channel*)l2; if (cp->cnt) { #ifdef DEBUG -/* dumpChanG (cp, ((chanItem*)l1)->v); */ + if (odb_flags & ODB_CHANG) dumpChanG (cp, ((chanItem*)l1)->v); #endif top_sort (cp->G); for (k=0;kcnt;k++) @@ -1076,10 +1108,6 @@ assignTracks (int nrtes, route* route_list, maze* mp) assignTrackNo (mp->vchans); } -#ifdef DEBUG -static void emitGraph (FILE* fp, maze* mp, Agraph_t* g, route* route_list); -#endif - static double vtrack (segment* seg, maze* m) { @@ -1222,8 +1250,36 @@ orthoEdges (Agraph_t* g, int useLbls) if (Concentrate) ps = newPS(); +#ifdef DEBUG + { + char* s = agget(g, "odb"); + char c; + odb_flags = 0; + if (s && (*s != '\0')) { + while ((c = *s++)) { + switch (c) { + case 'c' : + odb_flags |= ODB_CHANG; + break; + case 'm' : + odb_flags |= ODB_MAZE; + break; + case 'r' : + odb_flags |= ODB_ROUTE; + break; + case 's' : + odb_flags |= ODB_SGRAPH; + break; + } + } + } + } +#endif mp = mkMaze (g); sg = mp->sg; +#ifdef DEBUG + if (odb_flags & ODB_SGRAPH) emitSearchGraph (stderr, sg); +#endif n_edges = 0; for (n = agfstnode (g); n; n = agnxtnode(g, n)) { @@ -1261,7 +1317,7 @@ orthoEdges (Agraph_t* g, int useLbls) dest = CELL(aghead(e)); if (start == dest) - addLoop (sg, start, dn); + addLoop (sg, start, dn, sn); else { addNodeEdges (sg, dest, dn); addNodeEdges (sg, start, sn); @@ -1277,7 +1333,9 @@ orthoEdges (Agraph_t* g, int useLbls) mp->vchans = extractVChans (mp); assignSegs (n_edges, route_list, mp); assignTracks (n_edges, route_list, mp); - /* emitGraph (stdout, mp, g, route_list); */ +#ifdef DEBUG + if (odb_flags & ODB_ROUTE) emitGraph (stderr, mp, g, route_list); +#endif attachOrthoEdges (mp, n_edges, route_list, &sinfo, es); if (Concentrate) @@ -1456,7 +1514,7 @@ emitGraph (FILE* fp, maze* mp, Agraph_t* g, route* route_list) fputs ("0 0 1 setrgbcolor\n", fp); for (i = 0; i < mp->ngcells; i++) { bb = mp->gcells[i].bb; - printf ("%f %f %f %f node\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y); + fprintf (fp, "%f %f %f %f node\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y); } i = 0; @@ -1470,7 +1528,7 @@ emitGraph (FILE* fp, maze* mp, Agraph_t* g, route* route_list) fputs ("0.8 0.8 0.8 setrgbcolor\n", fp); for (i = 0; i < mp->ncells; i++) { bb = mp->cells[i].bb; - printf ("%f %f %f %f cell\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y); + fprintf (fp, "%f %f %f %f cell\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y); absbb.LL.x = MIN(absbb.LL.x, bb.LL.x); absbb.LL.y = MIN(absbb.LL.y, bb.LL.y); absbb.UR.x = MAX(absbb.UR.x, bb.UR.x); -- 2.40.0