49#define DEBUG_FN UNUSED
59#define CELL(n) ((cell*)ND_alg(n))
60#define MID(a,b) (((a)+(b))/2.0)
70 if (cp == q->
cells[0] || cp == q->
cells[1])
return cp;
71 else return p->
cells[1];
91 if (cp == ptr->
cells[1]) {
120setSeg (
segment* sp,
bool dir,
double fix,
double b1,
double b2,
int l1,
int l2)
158 pointf bp1, bp2, prevbp = {0.0,0.0};
161 for (ptr = fst; ptr; ptr =
N_DAD(ptr)) sz++;
186 else if (prevbp.
y > bp1.
y) l1 =
B_UP;
211 rte.
segs[rte.
n++] = seg;
219 if (prevbp.
y > bp1.
y) l1 =
B_UP;
233 rte.
segs[rte.
n++] = seg;
242 for (
size_t i=0; i<rte.
n; i++) {
281 const paird *key1 = k1;
282 const paird *key2 = k2;
283 if (key1->
p1 > key2->
p1) {
284 if (key1->
p2 <= key2->
p2)
return 0;
287 else if (key1->
p1 < key2->
p1) {
288 if (key1->
p2 >= key2->
p2)
return 0;
295 const double *key1 = k1;
296 const double *key2 = k2;
297 if (*key1 > *key2)
return 1;
298 else if (*key1 < *key2)
return -1;
343 for (i = 0; i < mp->
ncells; i++) {
380 for (i = 0; i < mp->
ncells; i++) {
414 seg_list_append(&chan->
seg_list, seg);
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++) {
456 for (i = 0; i < cp->
nsides; i++) {
459 if (onp->
isVert)
continue;
460 if (onp->
cells[0] == cp) {
483 for (i = 0; i < cp->
nsides; i++) {
521 fprintf (fp,
"((%f,%f),(%f,%f)) %s %s", seg->
comm_coord, seg->
p.
p1,
524 fprintf (fp,
"((%f,%f),(%f,%f)) %s %s", seg->
p.
p1,seg->
comm_coord,
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) {
533 if (adj_list_is_empty(&adj))
continue;
535 fputs (
" ->\n", stderr);
536 for (
size_t i = 0; i < adj_list_size(&adj); ++i) {
538 putSeg(stderr, seg_list_get(&cp->
seg_list, adj_list_get(&adj, i)));
539 fputs (
"\n", stderr);
556 if (!seg_list_is_empty(&cp->
seg_list)) {
561 for (
size_t k = 0; k < seg_list_size(&cp->
seg_list); ++k)
588 if ((S1l2==T2 && S2l2!=T2) || (S1l2==
B_NODE && S2l2==T1))
598 if(S1->
l2==T1&&S2->
l1==T2)
return(-1);
599 else if(S1->
l2==T2&&S2->
l1==T1)
return(1);
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);
615 if (S1l2==
T)
return -1;
625 if (S1->
p.
p2 < S2->
p.
p1 || S1->
p.
p1 > S2->
p.
p2)
return 0;
632 if (S1->
p.
p1 == S2->
p.
p1) {
634 if (S1->
l1 == S2->
l1 && S1->
l2 == S2->
l2)
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;
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;
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;
665 if (S1->
p.
p2 < S2->
p.
p2) {
675 if (S1->
p.
p2 == S2->
p.
p1) {
676 if (S1->
l2 == S2->
l1)
return 0;
677 if (S1->
l2 == T2)
return 1;
681 if (S1->
l1 == S2->
l2)
return 0;
682 if (S1->
l1 == T2)
return 1;
705 agerrorf(
"incomparable segments !! -- Aborting\n");
717 seg_list_t *seg_list = &cp->
seg_list;
718 const size_t size = seg_list_size(&cp->
seg_list);
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));
727 }
else if (
cmp > 0) {
729 }
else if (
cmp == -1) {
750 if (!seg_list_is_empty(&cp->
seg_list))
782 for(x=1;x<=hops;x++) {
786 if(current->
l1==
B_UP) ans *= -1;
809 return s1->p.p1 == s2->
p.
p1 &&
810 s1->p.p2 == s2->
p.
p2 &&
823 int prec = 0, ans = 0, temp;
870 for (x=1;x<=hops;x++) {
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) {
983 if (
is_parallel(seg_list_get(segs, i), seg_list_get(segs, j))) {
985 if (seg_list_get(segs, i)->prev == 0) {
986 if (seg_list_get(segs, j)->prev == 0)
991 else if (seg_list_get(segs, j)->prev == 0) {
995 if (seg_list_get(segs, i)->prev->comm_coord ==
996 seg_list_get(segs, j)->prev->comm_coord)
1002 if (
decide_point(&p, seg_list_get(segs, i), seg_list_get(segs, j), 0, dir)
1008 if (
decide_point(&p, seg_list_get(segs, i), seg_list_get(segs, j), 1,
1021 removeEdge(seg_list_get(segs, i), seg_list_get(segs, j), 1 - dir, mp);
1022 }
else if (prec1 == 0) {
1028 }
else if (prec2 == 0) {
1032 1 - dir, hops.
b, mp);
1033 }
else if (prec2 == 1) {
1037 1 - dir, hops.
b, mp);
1039 }
else if (prec1 == 1) {
1045 removeEdge(seg_list_get(segs, i), seg_list_get(segs, j), 1 - dir, mp);
1108 const double f = (double)seg->
track_no / ((
double)seg_list_size(&chp->
seg_list) + 1);
1116 double f = 1.0 - (double)seg->
track_no / ((
double)seg_list_size(&chp->
seg_list) + 1);
1119 return round(lo + f * (hi - lo));
1141 for (
size_t irte = 0; irte < n_edges; irte++) {
1146 rte = route_list[irte];
1147 size_t npts = 1 + 3*rte.
n;
1166 ispline[0] = ispline[1] = p;
1169 for (
size_t i = 1;i<rte.
n;i++) {
1175 ispline[ipt+2] = ispline[ipt+1] = ispline[ipt] = p;
1187 ispline[ipt] = ispline[ipt+1] = p;
1202 return (
int)
DIST2(p,q);
1208 if (e0->
d > e1->
d) {
1211 if (e0->
d < e1->
d) {
1256 char*
s =
agget(g,
"odb");
1259 if (
s && *
s !=
'\0') {
1260 while ((c = *
s++)) {
1285 agwarningf(
"Orthogonal edges do not currently handle edge labels. Try using xlabels.\n");
1323 sn = &sg->
nodes[gstart];
1324 dn = &sg->
nodes[gstart+1];
1325 for (
size_t i = 0; i < n_edges; i++) {
1342 if (
shortPath (sg, dn, sn))
goto orthofinish;
1364 for (
size_t i=0; i < n_edges; i++)
1365 free (route_list[i].segs);
1376%%%%BoundingBox: (atend)\n\
1381 X Y 3 0 360 arc fill\n\
1400 newpath l d moveto\n\
1401 r d lineto r u lineto l u lineto\n\
1409%%%%BoundingBox: %.f %.f %.f %.f\n";
1430 agerrorf(
"Node not adjacent to cell -- Aborting\n");
1454 fprintf(fp,
"newpath %.0f %.0f moveto\n",
SC * x,
SC * y);
1456 for (
size_t i = 1;i<rte.
n;i++) {
1468 fprintf(fp,
"%.0f %.0f lineto\n",
SC * x,
SC * y);
1484 fprintf(fp,
"%.0f %.0f lineto stroke\n",
SC * x,
SC * y);
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++) {
1511 if (cp == np->
cells[1]) {
1518 fprintf (fp,
" %d [pos=\"%.0f,%.0f!\"]\n", i, p.
x, p.
y);
1520 for (i = 0; i < sg->
nedges; i++) {
1522 fprintf (fp,
" %d -- %d[label=\"%f\"]\n", ep->
v1, ep->
v2, ep->
weight);
1529 boxf absbb = {.
LL = {.
x = DBL_MAX, .y = DBL_MAX},
1530 .UR = {.x = -DBL_MAX, .y = -DBL_MAX}};
1533 fprintf (fp,
"%d %d translate\n",
TRANS,
TRANS);
1535 fputs (
"0 0 1 setrgbcolor\n", fp);
1536 for (
size_t i = 0; i < mp->
ngcells; i++) {
1538 fprintf (fp,
"%f %f %f %f node\n", bb.
LL.
x, bb.
LL.
y, bb.
UR.
x, bb.
UR.
y);
1541 for (
size_t i = 0; i < n_edges; i++) {
1542 absbb =
emitEdge (fp, es[i].e, route_list[i], mp, absbb);
1545 fputs (
"0.8 0.8 0.8 setrgbcolor\n", fp);
1546 for (
int i = 0; i < mp->
ncells; i++) {
1548 fprintf (fp,
"%f %f %f %f cell\n", bb.
LL.
x, bb.
LL.
y, bb.
UR.
x, bb.
UR.
y);
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
CDT_API Dtlink_t * dtflatten(Dt_t *)
CDT_API int dtclose(Dt_t *)
CDT_API Dtmethod_t * Dtoset
ordered set (self-adjusting tree)
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
static NORETURN void graphviz_exit(int status)
static int cmp(const void *key, const void *candidate)
geometric functions (e.g. on points and boxes)
void free_graph(gmlgraph *p)
int agnedges(Agraph_t *g)
char * agget(void *obj, char *name)
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
void agwarningf(const char *fmt,...)
void agerrorf(const char *fmt,...)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
char * agnameof(void *)
returns a string descriptor for the object.
maze * mkMaze(graph_t *g)
creates maze and fills maze::gcells and maze::cells. A subroutine of orthoEdges.
void updateWts(sgraph *g, cell *cp, sedge *ep)
updates sedge::weight of cell edges
makes maze with mkMaze for routing orthogonal edges
#define IsHScan(cp)
cell already inserted in horizontal channel
#define IsVScan(cp)
cell already inserted in vertical channel
#define IsNode(cp)
cell corresponds to node
static boxf bbox(Ppoly_t **obsp, int npoly, int *np)
NEATOPROCS_API void s1(graph_t *, node_t *)
snode priority queue for shortPath in sgraph
static char * bendToStr(bend b)
static int seg_cmp(segment *S1, segment *S2)
static pointf midPt(cell *cp)
static route convertSPtoRoute(sgraph *g, snode *fst, snode *lst)
static Dt_t * extractVChans(maze *mp)
static int add_edges_in_G(channel *cp)
static int decide_point(pair *ret, segment *si, segment *sj, int dir1, int dir2)
static int add_p_edges(Dt_t *chans, maze *mp)
static int edgeLen(Agedge_t *e)
static DEBUG_FN void emitSearchGraph(FILE *fp, sgraph *sg)
dumps in dot format snode::cells and edges of sgraph for debugging
static void removeEdge(segment *seg1, segment *seg2, int dir, maze *mp)
static void setSeg(segment *sp, bool dir, double fix, double b1, double b2, int l1, int l2)
static int eqEndSeg(bend S1l2, bend S2l2, bend T1, bend T2)
static double htrack(segment *seg, maze *m)
static pointf coordOf(cell *cp, snode *np)
static void putSeg(FILE *fp, segment *seg)
static int segCmp(segment *S1, segment *S2, bend T1, bend T2)
static bool swap_ends_p(edge_t *e)
static segment * next_seg(segment *seg, int dir)
static void set_parallel_edges(segment *seg1, segment *seg2, int dir1, int dir2, int hops, maze *mp)
static bool spline_merge(node_t *n)
static pointf sidePt(snode *ptr, cell *cp)
static DEBUG_FN void dumpChanG(channel *cp, double v)
static int addPEdges(channel *cp, maze *mp)
static void assignSegs(size_t nrtes, route *route_list, maze *mp)
static cell * cellOf(snode *p, snode *q)
static void create_graphs(Dt_t *chans)
static void addChan(Dt_t *chdict, channel *cp, double j)
static int add_np_edges(Dt_t *chans)
static void insertChan(channel *chan, segment *seg)
static double vtrack(segment *seg, maze *m)
static DEBUG_FN void emitGraph(FILE *fp, maze *mp, size_t n_edges, route *route_list, epair_t[])
static Dt_t * extractHChans(maze *mp)
static int overlapSeg(segment *S1, segment *S2, bend T1, bend T2)
static pointf addPoints(pointf p0, pointf p1)
static void freeChannel(void *chan)
static void assignTrackNo(Dt_t *chans)
static void attachOrthoEdges(maze *mp, size_t n_edges, route *route_list, splineInfo *sinfo, epair_t es[], bool doLbls)
void orthoEdges(Agraph_t *g, bool useLbls)
static int dcmpid(void *k1, void *k2)
static int ellSeg(bend S1l1, bend S1l2, bend T)
static void freeChanItem(void *item)
static int chancmpid(void *k1, void *k2)
static void addNodeEdges(sgraph *sg, cell *cp, snode *np)
static int assignTracks(maze *mp)
static int propagate_prec(segment *seg, int prec, int hops, int dir)
static channel * chanSearch(Dt_t *chans, segment *seg)
static void addLoop(sgraph *sg, cell *cp, snode *dp, snode *sp)
static int edgecmp(const void *x, const void *y)
static boxf emitEdge(FILE *fp, Agedge_t *e, route rte, maze *m, boxf bb)
static bool is_parallel(segment *s1, segment *s2)
static Dtdisc_t chanItemDisc
void addPS(PointSet *ps, double x, double y)
void freePS(PointSet *ps)
int isInPS(PointSet *ps, double x, double y)
point containers PointSet and PointMap
rawgraph * make_graph(size_t n)
makes a graph with n vertices, 0 edges
void insert_edge(rawgraph *g, size_t v1, size_t v2)
inserts edge FROM v1 to v2
void remove_redge(rawgraph *g, size_t v1, size_t v2)
removes any edge between v1 to v2 – irrespective of direction
void top_sort(rawgraph *g)
bool edge_exists(rawgraph *g, size_t v1, size_t v2)
tests if there is an edge FROM v1 TO v2
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, size_t pn, splineInfo *info)
void addEdgeLabels(edge_t *e)
sedge * createSEdge(sgraph *g, snode *v1, snode *v2, double wt)
int shortPath(sgraph *g, snode *from, snode *to)
result of partitioning available space, part of maze
snode ** sides
up to four sides: M_RIGHT, M_TOP, M_LEFT, M_BOTTOM
seg_list_t seg_list
segment pointers
available channels for orthogonal edges around nodes of graph_t
cell * cells
cells not corresponding to graph nodes
cell * gcells
cells corresponding to graph nodes
Dt_t * vchans
set of vertical channels, created by extractVChans
Dt_t * hchans
set of horizontal channels, created by extractHChans.
size_t ind_no
index number of this segment in its channel
a node of search graph sgraph, is created as a border segment between two adjusted cells of type cell...
struct cell * cells[2]
[0] - left or botom, [1] - top or right adjusted cell
adj_list_t adj_list
adjacency list
abstraction for squashing compiler warnings for unused symbols