11 #include "graph-data.h"
13 #define MMALLOC(sz) mmalloc(sz,__FILE__,__LINE__)
14 #define MREALLOC(p,sz) mrealloc(p,sz,__FILE__,__LINE__)
16 static void *mmalloccheck(void *p, const char *op, size_t sz,
17 const char *file, int line) {
19 fprintf(stderr,"%s:%d: %s of %lu failed: %s\n",
20 file, line, op, (unsigned long)sz, strerror(errno));
24 static void *mmalloc(size_t sz, const char *file, int line) {
28 return mmalloccheck(p,"malloc",sz,file,line);
31 static void *mrealloc(void *p, size_t sz, const char *file, int line) {
33 return mmalloccheck(p,"realloc",sz,file,line);
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) {
42 r= vasprintf(&p,fmt,al);
44 fprintf(stderr,"vasprintf(\"%s\",...) failed: %s\n",
45 fmt, strerror(errno));
51 static char *masprintf(const char *fmt, ...)
52 __attribute__((format(printf,1,2)));
53 static char *masprintf(const char *fmt, ...) {
57 p= mvasprintf(fmt,al);
62 /*---------- output processing ----------*/
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 {
73 char *s, *p, *newline;
77 s= mvasprintf(fmt,al);
81 newline= strchr(p,'\n');
82 if (newline) { *newline= 0; }
84 if (l+b->used > b->allocd) {
86 b->buf= MREALLOC(b->buf, b->allocd);
88 memcpy(b->buf+b->used, p, l);
93 if (trace) { fputs("# ",stdout); }
94 fwrite(b->buf, 1,b->used, stdout);
96 if (ferror(stdout) || fflush(stdout)) {
97 perror("stdout voutputstuff"); exit(12);
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); \
112 static void fn(const char *fmt, ...) __attribute__((format(printf,1,2))); \
113 static void fn(const char *fmt, ...) { \
122 /*---------- traceing of various things ----------*/
124 static void trace_node(Node *node) {
125 trace("n%s",node->pname);
128 static void trace_nodeside(NodeSide *node) {
129 trace("n%s %c",node->node->pname,"OI"[node->side]);
132 static void trace_edge(Edge *edge) {
133 trace("e%s",edge->pname);
136 static void trace_edgeend(EdgeEnd *edge) {
137 trace("e%s %c",edge->edge->pname,"OI"[edge->end]);
140 static void trace_combpos(int combpos, Segment *seg) {
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;
153 /*---------- general graph-manipulation tools ----------*/
155 static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
156 return &thisend->edge->ends[!thisend->end];
159 static int count_edges(const NodeSide *node) {
163 for (count=0, edge=node->head;
165 count++, edge=edge->next);
169 static Edge *makeedge(const char *pname, double distance,
170 MovFeat *subseg, int movpos) {
174 e= MMALLOC(sizeof(*e));
176 e->distance= distance;
180 e->ends[end].edge= e;
181 e->ends[end].end= end;
183 trace("[new:"); trace_edge(e); trace("]");
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);
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;
199 static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) {
200 edgeend_detach(tomove);
201 edgeend_attach(tomove,newtarget);
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("]");
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);
217 /*---------- operations ----------*/
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
231 * The conversion has two stages:
233 * FIRST STAGE (movfeatmultedges):
235 * We multiply up each edge of any segment with moveable features to
236 * be an edge which is a position of the *-feature.
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
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
248 * *----A1/P0----* becomes *----A1/P0J0----*
253 * We remove stub moveable edges: whenever, at a node which has only
254 * edges which are part of the same segment, we find an edge on one
255 * side in which is not matched exactly (moveable feature settings
256 * and direction) by an edge on the other side, we delete that extra
259 * is split into one node
260 * for each position and direction (directions are
261 * end0-to-side0+end1-to-side1 and end0-to-side1+end1-to-side0), to
262 * which the corresponding edges are connected. Any resulting node
263 * which has only one edge is removed together with the edge.
265 * For example (neglecting direction for the purposes of the
266 * example), when we start with:
269 * ...*----A1/P0J1----*---A1/P0J1---*...
270 * `---A1/P1J0---' `--A1/P1J1--'
273 * the edges A1/P0J0 and A1/P1J1 are not matched on the RHS of the node,
274 * so they are removed:
276 * ...*----A1/P0J1----*---A1/P0J1---*...
277 * `---A1/P1J0---' `--A1/P1J1--'
282 * We split nodes: every node which has only edges which are part of
283 * the same segment is split into one node for each kind of edge
284 * which goes through it. The 2nd stage ensures that this is always
287 * Our example above turns into:
289 * ...*----A1/P0J1----*---A1/P0J1---*...
290 * `---A1/P1J0----*---A1/P1J1--'
293 static void movfeatmultedges(void) {
295 int side, l, i, weight, combpos, end;
297 Edge *edge, *newedge;
299 MovFeat *subseg, *starfeature, *loopfeat;
302 trace("movfeatmultedges ...\n");
303 FOR_ALL_NODES(node) {
304 FOR_EDGES(edge, node,side,edgeend) {
305 subseg= edge->subseg;
306 segment= subseg->segment;
308 trace("movfeatmultedges "); trace_edge(edge);
309 trace(" segment %s ", segment->segname);
310 if (segment->n_movfeats<=1) { trace("no moveables\n"); continue; }
311 if (subseg == segment->starfeature) { trace("*-feature\n"); continue; }
313 starfeature= segment->starfeature;
318 starfeature= MMALLOC(sizeof(*starfeature));
319 starfeature->segment= segment;
321 l=2; starfeature->n_positions=1;
322 FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
323 if (!loopfeat->movfeat) continue;
324 l += strlen(loopfeat->movfeat);
325 starfeature->n_positions *= loopfeat->n_positions;
328 starfeature->movfeat= featstr= MMALLOC(l);
329 strcpy(featstr, "*");
331 FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
332 if (!loopfeat->movfeat) continue;
333 strcat(featstr, loopfeat->movfeat);
336 segment->starfeature= starfeature;
338 trace(" %s(%d) ", starfeature->movfeat, starfeature->n_positions);
340 if (subseg->movfeat) {
342 FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
343 if (loopfeat == subseg) goto found;
344 weight *= loopfeat->n_positions;
348 trace("%s(x%d)",subseg->movfeat,weight);
356 for (combpos=0; combpos<starfeature->n_positions; combpos++) {
357 trace("movfeatmultedges "); trace_combpos(combpos,segment);
358 if ((combpos / weight) % subseg->n_positions != edge->movpos) {
359 trace(" excluded\n");
362 newedge= makeedge(masprintf("%s/*%d",edge->pname,combpos),
367 edgeend_attach(&newedge->ends[end], edge->ends[end].node);
370 /* edge_delete doesn't destroy or modify this edge node,
371 * so we can safely carry on with this loop, which will
372 * now carry on with the next edge - either one we've just
373 * added, or the one which was next before we started messing
378 trace("movfeatmultedges complete.\n");
381 static void elimtrivial(void) {
382 /* Eliminate trivial nodes: ones which have only two edges, which
383 * come in on opposite sides, have the same subsegspec, and with the
384 * two ends identically aligned.
386 EdgeEnd *leftedge, *rightedge;
387 Node *node, *next_node;
389 FOR_ALL_NODES(node) {
390 next_node=node->next;
391 trace("elimtrivial node "); trace_node(node); trace(" ");
392 if (!(count_edges(&node->sides[0])==1 &&
393 count_edges(&node->sides[1])==1)) {
394 trace("no, a non-unitary side\n");
397 leftedge= node->sides[0].head;
398 rightedge= node->sides[1].head;
399 if (leftedge->edge->subseg != rightedge->edge->subseg) {
400 trace("no, (sub)segments differ\n");
403 if (leftedge->edge->movpos != rightedge->edge->movpos) {
404 trace("no, movpos's differ\n");
407 if (leftedge->end == rightedge->end) {
408 trace("no, opposite alignment\n");
412 rightedge->edge->pname=
413 masprintf("%s+%s", leftedge->edge->pname, rightedge->edge->pname);
414 rightedge->edge->distance += leftedge->edge->distance;
415 edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
416 edge_delete(leftedge->edge);
417 node_surely_orphaned(node);
418 trace(" elimtrivial operation complete\n");
422 static void check(const char *why) {
424 int alloc_edone, used_edone;
425 typedef struct { Edge *edge; int endsdone; } EdgeDone;
426 EdgeDone *edone, *search_edone;
432 alloc_edone= used_edone= 0;
434 trace("consistency check (%s) ...\n",why);
435 FOR_ALL_NODES(node) {
436 trace(" consistency "); trace_node(node); trace("\n");
437 LIST_CHECKNODE(all_nodes,node);
439 trace(" consistency "); trace_nodeside(&node->sides[side]); trace("\n");
440 assert(node->sides[side].node == node);
441 assert(node->sides[side].side == side);
442 for (edgeend=node->sides[side].head; edgeend; edgeend=edgeend->next) {
443 trace(" consistency "); trace_nodeside(&node->sides[side]);
444 trace(" "); trace_edgeend(edgeend); trace("\n");
447 LIST_CHECKNODE(node->sides[side], edgeend);
448 assert(edgeend == &edge->ends[edgeend->end]);
449 assert(edgeend->node == &node->sides[side]);
450 if (used_edone==alloc_edone) {
451 alloc_edone += 2; alloc_edone *= 2;
452 edone= MREALLOC(edone, alloc_edone * sizeof(*edone));
454 for (search_edone= edone;
455 search_edone < edone + used_edone && search_edone->edge != edge;
457 if (search_edone >= edone + used_edone) {
458 search_edone->edge= edge;
459 search_edone->endsdone= 0;
462 search_edone->endsdone++;
463 assert(search_edone->endsdone <= 2);
467 for (search_edone= edone;
468 search_edone < edone + used_edone;
470 trace("consistency "); trace_edge(search_edone->edge);
471 trace(" count=%d\n", search_edone->endsdone);
472 assert(search_edone->endsdone == 2);
474 trace("consistency check (%s) ok\n",why);
477 static void consistency(void) {
478 check("command-line request");
481 static void printforneato(void) {
487 output("digraph L {\n");
489 FOR_ALL_NODES(node) {
490 output(" n%sO [label=\"%s\"];\n"
491 " n%sI [label=\"+\"];\n",
492 node->pname, node->pname, node->pname);
493 output(" n%sO -> n%sI [len=0.25 arrowsize=0];\n",
494 node->pname, node->pname);
495 FOR_EDGES(edge, node,side,edgeend) {
496 output(" n%s%c -> n%s%c [label=\"%s:",
497 edge->ends[0].node->node->pname,
498 "OI"[edge->ends[0].node->side],
499 edge->ends[1].node->node->pname,
500 "OI"[edge->ends[1].node->side],
502 if (!edge->subseg->segment->segname) {
505 output(edge->subseg->segment->segname);
506 if (edge->subseg->movfeat) {
507 output("/%s%d",edge->subseg->movfeat,edge->movpos);
510 output(":%.2f\"];\n",edge->distance);
521 static const OpInfo opinfos[]= {
522 #define OI(x) { #x, x },
530 static void usage(void) {
534 "usage: .../redactgraph <operation> [<operation>...]\n"
536 for (oi=opinfos; oi->name; oi++) {
537 fprintf(stderr," %s\n",oi->name);
543 int main(int argc, const char *const *argv) {
547 if (!argv[0] || !argv[1]) usage();
549 while ((arg= *++argv)) {
550 for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
551 if (!oi->name) usage();
556 if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }