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
   9 #include "dlist.h"
  10 #include "graph-data.h"
  11
  12 /*---------- output processing ----------*/
  13
  14 static void voutputstuff(int trace, const char *fmt, va_list al) {
  15   static struct OutputBuf {
  16     int used, allocd;
  17     char *buf;
  18   } bufs[2];
  19
  20   struct OutputBuf *b;
  21   char *s, *p, *newline;
  22   int r, l;
  23
  24   b= &bufs[trace];
  25   r= vasprintf(&s,fmt,al);  if (r<0) { perror("vasprintf"); exit(16); }
  26   p= s;
  27
  28   for (;;) {
  29     newline= strchr(p,'\n');
  30     if (newline) { *newline= 0; }
  31     l= strlen(p);
  32     if (l+b->used > b->allocd) {
  33       b->allocd= l+b->used;
  34       b->buf= realloc(b->buf, b->allocd);
  35       if (!b->buf) { perror("realloc voutputstuff"); exit(16); }
  36     }
  37     memcpy(b->buf+b->used, p, l);
  38     b->used += l;
  39
  40     if (!newline) break;
  41
  42     if (trace) { fputs("# ",stdout); }
  43     fwrite(b->buf, 1,b->used, stdout);
  44     putc('\n',stdout);
  45     if (ferror(stdout) || fflush(stdout)) {
  46       perror("stdout voutputstuff"); exit(12);
  47     }
  48     b->used= 0;
  49     p= newline+1;
  50   }
  51
  52   free(s);
  53 }
  54
  55 #define OF(fn,tr)                                       \
  56   static void v##fn(const char *fmt, va_list al) {      \
  57     voutputstuff(tr,fmt,al);                            \
  58   }                                                     \
  59   static void fn(const char *fmt, ...) {                \
  60     va_list al;                                         \
  61     va_start(al,fmt);                                   \
  62     v##fn(fmt,al);                                      \
  63     va_end(al);                                         \
  64   }
  65 OF(output,0)
  66 OF(trace,1)
  67
  68 /*---------- general graph-manipulation and printing stuff ----------*/
  69
  70 static void trace_node(Node *node) {
  71   trace("node%d",node->nodenum);
  72 }
  73
  74 static void trace_edgeend(EdgeEnd *edge) {
  75   trace("edge%d %c",edge->edge->edgenum,"OI"[edge->end]);
  76 }
  77
  78 static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
  79   return &thisend->edge->ends[!thisend->end];
  80 }
  81
  82 static int count_edges(const NodeSide *node) {
  83   int count;
  84   const EdgeEnd *edge;
  85
  86   for (count=0, edge=node->head;
  87        edge;
  88        count++, edge=edge->next);
  89   return count;
  90 }
  91
  92 static void edgeend_disconnect(EdgeEnd *toremove) {
  93   LIST_UNLINK(*toremove->node, toremove);
  94 }
  95
  96 static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) {
  97   edgeend_disconnect(tomove);
  98   LIST_LINK_TAIL(*newtarget, tomove);
  99   tomove->node= newtarget;
 100 }
 101
 102 static void edge_delete(Edge *edge) {
 103   edgeend_disconnect(&edge->ends[0]);
 104   edgeend_disconnect(&edge->ends[1]);
 105 }
 106
 107 static void node_surely_orphaned(Node *node) {
 108   assert(!node->sides[0].head);
 109   assert(!node->sides[1].head);
 110   LIST_UNLINK(all_nodes, node);
 111 }
 112
 113 /*---------- operations ----------*/
 114
 115 static void extendsplits(void) {
 116   int pass=0, rightside, n;
 117   Node *node;
 118   EdgeEnd *leftedge, *rightedge;
 119
 120   /*
 121    * Whenever we have a node which has one or more moveable feature
 122    * subsegments, part of the same moveable feature, on one side, and
 123    * fixed portion of the same segment on the other, we eliminate
 124    * the fixed portion and add its length to both the moveables,
 125    * so that we have one subsegspec for the whole of each position:
 126    *
 127    *    <---l---> <----l'--->             <---------(l+l')------>
 128    *
 129    *   *----A1---*----A1/P0--*  becomes  *--------A1/P0----------*
 130    *              `---A1/P1---*           `-------A1/P1-----------*
 131    *
 132    *              <----l''--->            <---------(l+l'')------>
 133    */
 134
 135   for (;;) {
 136     pass++;
 137     for (node=all_nodes.head; node; node=node->next) {
 138       for (rightside=0; rightside<2; rightside++) {
 139         trace("extendsplit pass %d node ",pass); trace_node(node);
 140         trace("/%d ",rightside);
 141         if ((n= count_edges(&node->sides[!rightside])) != 1) {
 142           trace("no: lhs edges=%d\n", n);
 143           goto no_extend_this;
 144         }
 145         leftedge= node->sides[!rightside].head;
 146         if (leftedge->edge->subseg->movfeat) {
 147           trace("no: lhs moveable\n");
 148           goto no_extend_this;
 149         }
 150         if (!node->sides[rightside].head) {
 151           trace("no: rhs absent\n");
 152           goto no_extend_this;
 153         }
 154         for (rightedge= node->sides[rightside].head;
 155              rightedge;
 156              rightedge= rightedge->next) {
 157           if (!rightedge->edge->subseg->movfeat) {
 158             trace("no: rhs fixed ("); trace_edgeend(rightedge); trace(")\n");
 159             goto no_extend_this;
 160           }
 161           if (leftedge->edge->subseg->segment !=
 162               rightedge->edge->subseg->segment) {
 163             trace("no: lhs seg %s, rhs seg %s (",
 164                   leftedge->edge->subseg->segment->segname,
 165                   rightedge->edge->subseg->segment->segname);
 166             trace_edgeend(rightedge); trace(")\n");
 167             goto no_extend_this;
 168           }
 169         }
 170         goto extend_this;
 171
 172       no_extend_this:;
 173       }
 174     }
 175     return;
 176
 177   extend_this:
 178     trace("yes, lhs "); trace_edgeend(leftedge); trace(":\n");
 179     for (rightedge= node->sides[rightside].head;
 180          rightedge;
 181          rightedge= rightedge->next) {
 182       rightedge->edge->distance += leftedge->edge->distance;
 183       edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
 184     }
 185     edge_delete(leftedge->edge);
 186     node_surely_orphaned(node);
 187     trace(" extendsplit operation complete\n");
 188   }
 189 }
 190
 191 static void elimtrivial(void) {
 192   /* Eliminate trivial nodes: ones which have only two edges, which
 193    * come in on opposite sides, have the same subsegspec, and with the
 194    * two ends identically aligned.
 195    */
 196   EdgeEnd *leftedge, *rightedge;
 197   Node *node, *next_node;
 198
 199   for (node=all_nodes.head; node; node=next_node) {
 200     next_node=node->next;
 201     trace("elimtrivial node "); trace_node(node); trace(" ");
 202     if (!(count_edges(&node->sides[0])==1 &&
 203           count_edges(&node->sides[1])==1)) {
 204       trace("no, a non-unitary side\n");
 205       continue;
 206     }
 207     leftedge= node->sides[0].head;
 208     rightedge= node->sides[1].head;
 209     if (leftedge->edge->subseg != rightedge->edge->subseg) {
 210       trace("no, (sub)segments differ\n");
 211       continue;
 212     }
 213     if (leftedge->edge->movpos != rightedge->edge->movpos) {
 214       trace("no, movpos's differ\n");
 215       continue;
 216     }
 217     if (leftedge->end == rightedge->end) {
 218       trace("no, opposite alignment\n");
 219       continue;
 220     }
 221     trace(" yes:\n");
 222     rightedge->edge->distance += leftedge->edge->distance;
 223     edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
 224     edge_delete(leftedge->edge);
 225     node_surely_orphaned(node);
 226     trace(" elimtrivial operation complete\n");
 227   }
 228 }
 229
 230 static void check(const char *why) {
 231   Node *node;
 232   int alloc_edone, used_edone;
 233   typedef struct { Edge *edge; int endsdone; } EdgeDone;
 234   EdgeDone *edone, *search_edone;
 235   int side;
 236   EdgeEnd *edgeend;
 237   Edge *edge;
 238
 239   edone= 0;
 240   alloc_edone= used_edone= 0;
 241
 242   trace("consistency check (%s) ...\n",why);
 243   for (node=all_nodes.head; node; node=node->next) {
 244     trace(" consistency node%d\n", node->nodenum);
 245     LIST_CHECKNODE(all_nodes,node);
 246     for (side=0; side<2; side++) {
 247       trace(" consistency node%d %c\n", node->nodenum, "OI"[side]);
 248       assert(node->sides[side].node == node);
 249       assert(node->sides[side].side == side);
 250       for (edgeend=node->sides[side].head; edgeend; edgeend=edgeend->next) {
 251         trace(" consistency node%d %c ", node->nodenum, "OI"[side]);
 252         trace_edgeend(edgeend);
 253         trace("\n");
 254
 255         edge= edgeend->edge;
 256         LIST_CHECKNODE(node->sides[side], edgeend);
 257         assert(edgeend == &edge->ends[edgeend->end]);
 258         assert(edgeend->node == &node->sides[side]);
 259         if (used_edone==alloc_edone) {
 260           alloc_edone += 2; alloc_edone *= 2;
 261           edone= realloc(edone, alloc_edone * sizeof(*edone));
 262           if (!edone) { perror("realloc check edone"); exit(16); }
 263         }
 264         for (search_edone= edone;
 265              search_edone < edone + used_edone && search_edone->edge != edge;
 266              search_edone++);
 267         if (search_edone >= edone + used_edone) {
 268           search_edone->edge= edge;
 269           search_edone->endsdone= 0;
 270           used_edone++;
 271         }
 272         search_edone->endsdone++;
 273         assert(search_edone->endsdone <= 2);
 274       }
 275     }
 276   }
 277   for (search_edone= edone;
 278        search_edone < edone + used_edone;
 279        search_edone++) {
 280     trace("consistency edge%d count=%d\n",
 281           search_edone->edge, search_edone->endsdone);
 282     assert(search_edone->endsdone == 2);
 283   }
 284   trace("consistency check (%s) ok\n",why);
 285 }
 286
 287 static void consistency(void) {
 288   check("command-line request");
 289 }
 290
 291 static void printforneato(void) {
 292   Node *node;
 293   EdgeEnd *edgeend;
 294   Edge *edge;
 295   int side;
 296
 297   output("digraph L {\n");
 298
 299   for (node=all_nodes.head; node; node=node->next) {
 300     output("  n%dO [label=\"%d\"];\n"
 301            "  n%dI [label=\"+\"];\n",
 302            node->nodenum, node->nodenum, node->nodenum);
 303     output("  n%dO -> n%dI [len=0.25 arrowsize=0];\n",
 304            node->nodenum, node->nodenum);
 305     for (side=0; side<2; side++) {
 306       for (edgeend=node->sides[side].head; edgeend; edgeend=edgeend->next) {
 307         if (edgeend->end) continue; /* do each edge once, from end 0, only */
 308         edge= edgeend->edge;
 309         output("  n%d%c -> n%d%c [label=\"%d:",
 310                edge->ends[0].node->node->nodenum,
 311                "OI"[edge->ends[0].node->side],
 312                edge->ends[1].node->node->nodenum,
 313                "OI"[edge->ends[1].node->side],
 314                edge->edgenum);
 315         if (!edge->subseg->segment->segname) {
 316           output("?");
 317         } else {
 318           output(edge->subseg->segment->segname);
 319           if (edge->subseg->movfeat) {
 320             output("/%s%d",edge->subseg->movfeat,edge->movpos);
 321           }
 322         }
 323         output(":%.2f\"];\n",edge->distance);
 324       }
 325     }
 326   }
 327   output("}\n");
 328 }
 329
 330 typedef struct {
 331   const char *name;
 332   void (*fn)(void);
 333 } OpInfo;
 334
 335 static const OpInfo opinfos[]= {
 336 #define OI(x) { #x, x },
 337   OI(printforneato)
 338   OI(consistency)
 339   OI(extendsplits)
 340   OI(elimtrivial)
 341   { 0,0 }
 342 };
 343
 344 static void usage(void) {
 345   const OpInfo *oi;
 346
 347   fprintf(stderr,
 348           "usage: .../redactgraph <operation> [<operation>...]\n"
 349           "operations:\n");
 350   for (oi=opinfos; oi->name; oi++) {
 351     fprintf(stderr," %s\n",oi->name);
 352   }
 353   fflush(stderr);
 354   exit(8);
 355 }
 356
 357 int main(int argc, const char *const *argv) {
 358   const OpInfo *oi;
 359   const char *arg;
 360
 361   if (!argv[0] || !argv[1]) usage();
 362
 363   while ((arg= *++argv)) {
 364     for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
 365     if (!oi->name) usage();
 366     oi->fn();
 367   }
 368   trace("\n");
 369   output("\n");
 370   if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }
 371   exit(0);
 372 }