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