layout/redactgraph.c

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