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("n%p",node);
  72 }
  73
  74 static void trace_edgeend(EdgeEnd *edge) {
  75   trace("n%p%c",edge->node->node,"OI"[edge->node->side]);
  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, 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[0].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 consistency(void) {
 231 }
 232
 233 static void printforneato(void) {
 234   Node *node;
 235   EdgeEnd *edgeend;
 236   Edge *edge;
 237   int side;
 238
 239   output("digraph L {\n");
 240
 241   for (node=all_nodes.head; node; node=node->next) {
 242     output("  n%pO [label=\"O\"];\n"
 243            "  n%pI [label=\"+\"];\n",
 244            node, node);
 245     output("  n%pO -> n%pI [len=0.25 arrowsize=0];\n",
 246            node, node);
 247     for (side=0; side<2; side++) {
 248       for (edgeend=node->sides[side].head; edgeend; edgeend=edgeend->next) {
 249         if (edgeend->end) continue; /* do each edge once, from end 0, only */
 250         edge= edgeend->edge;
 251         output("  n%p%c -> n%p%c [label=\"",
 252                edge->ends[0].node->node, "OI"[edge->ends[0].node->side],
 253                edge->ends[1].node->node, "OI"[edge->ends[1].node->side]);
 254         if (!edge->subseg->segment->segname) {
 255           output("?");
 256         } else {
 257           output(edge->subseg->segment->segname);
 258           if (edge->subseg->movfeat) {
 259             output("/%s%d",edge->subseg->movfeat,edge->movpos);
 260           }
 261         }
 262         output("\"];\n");
 263       }
 264     }
 265   }
 266   output("}\n");
 267 }
 268
 269 typedef struct {
 270   const char *name;
 271   void (*fn)(void);
 272 } OpInfo;
 273
 274 static const OpInfo opinfos[]= {
 275 #define OI(x) { #x, x },
 276   OI(printforneato)
 277   OI(consistency)
 278   OI(extendsplits)
 279   OI(elimtrivial)
 280   { 0,0 }
 281 };
 282
 283 static void usage(void) {
 284   const OpInfo *oi;
 285
 286   fprintf(stderr,
 287           "usage: .../redactgraph <operation> [<operation>...]\n"
 288           "operations:\n");
 289   for (oi=opinfos; oi->name; oi++) {
 290     fprintf(stderr," %s\n",oi->name);
 291   }
 292   fflush(stderr);
 293   exit(8);
 294 }
 295
 296 int main(int argc, const char *const *argv) {
 297   const OpInfo *oi;
 298   const char *arg;
 299
 300   if (!argv[0] || !argv[1]) usage();
 301
 302   while ((arg= *++argv)) {
 303     for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
 304     if (!oi->name) usage();
 305     oi->fn();
 306   }
 307   trace("\n");
 308   output("\n");
 309   if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }
 310   exit(0);
 311 }