2 * output format from printforforsafety is lines like this:
3 * segment <node>.<side> <node>.<side> <segment>[/<movinfo>] <distance>
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
23 * - not at all (indicates a terminus)
24 * Refer to safety.h for info regarding <combpos>.
26 * See layout-data.h comment for info regarding layout data for
29 /* for debugging, runes like
30 * ./ours.redactgraph consistency movfeatsplitedges consistency movfeatrmstubs consistency movfeatsplitnodes consistency trivpairnodes consistency trivnullnodes consistency printforneato | neato -Tps >u.ps
42 #include "graph-data.h"
44 #define MMALLOC(sz) mmalloc(sz,__FILE__,__LINE__)
45 #define MREALLOC(p,sz) mrealloc(p,sz,__FILE__,__LINE__)
47 static void *mmalloccheck(void *p, const char *op, size_t sz,
48 const char *file, int line) {
50 fprintf(stderr,"%s:%d: %s of %lu failed: %s\n",
51 file, line, op, (unsigned long)sz, strerror(errno));
55 static void *mmalloc(size_t sz, const char *file, int line) {
59 return mmalloccheck(p,"malloc",sz,file,line);
62 static void *mrealloc(void *p, size_t sz, const char *file, int line) {
64 return mmalloccheck(p,"realloc",sz,file,line);
67 static char *mvasprintf(const char *fmt, va_list al)
68 __attribute__((format(printf,1,0)));
69 static char *mvasprintf(const char *fmt, va_list al) {
73 r= vasprintf(&p,fmt,al);
75 fprintf(stderr,"vasprintf(\"%s\",...) failed: %s\n",
76 fmt, strerror(errno));
82 static char *masprintf(const char *fmt, ...)
83 __attribute__((format(printf,1,2)));
84 static char *masprintf(const char *fmt, ...) {
88 p= mvasprintf(fmt,al);
93 /*---------- output processing ----------*/
95 static void voutputstuff(int trace, const char *fmt, va_list al)
96 __attribute__((format(printf,2,0)));
97 static void voutputstuff(int trace, const char *fmt, va_list al) {
98 static struct OutputBuf {
104 char *s, *p, *newline;
108 s= mvasprintf(fmt,al);
112 newline= strchr(p,'\n');
113 if (newline) { *newline= 0; }
115 if (l+b->used > b->allocd) {
116 b->allocd= l+b->used;
117 b->buf= MREALLOC(b->buf, b->allocd);
119 memcpy(b->buf+b->used, p, l);
124 if (trace) { fputs("# ",stdout); }
125 fwrite(b->buf, 1,b->used, stdout);
127 if (ferror(stdout) || fflush(stdout)) {
128 perror("stdout voutputstuff"); exit(12);
138 static void v##fn(const char *fmt, va_list al) \
139 __attribute__((format(printf,1,0))); \
140 static void v##fn(const char *fmt, va_list al) { \
141 voutputstuff(tr,fmt,al); \
143 static void fn(const char *fmt, ...) __attribute__((format(printf,1,2))); \
144 static void fn(const char *fmt, ...) { \
153 /*---------- traceing of various things ----------*/
155 static void trace_node(Node *node) {
156 trace("n%s",node->pname);
159 static void trace_nodeside(NodeSide *node) {
160 trace("n%s %c",node->node->pname,"OI"[node->side]);
163 static void trace_edge(Edge *edge) {
164 trace("e%s",edge->pname);
167 static void trace_edgeend(EdgeEnd *edge) {
168 trace("e%s %c",edge->edge->pname,"OI"[edge->end]);
171 static void trace_combpos(int combpos, Segment *seg) {
177 FOR_SEGMENT_MOVFEATS(i,f,seg) {
178 if (!f->movfeat) continue;
179 trace("%s%d", f->movfeat, (combpos / weight) % f->n_positions);
180 weight *= f->n_positions;
184 /*---------- general graph-manipulation tools ----------*/
186 static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
187 return &thisend->edge->ends[!thisend->end];
190 static int count_edges(const NodeSide *node) {
194 for (count=0, edge=node->head;
196 count++, edge=edge->next);
200 static Edge *edge_create(const char *pname, double distance,
201 MovFeat *subseg, int movpos) {
205 e= MMALLOC(sizeof(*e));
207 e->distance= distance;
211 e->ends[end].edge= e;
212 e->ends[end].end= end;
214 trace("[new:"); trace_edge(e); trace("]");
218 static Node *node_create(const char *pname) {
222 n= MMALLOC(sizeof(*n));
225 n->sides[side].node= n;
226 n->sides[side].side= side;
227 LIST_INIT(n->sides[side]);
229 LIST_LINK_TAIL(all_nodes,n);
233 /* Perhaps surprisingly, it's OK to remove nodes and edges in loops
234 * made with the macros in graph-data.h, provided that if the
235 * _current_ node or edge is removed, that happens last. This is
236 * because removing a node or edge it doesn't actually free it or
237 * change its contents, so the thing->next is still valid afterwards.
238 * This depends on the fact that we never free anything we're done
242 static void edgeend_detach(EdgeEnd *toremove) {
243 trace("[detach:"); trace_edgeend(toremove);
244 trace("-"); trace_nodeside(toremove->node); trace("]");
245 LIST_UNLINK(*toremove->node, toremove);
247 static void edgeend_attach(EdgeEnd *toattach, NodeSide *newtarget) {
248 trace("[attach:"); trace_edgeend(toattach);
249 trace("-"); trace_nodeside(newtarget); trace("]");
250 LIST_LINK_TAIL(*newtarget, toattach);
251 toattach->node= newtarget;
253 static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) {
254 edgeend_detach(tomove);
255 edgeend_attach(tomove,newtarget);
258 static void edge_delete(EdgeEnd *detachlast) {
260 edge= detachlast->edge;
261 edgeend_detach(&edge->ends[!detachlast->end]);
262 edgeend_detach(detachlast);
263 trace("[delete:"); trace_edge(edge); trace("]");
266 static void node_surely_orphaned(Node *node) {
267 trace("[nodeorphan:"); trace_node(node); trace("]");
268 assert(!node->sides[0].head);
269 assert(!node->sides[1].head);
270 LIST_UNLINK(all_nodes, node);
273 /*---------- operations - heavyweight graph redaction ----------*/
275 /* We combine the individual moveable features in each segment into
276 * a single `feature' with the cross-product of all of the
277 * positions. The new feature does not appear in
278 * Segment->[n_]movfeats, but Edge->subseg and Edge->movpos are
279 * updated (ie Edge->subseg->segment->movfeats is the original array
280 * containing only the actual features, and so does not contain
281 * Edge->subseg). It is often printed as if its name was `*' (which
282 * is not legal in input files etc.). The positions of the
283 * *-feature are numbered according to the obvious arithmetic coding
284 * of the individual actual feature positions. See also
287 * The conversion has two stages:
289 * FIRST STAGE (movfeatsplitedges):
291 * We multiply up each edge of any segment with moveable features to
292 * be an edge which is a position of the *-feature.
294 * For example, if segment A1 has feature P with states 0 and 1
295 * and feature J with states 0 and 1, then the edges are translated
298 * A1 A1/P0J0 A1/P0J1 A1/P1J0 A1/P1J1
299 * A1/P0 A1/P0J0 A1/P0J1
300 * A1/P1 A1/P1J0 A1/P1J1
301 * A1/J0 A1/P0J0 A1/P1J0
302 * A1/J1 A1/P0J1 A1/P1J1
304 * *----A1/P0----* becomes *----A1/P0J0----*
307 * SECOND STAGE (movfeatrmstubs):
309 * We remove stub moveable edges: whenever, at a node which has only
310 * edges which are part of the same segment, we find an edge on one
311 * side in which is not matched exactly (moveable feature settings
312 * and direction) by an edge on the other side, we delete that extra
315 * is split into one node
316 * for each position and direction (directions are
317 * end0-to-side0+end1-to-side1 and end0-to-side1+end1-to-side0), to
318 * which the corresponding edges are connected. Any resulting node
319 * which has only one edge is removed together with the edge.
321 * For example (neglecting direction for the purposes of the
322 * example), when we start with:
325 * ...*----A1/P0J1----*---A1/P0J1---*...
326 * `---A1/P1J0---' `--A1/P1J1--'
329 * the edges A1/P0J0 and A1/P1J1 are not matched on the RHS of the node,
330 * so they are removed:
332 * ...*----A1/P0J1----*---A1/P0J1---*...
333 * `---A1/P1J0---' `--A1/P1J1--'
338 * We split nodes: every node which has only edges which are part of
339 * the same segment is split into one node for each kind of edge
340 * which goes through it. The 2nd stage ensures that this is always
343 * Our example above turns into:
345 * ...*----A1/P0J1----*---A1/P0J1---*...
346 * `---A1/P1J0----*---A1/P1J1--'
349 static void movfeatsplitedges(void) {
351 int side, l, i, weight, combpos, end;
353 Edge *edge, *newedge;
355 MovFeat *subseg, *starfeature, *loopfeat;
358 trace("movfeatsplitedges ...\n");
359 FOR_ALL_NODES(node) {
360 FOR_EDGES(edge, node,side,edgeend) {
361 subseg= edge->subseg;
362 segment= subseg->segment;
364 trace("movfeatsplitedges "); trace_edge(edge);
365 trace(" segment %s ", segment->segname);
366 if (segment->n_movfeats<=1) { trace("no moveables\n"); continue; }
367 if (subseg == segment->starfeature) { trace("*-feature\n"); continue; }
369 starfeature= segment->starfeature;
374 starfeature= MMALLOC(sizeof(*starfeature));
375 starfeature->segment= segment;
377 l=2; starfeature->n_positions=1;
378 FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
379 if (!loopfeat->movfeat) continue;
380 l += strlen(loopfeat->movfeat);
381 starfeature->n_positions *= loopfeat->n_positions;
384 starfeature->movfeat= featstr= MMALLOC(l);
385 strcpy(featstr, "*");
387 FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
388 if (!loopfeat->movfeat) continue;
389 strcat(featstr, loopfeat->movfeat);
392 segment->starfeature= starfeature;
394 trace(" %s(%d) ", starfeature->movfeat, starfeature->n_positions);
396 if (subseg->movfeat) {
398 FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
399 if (loopfeat == subseg) goto found;
400 weight *= loopfeat->n_positions;
404 trace("%s(x%d)",subseg->movfeat,weight);
412 for (combpos=0; combpos<starfeature->n_positions; combpos++) {
413 trace("movfeatsplitedges "); trace_combpos(combpos,segment);
414 if ((combpos / weight) % subseg->n_positions != edge->movpos) {
415 trace(" excluded\n");
418 newedge= edge_create(masprintf("%s/*%d",edge->pname,combpos),
423 edgeend_attach(&newedge->ends[end], edge->ends[end].node);
425 edge_delete(edgeend);
428 trace("movfeatsplitedges complete.\n");
431 static int movfeat_isinnernode(Node *node) {
434 Segment *all_segment, *segment;
439 if (!node->sides[side].head) {
440 trace(" %c terminus\n", "OI"[side]);
444 FOR_NODE_EDGEENDS(side,edgeend, node) {
445 segment= edgeend->edge->subseg->segment;
447 all_segment= segment;
448 } else if (all_segment != segment) {
449 trace(" not inner: %s and %s\n",
450 all_segment->segname, segment->segname);
455 trace(" not inner: no edges?!\n");
458 trace(" inner %s ",all_segment->segname);
462 static EdgeEnd *movfeat_findmate(EdgeEnd *key) {
467 node= key->node->node;
468 mateside= !key->node->side;
470 FOR_SIDE_EDGEENDS(mate, node,mateside) {
471 if (key->edge->subseg == mate->edge->subseg &&
472 key->edge->movpos == mate->edge->movpos &&
473 key->end != mate->end)
476 return 0; /* no mate - must be a stub */
479 static void movfeatrmstubs(void) {
480 int pass, anychange, side;
483 EdgeEnd *edgeend, *mate;
489 trace("movfeatrmstubs pass %d ...\n", pass);
490 FOR_ALL_NODES(node) {
491 trace("movfeatrmstubs ");
492 if (!movfeat_isinnernode(node)) continue;
493 FOR_NODE_EDGEENDS(side,edgeend, node) {
495 mate= movfeat_findmate(edgeend);
497 trace("("); trace_edgeend(edgeend); trace(")");
500 edge_delete(edgeend);
505 trace("movfeatrmstubs pass %d %s\n", pass, anychange?"changed":"alldone");
509 static void movfeatsplitnodes(void) {
510 Node *node, *newnode;
511 EdgeEnd *edgeend, *mate;
515 FOR_ALL_NODES(node) {
516 trace("movfeatsplitnodes ");
517 if (!movfeat_isinnernode(node)) continue;
518 if (!node->sides[0].head->next) {
519 trace("pair-trivial\n");
522 FOR_NODE_EDGEENDS(side,edgeend, node) {
524 mate= movfeat_findmate(edgeend);
526 newnode= node_create(masprintf("%sx%d",node->pname,edge->movpos));
527 edgeend_replumb(mate, &newnode->sides[mate->node->side]);
528 edgeend_replumb(edgeend, &newnode->sides[edgeend->node->side]);
533 /*---------- operations - trivial graph redaction etc. ----------*/
535 static void trivpairnodes(void) {
536 /* Eliminate near-trivial nodes - in this case, ones which have only
537 * two edges, which come in on opposite sides, have the same
538 * subsegspec, and with the two ends identically aligned.
540 EdgeEnd *leftedge, *rightedge;
543 FOR_ALL_NODES(node) {
544 trace("trivpairnodes node "); trace_node(node); trace(" ");
545 if (!(count_edges(&node->sides[0])==1 &&
546 count_edges(&node->sides[1])==1)) {
547 trace("no, a non-unitary side\n");
550 leftedge= node->sides[0].head;
551 rightedge= node->sides[1].head;
552 if (leftedge->edge->subseg != rightedge->edge->subseg) {
553 trace("no, (sub)segments differ\n");
556 if (leftedge->edge->movpos != rightedge->edge->movpos) {
557 trace("no, movpos's differ\n");
560 if (leftedge->end == rightedge->end) {
561 trace("no, opposite alignment\n");
565 if (!strchr(rightedge->edge->pname, '+')) {
566 rightedge->edge->pname=
567 masprintf("%s+", rightedge->edge->pname);
569 rightedge->edge->distance += leftedge->edge->distance;
570 edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
571 edge_delete(leftedge);
572 trace(" trivpairnodes operation complete\n");
576 static void trivnullnodes(void) {
577 /* Eliminate trivial nodes - ones which have no edges. */
581 trace("trivnullnodes ");
582 FOR_ALL_NODES(node) {
584 if (node->sides[side].head)
587 node_surely_orphaned(node);
590 trace(" trivnullnodes done.\n");
593 static void check(const char *why) {
595 int alloc_edone, used_edone;
596 typedef struct { Edge *edge; int endsdone; } EdgeDone;
597 EdgeDone *edone, *search_edone;
603 alloc_edone= used_edone= 0;
605 trace("consistency check (%s) ...\n",why);
606 FOR_ALL_NODES(node) {
607 trace(" consistency "); trace_node(node); trace("\n");
608 LIST_CHECKNODE(all_nodes,node);
610 trace(" consistency "); trace_nodeside(&node->sides[side]); trace("\n");
611 assert(node->sides[side].node == node);
612 assert(node->sides[side].side == side);
613 FOR_SIDE_EDGEENDS(edgeend, node,side) {
614 trace(" consistency "); trace_nodeside(&node->sides[side]);
615 trace(" "); trace_edgeend(edgeend); trace("\n");
618 LIST_CHECKNODE(node->sides[side], edgeend);
619 assert(edgeend == &edge->ends[edgeend->end]);
620 assert(edgeend->node == &node->sides[side]);
621 if (used_edone==alloc_edone) {
622 alloc_edone += 2; alloc_edone *= 2;
623 edone= MREALLOC(edone, alloc_edone * sizeof(*edone));
625 for (search_edone= edone;
626 search_edone < edone + used_edone && search_edone->edge != edge;
628 if (search_edone >= edone + used_edone) {
629 search_edone->edge= edge;
630 search_edone->endsdone= 0;
633 search_edone->endsdone++;
634 assert(search_edone->endsdone <= 2);
638 for (search_edone= edone;
639 search_edone < edone + used_edone;
641 trace("consistency "); trace_edge(search_edone->edge);
642 trace(" count=%d\n", search_edone->endsdone);
643 assert(search_edone->endsdone == 2);
645 trace("consistency check (%s) ok\n",why);
648 static void consistency(void) {
649 check("command-line request");
652 /*---------- operations - output ----------*/
654 static void printforneato(void) {
660 output("digraph L {\n");
662 FOR_ALL_NODES(node) {
663 output(" n%sO [label=\"%s\"];\n"
664 " n%sI [label=\"+\"];\n",
665 node->pname, node->pname, node->pname);
666 output(" n%sO -> n%sI [len=0.25 arrowsize=0];\n",
667 node->pname, node->pname);
668 FOR_EDGES(edge, node,side,edgeend) {
669 output(" n%s%c -> n%s%c [label=\"%s:",
670 edge->ends[0].node->node->pname,
671 "OI"[edge->ends[0].node->side],
672 edge->ends[1].node->node->pname,
673 "OI"[edge->ends[1].node->side],
675 if (!edge->subseg->segment->segname) {
678 output(edge->subseg->segment->segname);
679 if (edge->subseg->movfeat) {
680 output("/%s%d",edge->subseg->movfeat,edge->movpos);
683 output(":%.2f\"];\n",edge->distance);
689 static void printforforsafety(void) {
693 int side, end, weight, i;
697 FOR_ALL_NODES(node) {
698 FOR_EDGES(edge, node,side,edgeend) {
702 edge->ends[end].node->node->pname,
703 edge->ends[end].node->side);
705 segment= edge->subseg->segment;
706 output(segment->segname);
707 if (segment->n_movfeats>1) {
708 if (!segment->starfeature) {
709 fprintf(stderr,"printforforsafety before movfeatsplitedges!\n");
714 FOR_SEGMENT_MOVFEATS(i,movfeat, segment) {
715 if (!movfeat->movfeat) continue;
716 output("%s%d", movfeat->movfeat,
717 (edge->movpos / weight) % movfeat->n_positions);
718 weight *= movfeat->n_positions;
720 output("*%d", edge->movpos);
722 output(" %f\n", edge->distance);
728 static void printforlayoutsegjoins(void) {
730 EdgeEnd *edgeend, *edgeend2;
731 Segment **segmentp, *segment, *segment2;
732 int side, side2, order, max_order, colour, any_left;
734 /* we format segment->u as follows: */
735 #define LSJ_U_VERTEXORDER_MASK 0x000000ff
736 #define LSJ_U_COLOUR_SHIFT 8
737 #define LSJ_U_COLOUR_BITS 16
738 #define LSJ_U_COLOUR_UNIT (1<<LSJ_U_COLOUR_SHIFT)
739 #define LSJ_U_COLOUR_MASK 0x00ffff00
740 #define LSJ_U_SEGEND_DONE 0x01000000
741 #define LSJ_U_COLOUR_CLASH 0x02000000
744 FOR_ALL_SEGMENTS(segmentp,segment)
747 FOR_ALL_NODES(node) {
750 if (!node->sides[side].head) {
751 output("segterminus");
756 output("%d\n", (node->layermin + node->layermax)/2);
758 output("abs segjoin_%s %f %f %f\n",node->pname,
759 node->x,node->y,node->a);
760 FOR_NODE_EDGEENDS(side,edgeend, node) {
761 segment= edgeend->edge->subseg->segment;
762 if (segment->u & LSJ_U_SEGEND_DONE) continue;
763 segment->u |= LSJ_U_SEGEND_DONE;
764 assert(~segment->u & LSJ_U_VERTEXORDER_MASK); /* detect overflow */
766 order= segment->u & LSJ_U_VERTEXORDER_MASK;
767 if (order > max_order) max_order= order;
768 output("segend segjoin_%s %s\n",node->pname, segment->segname);
771 FOR_ALL_SEGMENTS(segmentp,segment)
772 segment->u &= ~LSJ_U_SEGEND_DONE;
775 /* Welsh and Powell's graph colouring algorithm
776 * (Wikipedia Graph_coloring) */
777 output("# max-order %d\n",max_order);
779 for (colour=LSJ_U_COLOUR_UNIT, any_left=1;
781 colour+=LSJ_U_COLOUR_UNIT) {
782 output("# colour %x\n", colour);
783 assert(!(colour & ~LSJ_U_COLOUR_MASK));
786 FOR_ALL_SEGMENTS(segmentp,segment)
787 segment->u &= ~LSJ_U_COLOUR_CLASH;
790 FOR_NODE_EDGEENDS(side,edgeend, node) {
791 segment= edgeend->edge->subseg->segment;
792 if (colour == (segment->u & LSJ_U_COLOUR_MASK)) {
793 output("# already %s\n", segment->segname);
794 FOR_NODE_EDGEENDS(side2,edgeend2, node) {
795 segment2= edgeend2->edge->subseg->segment;
796 output("# therefore-not %s\n", segment2->segname);
797 segment2->u |= LSJ_U_COLOUR_CLASH;
802 for (order=max_order; order>0; order--) { /* idiot-sort */
803 output("# order %d\n", order);
804 FOR_ALL_SEGMENTS(segmentp,segment)
805 if ((segment->u & LSJ_U_VERTEXORDER_MASK) == order) {
806 if (segment->u & LSJ_U_COLOUR_MASK) continue;
808 if (segment->u & LSJ_U_COLOUR_CLASH) {
809 output("# still-clashes %s\n", segment->segname);
812 segment->u |= colour;
813 output("# coloured %s\n", segment->segname);
816 output("# (skip %s %x)\n", segment->segname,segment->u);
821 FOR_ALL_SEGMENTS(segmentp,segment) {
822 int tcolour= segment->u & LSJ_U_COLOUR_MASK;
823 const double val1=0.60, val2=0.35;
825 if (!tcolour) continue;
827 (tcolour - LSJ_U_COLOUR_UNIT*2) * (val1-val2) /
828 (colour - LSJ_U_COLOUR_UNIT*2);
829 output("segcmap %s %f setgray\n", segment->segname,value);
831 output("#line %d %s\n", __LINE__, __FILE__);
832 output("ident $Revision$\n");
835 /*---------- main program ----------*/
842 static const OpInfo opinfos[]= {
843 #define OI(x) { #x, x },
845 OI(printforforsafety)
846 OI(printforlayoutsegjoins)
848 OI(movfeatsplitedges)
850 OI(movfeatsplitnodes)
856 static void usage(void) {
860 "usage: .../redactgraph <operation> [<operation>...]\n"
862 for (oi=opinfos; oi->name; oi++) {
863 fprintf(stderr," %s\n",oi->name);
869 int main(int argc, const char *const *argv) {
873 if (!argv[0] || !argv[1]) usage();
875 while ((arg= *++argv)) {
876 for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
877 if (!oi->name) usage();
882 if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }