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