layout/redactgraph.c

   1 /*
   2  * output format from printforforsafety is lines like this:
   3  *   segment <node>.<side> <node>.<side> <segment>[/<movinfo>] <distance>
   4  *   #...         (comment)
   5  *                (blank)
   6  *   end          (at end of file, mandatory)
   7  * syntactic restrictions:
   8  *   <node> is alphanumeric and starts with a letter
   9  *   <side> is precisely the digit 0 or the digit 1
  10  *   <segment> is alphanumeric (and comes from the layout)
  11  *   <movinfo> is  <movfeat><movpos>[<movfeat><movpos>...]*<combpos>
  12  *            where <movfeat> is alphabetic and <movpos> is and
  13  *            <combpos> are in decimal and have no unnecessary leading 0's
  14  *   <distance> contains only digits and perhaps decimal point
  15  * semantic restrictions (not enforced by redactgraph but ought to
  16  * be impossible for layout designer to violate):
  17  *   Each <segment>[/<movinfo>] appears exactly once.
  18  *   <segment> appears either once without /<movinfo> or always with.
  19  *   Each side of each node appears either
  20  *    - once as the 0th or 1th end of a <segment>
  21  *    - one or more times as the same end of <segment>/<movinfo>'s with
  22  *      the same <segment>
  23  *    - not at all (indicates a terminus)
  24  * Refer to safety.h for info regarding <combpos>.
  25  *
  26  * See layout-data.h comment for info regarding layout data for
  27  * control system.
  28  */
  29 /* for debugging, runes like
  30  *  ./ours.redactgraph consistency movfeatsplitedges consistency movfeatrmstubs consistency movfeatsplitnodes consistency trivpairnodes consistency trivnullnodes consistency printforneato | neato -Tps >u.ps
  31  * are often useful.
  32  */
  33
  34 #include <stdarg.h>
  35 #include <string.h>
  36 #include <stdlib.h>
  37 #include <stdio.h>
  38 #include <assert.h>
  39 #include <errno.h>
  40
  41 #include "dlist.h"
  42 #include "graph-data.h"
  43
  44 #define MMALLOC(sz) mmalloc(sz,__FILE__,__LINE__)
  45 #define MREALLOC(p,sz) mrealloc(p,sz,__FILE__,__LINE__)
  46
  47 static const char *title= "L";
  48
  49 static void *mmalloccheck(void *p, const char *op, size_t sz,
  50                           const char *file, int line) {
  51   if (p) return p;
  52   fprintf(stderr,"%s:%d: %s of %lu failed: %s\n",
  53           file, line, op, (unsigned long)sz, strerror(errno));
  54   exit(16);
  55 }
  56
  57 static void *mmalloc(size_t sz, const char *file, int line) {
  58   void *p;
  59   if (!sz) return 0;
  60   p= malloc(sz);
  61   return mmalloccheck(p,"malloc",sz,file,line);
  62 }
  63
  64 static void *mrealloc(void *p, size_t sz, const char *file, int line) {
  65   p= realloc(p,sz);
  66   return mmalloccheck(p,"realloc",sz,file,line);
  67 }
  68
  69 static char *mvasprintf(const char *fmt, va_list al)
  70      __attribute__((format(printf,1,0)));
  71 static char *mvasprintf(const char *fmt, va_list al) {
  72   char *p;
  73   int r;
  74
  75   r= vasprintf(&p,fmt,al);
  76   if (r<0) {
  77     fprintf(stderr,"vasprintf(\"%s\",...) failed: %s\n",
  78             fmt, strerror(errno));
  79     exit(16);
  80   }
  81   return p;
  82 }
  83
  84 static char *masprintf(const char *fmt, ...)
  85      __attribute__((format(printf,1,2)));
  86 static char *masprintf(const char *fmt, ...) {
  87   va_list al;
  88   char *p;
  89   va_start(al,fmt);
  90   p= mvasprintf(fmt,al);
  91   va_end(al);
  92   return p;
  93 }
  94
  95 /*---------- output processing ----------*/
  96
  97 static void voutputstuff(int trace, const char *fmt, va_list al)
  98      __attribute__((format(printf,2,0)));
  99 static void voutputstuff(int trace, const char *fmt, va_list al) {
 100   static struct OutputBuf {
 101     int used, allocd;
 102     char *buf;
 103   } bufs[2];
 104
 105   struct OutputBuf *b;
 106   char *s, *p, *newline;
 107   int l;
 108
 109   b= &bufs[trace];
 110   s= mvasprintf(fmt,al);
 111   p= s;
 112
 113   for (;;) {
 114     newline= strchr(p,'\n');
 115     if (newline) { *newline= 0; }
 116     l= strlen(p);
 117     if (l+b->used > b->allocd) {
 118       b->allocd= l+b->used;
 119       b->buf= MREALLOC(b->buf, b->allocd);
 120     }
 121     memcpy(b->buf+b->used, p, l);
 122     b->used += l;
 123
 124     if (!newline) break;
 125
 126     if (trace) { fputs("# ",stdout); }
 127     fwrite(b->buf, 1,b->used, stdout);
 128     putc('\n',stdout);
 129     if (ferror(stdout) || fflush(stdout)) {
 130       perror("stdout voutputstuff"); exit(12);
 131     }
 132     b->used= 0;
 133     p= newline+1;
 134   }
 135
 136   free(s);
 137 }
 138
 139 #define OF(fn,tr)                                                           \
 140   static void v##fn(const char *fmt, va_list al)                            \
 141      __attribute__((format(printf,1,0)));                                   \
 142   static void v##fn(const char *fmt, va_list al) {                          \
 143     voutputstuff(tr,fmt,al);                                                \
 144   }                                                                         \
 145   static void fn(const char *fmt, ...) __attribute__((format(printf,1,2))); \
 146   static void fn(const char *fmt, ...) {                                    \
 147     va_list al;                                                             \
 148     va_start(al,fmt);                                                       \
 149     v##fn(fmt,al);                                                          \
 150     va_end(al);                                                             \
 151   }
 152 OF(output,0)
 153 OF(trace,1)
 154
 155 /*---------- traceing of various things ----------*/
 156
 157 static void trace_node(Node *node) {
 158   trace("n%s",node->pname);
 159 }
 160
 161 static void trace_nodeside(NodeSide *node) {
 162   trace("n%s %c",node->node->pname,"OI"[node->side]);
 163 }
 164
 165 static void trace_edge(Edge *edge) {
 166   trace("e%s",edge->pname);
 167 }
 168
 169 static void trace_edgeend(EdgeEnd *edge) {
 170   trace("e%s %c",edge->edge->pname,"OI"[edge->end]);
 171 }
 172
 173 static void trace_combpos(int combpos, Segment *seg) {
 174   int i, weight;
 175   MovFeat *f;
 176
 177   trace("*");
 178   weight= 1;
 179   FOR_SEGMENT_MOVFEATS(i,f,seg) {
 180     if (!f->movfeat) continue;
 181     trace("%s%d", f->movfeat, (combpos / weight) % f->n_positions);
 182     weight *= f->n_positions;
 183   }
 184 }
 185
 186 /*---------- general graph-manipulation tools ----------*/
 187
 188 static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
 189   return &thisend->edge->ends[!thisend->end];
 190 }
 191
 192 static int count_edges(const NodeSide *node) {
 193   int count;
 194   const EdgeEnd *edge;
 195
 196   for (count=0, edge=node->head;
 197        edge;
 198        count++, edge=edge->next);
 199   return count;
 200 }
 201
 202 static Edge *edge_create(const char *pname, double distance,
 203                          MovFeat *subseg, int movpos) {
 204   Edge *e;
 205   int end;
 206
 207   e= MMALLOC(sizeof(*e));
 208   e->pname= pname;
 209   e->distance= distance;
 210   e->subseg= subseg;
 211   e->movpos= movpos;
 212   FOR_BOTH(end) {
 213     e->ends[end].edge= e;
 214     e->ends[end].end= end;
 215   }
 216   trace("[new:"); trace_edge(e); trace("]");
 217   return e;
 218 }
 219
 220 static Node *node_create(const char *pname) {
 221   Node *n;
 222   int side;
 223
 224   n= MMALLOC(sizeof(*n));
 225   n->pname= pname;
 226   FOR_BOTH(side) {
 227     n->sides[side].node= n;
 228     n->sides[side].side= side;
 229     LIST_INIT(n->sides[side]);
 230   }
 231   LIST_LINK_TAIL(all_nodes,n);
 232   return n;
 233 }
 234
 235 /* Perhaps surprisingly, it's OK to remove nodes and edges in loops
 236  * made with the macros in graph-data.h, provided that if the
 237  * _current_ node or edge is removed, that happens last.  This is
 238  * because removing a node or edge it doesn't actually free it or
 239  * change its contents, so the thing->next is still valid afterwards.
 240  * This depends on the fact that we never free anything we're done
 241  * with !
 242  */
 243
 244 static void edgeend_detach(EdgeEnd *toremove) {
 245   trace("[detach:"); trace_edgeend(toremove);
 246   trace("-"); trace_nodeside(toremove->node); trace("]");
 247   LIST_UNLINK(*toremove->node, toremove);
 248 }
 249 static void edgeend_attach(EdgeEnd *toattach, NodeSide *newtarget) {
 250   trace("[attach:"); trace_edgeend(toattach);
 251   trace("-"); trace_nodeside(newtarget); trace("]");
 252   LIST_LINK_TAIL(*newtarget, toattach);
 253   toattach->node= newtarget;
 254 }
 255 static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) {
 256   edgeend_detach(tomove);
 257   edgeend_attach(tomove,newtarget);
 258 }
 259
 260 static void edge_delete(EdgeEnd *detachlast) {
 261   Edge *edge;
 262   edge= detachlast->edge;
 263   edgeend_detach(&edge->ends[!detachlast->end]);
 264   edgeend_detach(detachlast);
 265   trace("[delete:"); trace_edge(edge); trace("]");
 266 }
 267
 268 static void node_surely_orphaned(Node *node) {
 269   trace("[nodeorphan:"); trace_node(node); trace("]");
 270   assert(!node->sides[0].head);
 271   assert(!node->sides[1].head);
 272   LIST_UNLINK(all_nodes, node);
 273 }
 274
 275 /*---------- operations - heavyweight graph redaction ----------*/
 276
 277   /* We combine the individual moveable features in each segment into
 278    * a single `feature' with the cross-product of all of the
 279    * positions.  The new feature does not appear in
 280    * Segment->[n_]movfeats, but Edge->subseg and Edge->movpos are
 281    * updated (ie Edge->subseg->segment->movfeats is the original array
 282    * containing only the actual features, and so does not contain
 283    * Edge->subseg).  It is often printed as if its name was `*' (which
 284    * is not legal in input files etc.).  The positions of the
 285    * *-feature are numbered according to the obvious arithmetic coding
 286    * of the individual actual feature positions.  See also
 287    * hostside/safety.h.
 288    *
 289    * The conversion has two stages:
 290    *
 291    * FIRST STAGE (movfeatsplitedges):
 292    *
 293    * We multiply up each edge of any segment with moveable features to
 294    * be an edge which is a position of the *-feature.
 295    *
 296    * For example, if segment A1 has feature P with states 0 and 1
 297    * and feature J with states 0 and 1, then the edges are translated
 298    * as follows
 299    *   old edge    new edges
 300    *    A1          A1/P0J0 A1/P0J1 A1/P1J0 A1/P1J1
 301    *    A1/P0       A1/P0J0 A1/P0J1
 302    *    A1/P1                       A1/P1J0 A1/P1J1
 303    *    A1/J0       A1/P0J0         A1/P1J0
 304    *    A1/J1               A1/P0J1         A1/P1J1
 305    * Eg,
 306    *     *----A1/P0----*   becomes   *----A1/P0J0----*
 307    *                                  `---A1/P0J1---'
 308    *
 309    * SECOND STAGE (movfeatrmstubs):
 310    *
 311    * We remove stub moveable edges: whenever, at a node which has only
 312    * edges which are part of the same segment, we find an edge on one
 313    * side in which is not matched exactly (moveable feature settings
 314    * and direction) by an edge on the other side, we delete that extra
 315    * edge:
 316    *
 317    * is split into one node
 318    * for each position and direction (directions are
 319    * end0-to-side0+end1-to-side1 and end0-to-side1+end1-to-side0), to
 320    * which the corresponding edges are connected.  Any resulting node
 321    * which has only one edge is removed together with the edge.
 322    *
 323    * For example (neglecting direction for the purposes of the
 324    * example), when we start with:
 325    *
 326    *             ,---A1/P0J0---.
 327    *         ...*----A1/P0J1----*---A1/P0J1---*...
 328    *             `---A1/P1J0---' `--A1/P1J1--'
 329    *              `--A1/P1J1--'
 330    *
 331    * the edges A1/P0J0 and A1/P1J1 are not matched on the RHS of the node,
 332    * so they are removed:
 333    *
 334    *         ...*----A1/P0J1----*---A1/P0J1---*...
 335    *             `---A1/P1J0---' `--A1/P1J1--'
 336    *
 337    *
 338    * THIRD STAGE:
 339    *
 340    * We split nodes: every node which has only edges which are part of
 341    * the same segment is split into one node for each kind of edge
 342    * which goes through it.  The 2nd stage ensures that this is always
 343    * straightforward.
 344    *
 345    * Our example above turns into:
 346    *
 347    *         ...*----A1/P0J1----*---A1/P0J1---*...
 348    *             `---A1/P1J0----*---A1/P1J1--'
 349    */
 350
 351 static void movfeatsplitedges(void) {
 352   Node *node;
 353   int side, l, i, weight, combpos, end;
 354   EdgeEnd *edgeend;
 355   Edge *edge, *newedge;
 356   Segment *segment;
 357   MovFeat *subseg, *starfeature, *loopfeat;
 358   char *featstr;
 359
 360   trace("movfeatsplitedges ...\n");
 361   FOR_ALL_NODES(node) {
 362     FOR_EDGES(edge, node,side,edgeend) {
 363       subseg= edge->subseg;
 364       segment= subseg->segment;
 365
 366       trace("movfeatsplitedges "); trace_edge(edge);
 367       trace(" segment %s ", segment->segname);
 368       if (segment->n_movfeats<=1) { trace("no moveables\n"); continue; }
 369       if (subseg == segment->starfeature) { trace("*-feature\n"); continue; }
 370
 371       starfeature= segment->starfeature;
 372       if (starfeature) {
 373         trace("old");
 374       } else {
 375         trace("new");
 376         starfeature= MMALLOC(sizeof(*starfeature));
 377         starfeature->segment= segment;
 378
 379         l=2;  starfeature->n_positions=1;
 380         FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
 381           if (!loopfeat->movfeat) continue;
 382           l += strlen(loopfeat->movfeat);
 383           starfeature->n_positions *= loopfeat->n_positions;
 384         }
 385
 386         starfeature->movfeat= featstr= MMALLOC(l);
 387         strcpy(featstr, "*");
 388
 389         FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
 390           if (!loopfeat->movfeat) continue;
 391           strcat(featstr, loopfeat->movfeat);
 392         }
 393
 394         segment->starfeature= starfeature;
 395       }
 396       trace(" %s(%d) ", starfeature->movfeat, starfeature->n_positions);
 397
 398       if (subseg->movfeat) {
 399         weight= 1;
 400         FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
 401           if (loopfeat == subseg) goto found;
 402           weight *= loopfeat->n_positions;
 403         }
 404         abort();
 405       found:
 406         trace("%s(x%d)",subseg->movfeat,weight);
 407       } else {
 408         weight= 1;
 409         trace("fixed");
 410       }
 411
 412       trace(" ...\n");
 413
 414       for (combpos=0; combpos<starfeature->n_positions; combpos++) {
 415         trace("movfeatsplitedges  "); trace_combpos(combpos,segment);
 416         if ((combpos / weight) % subseg->n_positions != edge->movpos) {
 417           trace(" excluded\n");
 418           continue;
 419         }
 420         newedge= edge_create(masprintf("%s/*%d",edge->pname,combpos),
 421                              edge->distance,
 422                              starfeature,
 423                              combpos);
 424         FOR_BOTH(end)
 425           edgeend_attach(&newedge->ends[end], edge->ends[end].node);
 426       }
 427       edge_delete(edgeend);
 428     }
 429   }
 430   trace("movfeatsplitedges complete.\n");
 431 }
 432
 433 static int movfeat_isinnernode(Node *node) {
 434   int side;
 435   EdgeEnd *edgeend;
 436   Segment *all_segment, *segment;
 437
 438   trace_node(node);
 439   all_segment= 0;
 440   FOR_BOTH(side) {
 441     if (!node->sides[side].head) {
 442       trace(" %c terminus\n", "OI"[side]);
 443       return 0;
 444     }
 445   }
 446   FOR_NODE_EDGEENDS(side,edgeend, node) {
 447     segment= edgeend->edge->subseg->segment;
 448     if (!all_segment) {
 449       all_segment= segment;
 450     } else if (all_segment != segment) {
 451       trace(" not inner: %s and %s\n",
 452             all_segment->segname, segment->segname);
 453       return 0;
 454     }
 455   }
 456   if (!all_segment) {
 457     trace(" not inner: no edges?!\n");
 458     return 0;
 459   }
 460   trace(" inner %s ",all_segment->segname);
 461   return 1;
 462 }
 463
 464 static EdgeEnd *movfeat_findmate(EdgeEnd *key) {
 465   Node *node;
 466   EdgeEnd *mate;
 467   int mateside;
 468
 469   node= key->node->node;
 470   mateside= !key->node->side;
 471
 472   FOR_SIDE_EDGEENDS(mate, node,mateside) {
 473     if (key->edge->subseg == mate->edge->subseg &&
 474         key->edge->movpos == mate->edge->movpos &&
 475         key->end != mate->end)
 476       return mate;
 477   }
 478   return 0; /* no mate - must be a stub */
 479 }
 480
 481 static void movfeatrmstubs(void) {
 482   int pass, anychange, side;
 483   Node *node;
 484   Edge *edge;
 485   EdgeEnd *edgeend, *mate;
 486
 487   pass= 0;
 488   do {
 489     anychange= 0;
 490     pass++;
 491     trace("movfeatrmstubs pass %d ...\n", pass);
 492     FOR_ALL_NODES(node) {
 493       trace("movfeatrmstubs ");
 494       if (!movfeat_isinnernode(node)) continue;
 495       FOR_NODE_EDGEENDS(side,edgeend, node) {
 496         edge= edgeend->edge;
 497         mate= movfeat_findmate(edgeend);
 498         if (mate) {
 499           trace("("); trace_edgeend(edgeend); trace(")");
 500           continue;
 501         }
 502         edge_delete(edgeend);
 503         anychange++;
 504       }
 505       trace("\n");
 506     }
 507     trace("movfeatrmstubs pass %d %s\n", pass, anychange?"changed":"alldone");
 508   } while (anychange);
 509 }
 510
 511 static int movfeatsplitnodes_once(void) {
 512   Node *node, *newnode;
 513   EdgeEnd *edgeend, *mate;
 514   Edge *edge;
 515   int side, ndone=0;
 516
 517   FOR_ALL_NODES(node) {
 518     trace("movfeatsplitnodes ");
 519     if (!movfeat_isinnernode(node)) continue;
 520     if (!node->sides[0].head->next) {
 521       trace("pair-trivial\n");
 522       continue;
 523     }
 524     FOR_NODE_EDGEENDS(side,edgeend, node) {
 525       ndone++;
 526       edge= edgeend->edge;
 527       mate= movfeat_findmate(edgeend);
 528       assert(mate);
 529       newnode= node_create(masprintf("%sx%d",node->pname,edge->movpos));
 530       edgeend_replumb(mate, &newnode->sides[mate->node->side]);
 531       edgeend_replumb(edgeend, &newnode->sides[edgeend->node->side]);
 532     }
 533   }
 534   trace("movfeatsplitnodes_once=%d\n",ndone);
 535   return ndone;
 536 }
 537
 538 static void movfeatsplitnodes(void) { movfeatsplitnodes_once(); }
 539 static void movfeatsplitnodesall(void) { while ( movfeatsplitnodes_once() ); }
 540
 541 /*---------- operations - trivial graph redaction etc. ----------*/
 542
 543 static void trivpairnodes(void) {
 544   /* Eliminate near-trivial nodes - in this case, ones which have only
 545    * two edges, which come in on opposite sides, have the same
 546    * subsegspec, and with the two ends identically aligned.
 547    */
 548   EdgeEnd *leftedge, *rightedge;
 549   Node *node;
 550
 551   FOR_ALL_NODES(node) {
 552     trace("trivpairnodes node "); trace_node(node); trace(" ");
 553     if (!(count_edges(&node->sides[0])==1 &&
 554           count_edges(&node->sides[1])==1)) {
 555       trace("no, a non-unitary side\n");
 556       continue;
 557     }
 558     leftedge= node->sides[0].head;
 559     rightedge= node->sides[1].head;
 560     if (leftedge->edge->subseg != rightedge->edge->subseg) {
 561       trace("no, (sub)segments differ\n");
 562       continue;
 563     }
 564     if (leftedge->edge->movpos != rightedge->edge->movpos) {
 565       trace("no, movpos's differ\n");
 566       continue;
 567     }
 568     if (leftedge->end == rightedge->end) {
 569       trace("no, opposite alignment\n");
 570       continue;
 571     }
 572     trace(" yes:\n");
 573     if (!strchr(rightedge->edge->pname, '+')) {
 574       rightedge->edge->pname=
 575         masprintf("%s+", rightedge->edge->pname);
 576     }
 577     rightedge->edge->distance += leftedge->edge->distance;
 578     edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
 579     edge_delete(leftedge);
 580     trace(" trivpairnodes operation complete\n");
 581   }
 582 }
 583
 584 static void trivnullnodes(void) {
 585   /* Eliminate trivial nodes - ones which have no edges. */
 586   Node *node;
 587   int side;
 588
 589   trace("trivnullnodes ");
 590   FOR_ALL_NODES(node) {
 591     FOR_BOTH(side) {
 592       if (node->sides[side].head)
 593         goto non_null;
 594     }
 595     node_surely_orphaned(node);
 596   non_null:;
 597   }
 598   trace(" trivnullnodes done.\n");
 599 }
 600
 601 static void check(const char *why) {
 602   Node *node;
 603   int alloc_edone, used_edone;
 604   typedef struct { Edge *edge; int endsdone; } EdgeDone;
 605   EdgeDone *edone, *search_edone;
 606   int side;
 607   EdgeEnd *edgeend;
 608   Edge *edge;
 609
 610   edone= 0;
 611   alloc_edone= used_edone= 0;
 612
 613   trace("consistency check (%s) ...\n",why);
 614   FOR_ALL_NODES(node) {
 615     trace(" consistency "); trace_node(node); trace("\n");
 616     LIST_CHECKNODE(all_nodes,node);
 617     FOR_BOTH(side) {
 618       trace(" consistency "); trace_nodeside(&node->sides[side]); trace("\n");
 619       assert(node->sides[side].node == node);
 620       assert(node->sides[side].side == side);
 621       FOR_SIDE_EDGEENDS(edgeend, node,side) {
 622         trace(" consistency "); trace_nodeside(&node->sides[side]);
 623         trace(" "); trace_edgeend(edgeend); trace("\n");
 624
 625         edge= edgeend->edge;
 626         LIST_CHECKNODE(node->sides[side], edgeend);
 627         assert(edgeend == &edge->ends[edgeend->end]);
 628         assert(edgeend->node == &node->sides[side]);
 629         if (used_edone==alloc_edone) {
 630           alloc_edone += 2; alloc_edone *= 2;
 631           edone= MREALLOC(edone, alloc_edone * sizeof(*edone));
 632         }
 633         for (search_edone= edone;
 634              search_edone < edone + used_edone && search_edone->edge != edge;
 635              search_edone++);
 636         if (search_edone >= edone + used_edone) {
 637           search_edone->edge= edge;
 638           search_edone->endsdone= 0;
 639           used_edone++;
 640         }
 641         search_edone->endsdone++;
 642         assert(search_edone->endsdone <= 2);
 643       }
 644     }
 645   }
 646   for (search_edone= edone;
 647        search_edone < edone + used_edone;
 648        search_edone++) {
 649     trace("consistency "); trace_edge(search_edone->edge);
 650     trace(" count=%d\n", search_edone->endsdone);
 651     assert(search_edone->endsdone == 2);
 652   }
 653   trace("consistency check (%s) ok\n",why);
 654 }
 655
 656 static void consistency(void) {
 657   check("command-line request");
 658 }
 659
 660 /*---------- operations - output ----------*/
 661
 662 static void printforneato_edgelabel(Edge *edge, const char *pname,
 663                                     const char *distdelim) {
 664   const char *segname= edge->subseg->segment->segname;
 665   output(" [label=\"");
 666   if (pname) output("%s:", pname);
 667   if (!segname) {
 668     output("?");
 669   } else {
 670     output(segname);
 671     if (edge->subseg->movfeat)
 672       output("/%s%d",edge->subseg->movfeat,edge->movpos);
 673   }
 674   output("%s%.2f\"", distdelim, edge->distance);
 675 }
 676
 677 static void printforneato(void) {
 678   Node *node;
 679   EdgeEnd *edgeend;
 680   Edge *edge;
 681   int side;
 682
 683   output("digraph \"%s\" {\n", title);
 684
 685   FOR_ALL_NODES(node) {
 686     output("  n%sO [label=\"%s\"];\n"
 687            "  n%sI [label=\"+\"];\n",
 688            node->pname, node->pname, node->pname);
 689     output("  n%sO -> n%sI [len=0.25 arrowsize=0];\n",
 690            node->pname, node->pname);
 691     FOR_EDGES(edge, node,side,edgeend) {
 692       output("  n%s%c -> n%s%c",
 693              edge->ends[0].node->node->pname,
 694              "OI"[edge->ends[0].node->side],
 695              edge->ends[1].node->node->pname,
 696              "OI"[edge->ends[1].node->side]);
 697       printforneato_edgelabel(edge, edge->pname, ":");
 698       output("];\n");
 699     }
 700   }
 701   output("}\n");
 702 }
 703
 704 static void printforneatosumm(void) {
 705   Node *node;
 706   EdgeEnd *edgeend;
 707   Edge *edge;
 708   int side;
 709
 710   output("digraph \"%s\" {\n", title);
 711
 712   FOR_ALL_NODES(node) {
 713     output("  n%s [shape=circle, style=filled, color=grey,"
 714            " label=\"\", height=0.2];\n",
 715            node->pname);
 716     FOR_EDGES(edge, node,side,edgeend) {
 717       output("  n%s -> n%s",
 718              edge->ends[0].node->node->pname,
 719              edge->ends[1].node->node->pname);
 720       printforneato_edgelabel(edge, 0, "\\n");
 721       output(", len=2, color=\"#999999\","
 722              " labeldistance=0, port_label_distance=0];\n");
 723     }
 724   }
 725   output("}\n");
 726 }
 727
 728 static void printforforsafety(void) {
 729   Node *node;
 730   Edge *edge;
 731   EdgeEnd *edgeend;
 732   int side, end, weight, i;
 733   Segment *segment;
 734   MovFeat *movfeat;
 735
 736   FOR_ALL_NODES(node) {
 737     FOR_EDGES(edge, node,side,edgeend) {
 738       output("segment ");
 739       FOR_BOTH(end) {
 740         output("n%s.%d ",
 741                edge->ends[end].node->node->pname,
 742                edge->ends[end].node->side);
 743       }
 744       segment= edge->subseg->segment;
 745       output(segment->segname);
 746       if (segment->n_movfeats>1) {
 747         if (!segment->starfeature) {
 748           fprintf(stderr,"printforforsafety before movfeatsplitedges!\n");
 749           exit(8);
 750         }
 751         output("/");
 752         weight= 1;
 753         FOR_SEGMENT_MOVFEATS(i,movfeat, segment) {
 754           if (!movfeat->movfeat) continue;
 755           output("%s%d", movfeat->movfeat,
 756                  (edge->movpos / weight) % movfeat->n_positions);
 757           weight *= movfeat->n_positions;
 758         }
 759         output("*%d", edge->movpos);
 760       }
 761       output(" %f\n", edge->distance);
 762     }
 763   }
 764   output("end\n");
 765 }
 766
 767 static void printforshellscript(void) {
 768   Node *node;
 769   Edge *edge;
 770   EdgeEnd *edgeend;
 771   int side, weight, i;
 772   Segment *segment;
 773   MovFeat *movfeat;
 774
 775   FOR_ALL_NODES(node) {
 776     FOR_EDGES(edge, node,side,edgeend) {
 777       output("l");
 778       segment= edge->subseg->segment;
 779       output(segment->segname);
 780       if (segment->n_movfeats>1) {
 781         if (!segment->starfeature) {
 782           fprintf(stderr,"printforshellscript before movfeatsplitedges!\n");
 783           exit(8);
 784         }
 785         weight= 1;
 786         FOR_SEGMENT_MOVFEATS(i,movfeat, segment) {
 787           if (!movfeat->movfeat) continue;
 788           output("%s%d", movfeat->movfeat,
 789                  (edge->movpos / weight) % movfeat->n_positions);
 790           weight *= movfeat->n_positions;
 791         }
 792       }
 793       output("=%d\n", (int)edge->distance);
 794     }
 795   }
 796 }
 797
 798 static void printforlayoutsegjoins(void) {
 799   Node *node;
 800   EdgeEnd *edgeend, *edgeend2;
 801   Segment **segmentp, *segment, *segment2;
 802   int side, side2, order, max_order, colour, any_left;
 803
 804   /* we format segment->u as follows: */
 805 #define LSJ_U_VERTEXORDER_MASK 0x000000ff
 806 #define LSJ_U_COLOUR_SHIFT                8
 807 #define LSJ_U_COLOUR_BITS                 16
 808 #define LSJ_U_COLOUR_UNIT                 (1<<LSJ_U_COLOUR_SHIFT)
 809 #define LSJ_U_COLOUR_MASK      0x00ffff00
 810 #define LSJ_U_SEGEND_DONE      0x01000000
 811 #define LSJ_U_COLOUR_CLASH     0x02000000
 812
 813   max_order= 0;
 814   FOR_ALL_SEGMENTS(segmentp,segment)
 815     segment->u= 0;
 816
 817   FOR_ALL_NODES(node) {
 818     output("layer ");
 819     FOR_BOTH(side)
 820       if (!node->sides[side].head) {
 821         output("segterminus");
 822         goto one_sided;
 823       }
 824     output("segjoin");
 825   one_sided:
 826     output("%d\n", (node->layermin + node->layermax)/2);
 827
 828     output("abs segjoin_%s %f %f %f\n",node->pname,
 829            node->x,node->y,node->a);
 830     FOR_NODE_EDGEENDS(side,edgeend, node) {
 831       segment= edgeend->edge->subseg->segment;
 832       if (segment->u & LSJ_U_SEGEND_DONE) continue;
 833       segment->u |= LSJ_U_SEGEND_DONE;
 834       assert(~segment->u & LSJ_U_VERTEXORDER_MASK); /* detect overflow */
 835       segment->u++;
 836       order= segment->u & LSJ_U_VERTEXORDER_MASK;
 837       if (order > max_order) max_order= order;
 838       output("segend segjoin_%s %s\n",node->pname, segment->segname);
 839     }
 840     output("\n");
 841     FOR_ALL_SEGMENTS(segmentp,segment)
 842       segment->u &= ~LSJ_U_SEGEND_DONE;
 843   }
 844
 845   /* Welsh and Powell's graph colouring algorithm
 846    * (Wikipedia Graph_coloring) */
 847   output("# max-order %d\n",max_order);
 848
 849   for (colour=LSJ_U_COLOUR_UNIT, any_left=1;
 850        any_left;
 851        colour+=LSJ_U_COLOUR_UNIT) {
 852     output("# colour %x\n", colour);
 853     assert(!(colour & ~LSJ_U_COLOUR_MASK));
 854    something_done:
 855     any_left= 0;
 856     FOR_ALL_SEGMENTS(segmentp,segment)
 857       segment->u &= ~LSJ_U_COLOUR_CLASH;
 858
 859     FOR_ALL_NODES(node)
 860       FOR_NODE_EDGEENDS(side,edgeend, node) {
 861         segment= edgeend->edge->subseg->segment;
 862         if (colour == (segment->u & LSJ_U_COLOUR_MASK)) {
 863           output("#  already %s\n", segment->segname);
 864           FOR_NODE_EDGEENDS(side2,edgeend2, node) {
 865             segment2= edgeend2->edge->subseg->segment;
 866             output("#   therefore-not %s\n", segment2->segname);
 867             segment2->u |= LSJ_U_COLOUR_CLASH;
 868           }
 869         }
 870       }
 871
 872     for (order=max_order; order>0; order--) { /* idiot-sort */
 873       output("#  order %d\n", order);
 874       FOR_ALL_SEGMENTS(segmentp,segment)
 875         if ((segment->u & LSJ_U_VERTEXORDER_MASK) == order) {
 876           if (segment->u & LSJ_U_COLOUR_MASK) continue;
 877           any_left= 1;
 878           if (segment->u & LSJ_U_COLOUR_CLASH) {
 879             output("#   still-clashes %s\n", segment->segname);
 880             continue;
 881           }
 882           segment->u |= colour;
 883           output("#   coloured %s\n", segment->segname);
 884           goto something_done;
 885         } else {
 886           output("# (skip %s %x)\n", segment->segname,segment->u);
 887         }
 888     }
 889   }
 890
 891   FOR_ALL_SEGMENTS(segmentp,segment) {
 892     int tcolour= segment->u & LSJ_U_COLOUR_MASK;
 893     const double val1=0.60, val2=0.35;
 894     double value;
 895     if (!tcolour) continue;
 896     value= val1 +
 897              (tcolour - LSJ_U_COLOUR_UNIT*2) * (val1-val2) /
 898              (colour - LSJ_U_COLOUR_UNIT*2);
 899     output("segcmap %s  %f setgray\n", segment->segname,value);
 900   }
 901   output("#line %d %s\n", __LINE__, __FILE__);
 902   output("ident\n");
 903 }
 904
 905 static void printforui(void) {
 906   Node *node;
 907   EdgeEnd *edgeend;
 908   int side;
 909
 910   FOR_ALL_NODES(node) {
 911     FOR_NODE_EDGEENDS(side,edgeend, node) {
 912       if (!edgeend->edge->subseg->movfeat) continue;
 913       output("layout-subseg-end %s %s %d %f %f\n",
 914              edgeend->edge->subseg->segment->segname,
 915              edgeend->edge->subseg->movfeat,
 916              edgeend->edge->movpos,
 917              node->x, node->y);
 918     }
 919   }
 920 }
 921
 922 /*---------- main program ----------*/
 923
 924 typedef struct {
 925   const char *name;
 926   void (*fn)(void);
 927 } OpInfo;
 928
 929 static const OpInfo opinfos[]= {
 930 #define OI(x) { #x, x },
 931   OI(printforneato)
 932   OI(printforneatosumm)
 933   OI(printforforsafety)
 934   OI(printforshellscript)
 935   OI(printforlayoutsegjoins)
 936   OI(printforui)
 937   OI(consistency)
 938   OI(movfeatsplitedges)
 939   OI(movfeatrmstubs)
 940   OI(movfeatsplitnodes)
 941   OI(movfeatsplitnodesall)
 942   OI(trivpairnodes)
 943   OI(trivnullnodes)
 944   { 0,0 }
 945 };
 946
 947 static void usage(void) {
 948   const OpInfo *oi;
 949
 950   fprintf(stderr,
 951           "usage: .../redactgraph [<options>] <operation> [<operation>...]\n"
 952           "options:\n"
 953           " -t<title>   title for neato (must have no metachars for \"...\")\n"
 954           "operations:\n");
 955   for (oi=opinfos; oi->name; oi++) {
 956     fprintf(stderr," %s\n",oi->name);
 957   }
 958   fflush(stderr);
 959   exit(8);
 960 }
 961
 962 int main(int argc, const char *const *argv) {
 963   const OpInfo *oi;
 964   const char *arg;
 965
 966   while ((arg= argv[1]) && arg[0]=='-') {
 967     if (!strcmp(arg,"-")) break;
 968     ++argv;
 969     if (!strcmp(arg,"--")) break;
 970     if (arg[1]=='t') { title= arg+2; }
 971     else { usage(); }
 972   }
 973
 974   if (!argv[0] || !argv[1]) usage();
 975
 976   while ((arg= *++argv)) {
 977     for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
 978     if (!oi->name) usage();
 979     oi->fn();
 980   }
 981   trace("\n");
 982   output("\n");
 983   if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }
 984   exit(0);
 985 }