layout/redactgraph.c

   1 /**/
   2
   3 #include <stdarg.h>
   4 #include <string.h>
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7 #include <assert.h>
   8 #include <errno.h>
   9
  10 #include "dlist.h"
  11 #include "graph-data.h"
  12
  13 #define MMALLOC(sz) mmalloc(sz,__FILE__,__LINE__)
  14 #define MREALLOC(p,sz) mrealloc(p,sz,__FILE__,__LINE__)
  15
  16 static void *mmalloccheck(void *p, const char *op, size_t sz,
  17                           const char *file, int line) {
  18   if (p) return p;
  19   fprintf(stderr,"%s:%d: %s of %lu failed: %s\n",
  20           file, line, op, (unsigned long)sz, strerror(errno));
  21   exit(16);
  22 }
  23
  24 static void *mmalloc(size_t sz, const char *file, int line) {
  25   void *p;
  26   if (!sz) return 0;
  27   p= malloc(sz);
  28   return mmalloccheck(p,"malloc",sz,file,line);
  29 }
  30
  31 static void *mrealloc(void *p, size_t sz, const char *file, int line) {
  32   p= realloc(p,sz);
  33   return mmalloccheck(p,"realloc",sz,file,line);
  34 }
  35
  36 static char *mvasprintf(const char *fmt, va_list al)
  37      __attribute__((format(printf,1,0)));
  38 static char *mvasprintf(const char *fmt, va_list al) {
  39   char *p;
  40   int r;
  41
  42   r= vasprintf(&p,fmt,al);
  43   if (r<0) {
  44     fprintf(stderr,"vasprintf(\"%s\",...) failed: %s\n",
  45             fmt, strerror(errno));
  46     exit(16);
  47   }
  48   return p;
  49 }
  50
  51 static char *masprintf(const char *fmt, ...)
  52      __attribute__((format(printf,1,2)));
  53 static char *masprintf(const char *fmt, ...) {
  54   va_list al;
  55   char *p;
  56   va_start(al,fmt);
  57   p= mvasprintf(fmt,al);
  58   va_end(al);
  59   return p;
  60 }
  61
  62 /*---------- output processing ----------*/
  63
  64 static void voutputstuff(int trace, const char *fmt, va_list al)
  65      __attribute__((format(printf,2,0)));
  66 static void voutputstuff(int trace, const char *fmt, va_list al) {
  67   static struct OutputBuf {
  68     int used, allocd;
  69     char *buf;
  70   } bufs[2];
  71
  72   struct OutputBuf *b;
  73   char *s, *p, *newline;
  74   int l;
  75
  76   b= &bufs[trace];
  77   s= mvasprintf(fmt,al);
  78   p= s;
  79
  80   for (;;) {
  81     newline= strchr(p,'\n');
  82     if (newline) { *newline= 0; }
  83     l= strlen(p);
  84     if (l+b->used > b->allocd) {
  85       b->allocd= l+b->used;
  86       b->buf= MREALLOC(b->buf, b->allocd);
  87     }
  88     memcpy(b->buf+b->used, p, l);
  89     b->used += l;
  90
  91     if (!newline) break;
  92
  93     if (trace) { fputs("# ",stdout); }
  94     fwrite(b->buf, 1,b->used, stdout);
  95     putc('\n',stdout);
  96     if (ferror(stdout) || fflush(stdout)) {
  97       perror("stdout voutputstuff"); exit(12);
  98     }
  99     b->used= 0;
 100     p= newline+1;
 101   }
 102
 103   free(s);
 104 }
 105
 106 #define OF(fn,tr)                                                           \
 107   static void v##fn(const char *fmt, va_list al)                            \
 108      __attribute__((format(printf,1,0)));                                   \
 109   static void v##fn(const char *fmt, va_list al) {                          \
 110     voutputstuff(tr,fmt,al);                                                \
 111   }                                                                         \
 112   static void fn(const char *fmt, ...) __attribute__((format(printf,1,2))); \
 113   static void fn(const char *fmt, ...) {                                    \
 114     va_list al;                                                             \
 115     va_start(al,fmt);                                                       \
 116     v##fn(fmt,al);                                                          \
 117     va_end(al);                                                             \
 118   }
 119 OF(output,0)
 120 OF(trace,1)
 121
 122 /*---------- traceing of various things ----------*/
 123
 124 static void trace_node(Node *node) {
 125   trace("n%s",node->pname);
 126 }
 127
 128 static void trace_nodeside(NodeSide *node) {
 129   trace("n%s %c",node->node->pname,"OI"[node->side]);
 130 }
 131
 132 static void trace_edge(Edge *edge) {
 133   trace("e%s",edge->pname);
 134 }
 135
 136 static void trace_edgeend(EdgeEnd *edge) {
 137   trace("e%s %c",edge->edge->pname,"OI"[edge->end]);
 138 }
 139
 140 static void trace_combpos(int combpos, Segment *seg) {
 141   int i, weight;
 142   MovFeat *f;
 143
 144   trace("*");
 145   weight= 1;
 146   FOR_SEGMENT_MOVFEATS(i,f,seg) {
 147     if (!f->movfeat) continue;
 148     trace("%s%d", f->movfeat, (combpos / weight) % f->n_positions);
 149     weight *= f->n_positions;
 150   }
 151 }
 152
 153 /*---------- general graph-manipulation tools ----------*/
 154
 155 static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
 156   return &thisend->edge->ends[!thisend->end];
 157 }
 158
 159 static int count_edges(const NodeSide *node) {
 160   int count;
 161   const EdgeEnd *edge;
 162
 163   for (count=0, edge=node->head;
 164        edge;
 165        count++, edge=edge->next);
 166   return count;
 167 }
 168
 169 static Edge *makeedge(const char *pname, double distance,
 170                       MovFeat *subseg, int movpos) {
 171   Edge *e;
 172   int end;
 173
 174   e= MMALLOC(sizeof(*e));
 175   e->pname= pname;
 176   e->distance= distance;
 177   e->subseg= subseg;
 178   e->movpos= movpos;
 179   FOR_BOTH(end) {
 180     e->ends[end].edge= e;
 181     e->ends[end].end= end;
 182   }
 183   trace("[new:"); trace_edge(e); trace("]");
 184   return e;
 185 }
 186
 187
 188 static void edgeend_detach(EdgeEnd *toremove) {
 189   trace("[detach:"); trace_edgeend(toremove);
 190   trace("-"); trace_nodeside(toremove->node); trace("]");
 191   LIST_UNLINK(*toremove->node, toremove);
 192 }
 193 static void edgeend_attach(EdgeEnd *toattach, NodeSide *newtarget) {
 194   trace("[attach:"); trace_edgeend(toattach);
 195   trace("-"); trace_nodeside(newtarget); trace("]");
 196   LIST_LINK_TAIL(*newtarget, toattach);
 197   toattach->node= newtarget;
 198 }
 199 static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) {
 200   edgeend_detach(tomove);
 201   edgeend_attach(tomove,newtarget);
 202 }
 203
 204 static void edge_delete(Edge *edge) {
 205   edgeend_detach(&edge->ends[0]);
 206   edgeend_detach(&edge->ends[1]);
 207   trace("[delete:"); trace_edge(edge); trace("]");
 208 }
 209
 210 static void node_surely_orphaned(Node *node) {
 211   trace("[nodeorphan:"); trace_node(node); trace("]");
 212   assert(!node->sides[0].head);
 213   assert(!node->sides[1].head);
 214   LIST_UNLINK(all_nodes, node);
 215 }
 216
 217 /*---------- operations ----------*/
 218
 219   /* We combine the individual moveable features in each segment into
 220    * a single `feature' with the cross-product of all of the
 221    * positions.  The new feature does not appear in
 222    * Segment->[n_]movfeats, but Edge->subseg and Edge->movpos are
 223    * updated (ie Edge->subseg->segment->movfeats is the original array
 224    * containing only the actual features, and so does not contain
 225    * Edge->subseg).  It is often printed as if its name was `*' (which
 226    * is not legal in input files etc.).  The positions of the
 227    * *-feature are numbered according to the obvious arithmetic coding
 228    * of the individual actual feature positions.  See also
 229    * hostside/safety.h.
 230    *
 231    * The conversion has two stages:
 232    *
 233    * FIRST STAGE (movfeatmultedges):
 234    *
 235    * We multiply up each edge of any segment with moveable features to
 236    * be an edge which is a position of the *-feature.
 237    *
 238    * For example, if segment A1 has feature P with states 0 and 1
 239    * and feature J with states 0 and 1, then the edges are translated
 240    * as follows
 241    *   old edge    new edges
 242    *    A1          A1/P0J0 A1/P0J1 A1/P1J0 A1/P1J1
 243    *    A1/P0       A1/P0J0 A1/P0J1
 244    *    A1/P1                       A1/P1J0 A1/P1J1
 245    *    A1/J0       A1/P0J0         A1/P1J0
 246    *    A1/J1               A1/P0J1         A1/P1J1
 247    * Eg,
 248    *     *----A1/P0----*   becomes   *----A1/P0J0----*
 249    *                                  `---A1/P0J1---'
 250    *
 251    * SECOND STAGE:
 252    *
 253    * We split nodes: every node which has (only) edges which are part
 254    * of the same segment is split into one node for each position and
 255    * direction (directions are end0-to-side0+end1-to-side1 and
 256    * end0-to-side1+end1-to-side0), to which the corresponding edges
 257    * are connected.  Any resulting node which has only one edge is
 258    * removed together with the edge.
 259    *
 260    * For example, when we start with:
 261    *
 262    *     ,---A1/P0J0---.
 263    * ...*----A1/P0J1----*---A1/P0J1---*...
 264    *     `---A1/P1J0---' `--A1/P1J1--'
 265    *      `--A1/P1J1--'
 266    *
 267    * the middle node is split like this (neglecting directions for
 268    * clarity):
 269    *
 270    *     ,---A1/P0J0----*
 271    * ...*----A1/P0J1----*---A1/P0J1---*...
 272    *     `---A1/P1J0----*            /
 273    *      `--A1/P1J1----*---A1/P1J1-'
 274    *
 275    * and then the stub edges and nodes are removed, leaving this:
 276    *
 277    * ...*----A1/P0J1----*---A1/P0J1---*...
 278    *     \                           /
 279    *      `--A1/P1J1----*---A1/P1J1-'
 280    *
 281    * The actual implementation of the second stage simply considers
 282    * whether to create each node as it goes along, rather than
 283    * inventing nodes merely to delete them.
 284    */
 285
 286 static void movfeatmultedges(void) {
 287   Node *node;
 288   int side, l, i, weight, combpos, end;
 289   EdgeEnd *edgeend;
 290   Edge *edge, *newedge;
 291   Segment *segment;
 292   MovFeat *subseg, *starfeature, *loopfeat;
 293   char *featstr;
 294
 295   trace("movfeatmultedges ...\n");
 296   FOR_ALL_NODES(node) {
 297     FOR_EDGES(edge, node,side,edgeend) {
 298       subseg= edge->subseg;
 299       segment= subseg->segment;
 300
 301       trace("movfeatmultedges "); trace_edge(edge);
 302       trace(" segment %s ", segment->segname);
 303       if (segment->n_movfeats<=1) { trace("no moveables\n"); continue; }
 304       if (subseg == segment->starfeature) { trace("*-feature\n"); continue; }
 305
 306       starfeature= segment->starfeature;
 307       if (starfeature) {
 308         trace("old");
 309       } else {
 310         trace("new");
 311         starfeature= MMALLOC(sizeof(*starfeature));
 312         starfeature->segment= segment;
 313
 314         l=2;  starfeature->n_positions=1;
 315         FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
 316           if (!loopfeat->movfeat) continue;
 317           l += strlen(loopfeat->movfeat);
 318           starfeature->n_positions *= loopfeat->n_positions;
 319         }
 320
 321         starfeature->movfeat= featstr= MMALLOC(l);
 322         strcpy(featstr, "*");
 323
 324         FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
 325           if (!loopfeat->movfeat) continue;
 326           strcat(featstr, loopfeat->movfeat);
 327         }
 328
 329         segment->starfeature= starfeature;
 330       }
 331       trace(" %s(%d) ", starfeature->movfeat, starfeature->n_positions);
 332
 333       if (subseg->movfeat) {
 334         weight= 1;
 335         FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
 336           if (loopfeat == subseg) goto found;
 337           weight *= loopfeat->n_positions;
 338         }
 339         abort();
 340       found:
 341         trace("%s(x%d)",subseg->movfeat,weight);
 342       } else {
 343         weight= 1;
 344         trace("fixed");
 345       }
 346
 347       trace(" ...\n");
 348
 349       for (combpos=0; combpos<starfeature->n_positions; combpos++) {
 350         trace("movfeatmultedges  "); trace_combpos(combpos,segment);
 351         if ((combpos / weight) % subseg->n_positions != edge->movpos) {
 352           trace(" excluded\n");
 353           continue;
 354         }
 355         newedge= makeedge(masprintf("%s/*%d",edge->pname,combpos),
 356                           edge->distance,
 357                           starfeature,
 358                           combpos);
 359         FOR_BOTH(end)
 360           edgeend_attach(&newedge->ends[end], edge->ends[end].node);
 361       }
 362       edge_delete(edge);
 363       /* edge_delete doesn't destroy or modify this edge node,
 364        * so we can safely carry on with this loop, which will
 365        * now carry on with the next edge - either one we've just
 366        * added, or the one which was next before we started messing
 367        * about.
 368        */
 369     }
 370   }
 371   trace("movfeatmultedges complete.\n");
 372 }
 373
 374 static void elimtrivial(void) {
 375   /* Eliminate trivial nodes: ones which have only two edges, which
 376    * come in on opposite sides, have the same subsegspec, and with the
 377    * two ends identically aligned.
 378    */
 379   EdgeEnd *leftedge, *rightedge;
 380   Node *node, *next_node;
 381
 382   FOR_ALL_NODES(node) {
 383     next_node=node->next;
 384     trace("elimtrivial node "); trace_node(node); trace(" ");
 385     if (!(count_edges(&node->sides[0])==1 &&
 386           count_edges(&node->sides[1])==1)) {
 387       trace("no, a non-unitary side\n");
 388       continue;
 389     }
 390     leftedge= node->sides[0].head;
 391     rightedge= node->sides[1].head;
 392     if (leftedge->edge->subseg != rightedge->edge->subseg) {
 393       trace("no, (sub)segments differ\n");
 394       continue;
 395     }
 396     if (leftedge->edge->movpos != rightedge->edge->movpos) {
 397       trace("no, movpos's differ\n");
 398       continue;
 399     }
 400     if (leftedge->end == rightedge->end) {
 401       trace("no, opposite alignment\n");
 402       continue;
 403     }
 404     trace(" yes:\n");
 405     rightedge->edge->distance += leftedge->edge->distance;
 406     edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
 407     edge_delete(leftedge->edge);
 408     node_surely_orphaned(node);
 409     trace(" elimtrivial operation complete\n");
 410   }
 411 }
 412
 413 static void check(const char *why) {
 414   Node *node;
 415   int alloc_edone, used_edone;
 416   typedef struct { Edge *edge; int endsdone; } EdgeDone;
 417   EdgeDone *edone, *search_edone;
 418   int side;
 419   EdgeEnd *edgeend;
 420   Edge *edge;
 421
 422   edone= 0;
 423   alloc_edone= used_edone= 0;
 424
 425   trace("consistency check (%s) ...\n",why);
 426   FOR_ALL_NODES(node) {
 427     trace(" consistency "); trace_node(node); trace("\n");
 428     LIST_CHECKNODE(all_nodes,node);
 429     FOR_BOTH(side) {
 430       trace(" consistency "); trace_nodeside(&node->sides[side]); trace("\n");
 431       assert(node->sides[side].node == node);
 432       assert(node->sides[side].side == side);
 433       for (edgeend=node->sides[side].head; edgeend; edgeend=edgeend->next) {
 434         trace(" consistency "); trace_nodeside(&node->sides[side]);
 435         trace(" "); trace_edgeend(edgeend); trace("\n");
 436
 437         edge= edgeend->edge;
 438         LIST_CHECKNODE(node->sides[side], edgeend);
 439         assert(edgeend == &edge->ends[edgeend->end]);
 440         assert(edgeend->node == &node->sides[side]);
 441         if (used_edone==alloc_edone) {
 442           alloc_edone += 2; alloc_edone *= 2;
 443           edone= MREALLOC(edone, alloc_edone * sizeof(*edone));
 444         }
 445         for (search_edone= edone;
 446              search_edone < edone + used_edone && search_edone->edge != edge;
 447              search_edone++);
 448         if (search_edone >= edone + used_edone) {
 449           search_edone->edge= edge;
 450           search_edone->endsdone= 0;
 451           used_edone++;
 452         }
 453         search_edone->endsdone++;
 454         assert(search_edone->endsdone <= 2);
 455       }
 456     }
 457   }
 458   for (search_edone= edone;
 459        search_edone < edone + used_edone;
 460        search_edone++) {
 461     trace("consistency "); trace_edge(search_edone->edge);
 462     trace(" count=%d\n", search_edone->endsdone);
 463     assert(search_edone->endsdone == 2);
 464   }
 465   trace("consistency check (%s) ok\n",why);
 466 }
 467
 468 static void consistency(void) {
 469   check("command-line request");
 470 }
 471
 472 static void printforneato(void) {
 473   Node *node;
 474   EdgeEnd *edgeend;
 475   Edge *edge;
 476   int side;
 477
 478   output("digraph L {\n");
 479
 480   FOR_ALL_NODES(node) {
 481     output("  n%sO [label=\"%s\"];\n"
 482            "  n%sI [label=\"+\"];\n",
 483            node->pname, node->pname, node->pname);
 484     output("  n%sO -> n%sI [len=0.25 arrowsize=0];\n",
 485            node->pname, node->pname);
 486     FOR_EDGES(edge, node,side,edgeend) {
 487       output("  n%s%c -> n%s%c [label=\"%s:",
 488              edge->ends[0].node->node->pname,
 489              "OI"[edge->ends[0].node->side],
 490              edge->ends[1].node->node->pname,
 491              "OI"[edge->ends[1].node->side],
 492              edge->pname);
 493       if (!edge->subseg->segment->segname) {
 494         output("?");
 495       } else {
 496         output(edge->subseg->segment->segname);
 497         if (edge->subseg->movfeat) {
 498           output("/%s%d",edge->subseg->movfeat,edge->movpos);
 499         }
 500       }
 501       output(":%.2f\"];\n",edge->distance);
 502     }
 503   }
 504   output("}\n");
 505 }
 506
 507 typedef struct {
 508   const char *name;
 509   void (*fn)(void);
 510 } OpInfo;
 511
 512 static const OpInfo opinfos[]= {
 513 #define OI(x) { #x, x },
 514   OI(printforneato)
 515   OI(consistency)
 516   OI(movfeatmultedges)
 517   OI(elimtrivial)
 518   { 0,0 }
 519 };
 520
 521 static void usage(void) {
 522   const OpInfo *oi;
 523
 524   fprintf(stderr,
 525           "usage: .../redactgraph <operation> [<operation>...]\n"
 526           "operations:\n");
 527   for (oi=opinfos; oi->name; oi++) {
 528     fprintf(stderr," %s\n",oi->name);
 529   }
 530   fflush(stderr);
 531   exit(8);
 532 }
 533
 534 int main(int argc, const char *const *argv) {
 535   const OpInfo *oi;
 536   const char *arg;
 537
 538   if (!argv[0] || !argv[1]) usage();
 539
 540   while ((arg= *++argv)) {
 541     for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
 542     if (!oi->name) usage();
 543     oi->fn();
 544   }
 545   trace("\n");
 546   output("\n");
 547   if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }
 548   exit(0);
 549 }