-/**/
-
-typedef struct Edge Edge;
-typedef struct EdgeEnd EdgeEnd;
-typedef struct Node Node;
-typedef struct NodeSideRef NodeSideRef;
-
-struct EdgeEnd {
- EdgeNode *back, *next; /* other ends at same side of same node */
- Edge *edge; /* edge->ends[end].edge==edge */
- int end; /* edge->ends[end].edge==end */
- NodeSide *node;
-};
+/*
+ * output format from printforforsafety is lines like this:
+ * segment <node>.<side> <node>.<side> <segment>[/<movinfo>] <distance>
+ * #... (comment)
+ * (blank)
+ * end (at end of file, mandatory)
+ * syntactic restrictions:
+ * <node> is alphanumeric and starts with a letter
+ * <side> is precisely the digit 0 or the digit 1
+ * <segment> is alphanumeric (and comes from the layout)
+ * <movinfo> is <movfeat><movpos>[<movfeat><movpos>...]*<combpos>
+ * where <movfeat> is alphabetic and <movpos> is and
+ * <combpos> are in decimal and have no unnecessary leading 0's
+ * <distance> contains only digits and perhaps decimal point
+ * semantic restrictions (not enforced by redactgraph but ought to
+ * be impossible for layout designer to violate):
+ * Each <segment>[/<movinfo>] appears exactly once.
+ * <segment> appears either once without /<movinfo> or always with.
+ * Each side of each node appears either
+ * - once as the 0th or 1th end of a <segment>
+ * - one or more times as the same end of <segment>/<movinfo>'s with
+ * the same <segment>
+ * - not at all (indicates a terminus)
+ * Refer to safety.h for info regarding <combpos>.
+ *
+ * See layout-data.h comment for info regarding layout data for
+ * control system.
+ */
+/* for debugging, runes like
+ * ./ours.redactgraph consistency movfeatsplitedges consistency movfeatrmstubs consistency movfeatsplitnodes consistency trivpairnodes consistency trivnullnodes consistency printforneato | neato -Tps >u.ps
+ * are often useful.
+ */
-struct Edge {
- double distance;
- const char *segment, *movfeatpos;
- EdgeEnd ends[2];
-};
+#include <stdarg.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include <errno.h>
-typedef struct {
- Node *node; /* node->edges[side].node==node */
- int side; /* node->edges[side].side==side */
- EdgeEnd *head, *tail;
-} NodeSide;
-
-struct Node {
- Node *back, *next;
- NodeSide sides[2];
-};
+#include "dlist.h"
+#include "graph-data.h"
+
+#define MMALLOC(sz) mmalloc(sz,__FILE__,__LINE__)
+#define MREALLOC(p,sz) mrealloc(p,sz,__FILE__,__LINE__)
+
+static void *mmalloccheck(void *p, const char *op, size_t sz,
+ const char *file, int line) {
+ if (p) return p;
+ fprintf(stderr,"%s:%d: %s of %lu failed: %s\n",
+ file, line, op, (unsigned long)sz, strerror(errno));
+ exit(16);
+}
+
+static void *mmalloc(size_t sz, const char *file, int line) {
+ void *p;
+ if (!sz) return 0;
+ p= malloc(sz);
+ return mmalloccheck(p,"malloc",sz,file,line);
+}
+
+static void *mrealloc(void *p, size_t sz, const char *file, int line) {
+ p= realloc(p,sz);
+ return mmalloccheck(p,"realloc",sz,file,line);
+}
+
+static char *mvasprintf(const char *fmt, va_list al)
+ __attribute__((format(printf,1,0)));
+static char *mvasprintf(const char *fmt, va_list al) {
+ char *p;
+ int r;
+
+ r= vasprintf(&p,fmt,al);
+ if (r<0) {
+ fprintf(stderr,"vasprintf(\"%s\",...) failed: %s\n",
+ fmt, strerror(errno));
+ exit(16);
+ }
+ return p;
+}
+
+static char *masprintf(const char *fmt, ...)
+ __attribute__((format(printf,1,2)));
+static char *masprintf(const char *fmt, ...) {
+ va_list al;
+ char *p;
+ va_start(al,fmt);
+ p= mvasprintf(fmt,al);
+ va_end(al);
+ return p;
+}
+
+/*---------- output processing ----------*/
+
+static void voutputstuff(int trace, const char *fmt, va_list al)
+ __attribute__((format(printf,2,0)));
+static void voutputstuff(int trace, const char *fmt, va_list al) {
+ static struct OutputBuf {
+ int used, allocd;
+ char *buf;
+ } bufs[2];
+
+ struct OutputBuf *b;
+ char *s, *p, *newline;
+ int l;
+
+ b= &bufs[trace];
+ s= mvasprintf(fmt,al);
+ p= s;
+
+ for (;;) {
+ newline= strchr(p,'\n');
+ if (newline) { *newline= 0; }
+ l= strlen(p);
+ if (l+b->used > b->allocd) {
+ b->allocd= l+b->used;
+ b->buf= MREALLOC(b->buf, b->allocd);
+ }
+ memcpy(b->buf+b->used, p, l);
+ b->used += l;
+
+ if (!newline) break;
+
+ if (trace) { fputs("# ",stdout); }
+ fwrite(b->buf, 1,b->used, stdout);
+ putc('\n',stdout);
+ if (ferror(stdout) || fflush(stdout)) {
+ perror("stdout voutputstuff"); exit(12);
+ }
+ b->used= 0;
+ p= newline+1;
+ }
+
+ free(s);
+}
+
+#define OF(fn,tr) \
+ static void v##fn(const char *fmt, va_list al) \
+ __attribute__((format(printf,1,0))); \
+ static void v##fn(const char *fmt, va_list al) { \
+ voutputstuff(tr,fmt,al); \
+ } \
+ static void fn(const char *fmt, ...) __attribute__((format(printf,1,2))); \
+ static void fn(const char *fmt, ...) { \
+ va_list al; \
+ va_start(al,fmt); \
+ v##fn(fmt,al); \
+ va_end(al); \
+ }
+OF(output,0)
+OF(trace,1)
+
+/*---------- traceing of various things ----------*/
+
+static void trace_node(Node *node) {
+ trace("n%s",node->pname);
+}
+
+static void trace_nodeside(NodeSide *node) {
+ trace("n%s %c",node->node->pname,"OI"[node->side]);
+}
+
+static void trace_edge(Edge *edge) {
+ trace("e%s",edge->pname);
+}
+
+static void trace_edgeend(EdgeEnd *edge) {
+ trace("e%s %c",edge->edge->pname,"OI"[edge->end]);
+}
+
+static void trace_combpos(int combpos, Segment *seg) {
+ int i, weight;
+ MovFeat *f;
+
+ trace("*");
+ weight= 1;
+ FOR_SEGMENT_MOVFEATS(i,f,seg) {
+ if (!f->movfeat) continue;
+ trace("%s%d", f->movfeat, (combpos / weight) % f->n_positions);
+ weight *= f->n_positions;
+ }
+}
+
+/*---------- general graph-manipulation tools ----------*/
+
+static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
+ return &thisend->edge->ends[!thisend->end];
+}
+
+static int count_edges(const NodeSide *node) {
+ int count;
+ const EdgeEnd *edge;
+
+ for (count=0, edge=node->head;
+ edge;
+ count++, edge=edge->next);
+ return count;
+}
-static Node *nodes_head, *nodes_tail;
+static Edge *edge_create(const char *pname, double distance,
+ MovFeat *subseg, int movpos) {
+ Edge *e;
+ int end;
+
+ e= MMALLOC(sizeof(*e));
+ e->pname= pname;
+ e->distance= distance;
+ e->subseg= subseg;
+ e->movpos= movpos;
+ FOR_BOTH(end) {
+ e->ends[end].edge= e;
+ e->ends[end].end= end;
+ }
+ trace("[new:"); trace_edge(e); trace("]");
+ return e;
+}
+
+static Node *node_create(const char *pname) {
+ Node *n;
+ int side;
+
+ n= MMALLOC(sizeof(*n));
+ n->pname= pname;
+ FOR_BOTH(side) {
+ n->sides[side].node= n;
+ n->sides[side].side= side;
+ LIST_INIT(n->sides[side]);
+ }
+ LIST_LINK_TAIL(all_nodes,n);
+ return n;
+}
-static void extendsplits(void) {
- /*
- * Whenever we have a node which has one or more moveable feature
- * subsegments, part of the same moveable feature, on one side, and
- * fixed portion of the same segment on the other, we eliminate
- * the fixed portion and add its length to both the moveables,
- * so that we have one subsegspec for the whole of each position:
+/* Perhaps surprisingly, it's OK to remove nodes and edges in loops
+ * made with the macros in graph-data.h, provided that if the
+ * _current_ node or edge is removed, that happens last. This is
+ * because removing a node or edge it doesn't actually free it or
+ * change its contents, so the thing->next is still valid afterwards.
+ * This depends on the fact that we never free anything we're done
+ * with !
+ */
+
+static void edgeend_detach(EdgeEnd *toremove) {
+ trace("[detach:"); trace_edgeend(toremove);
+ trace("-"); trace_nodeside(toremove->node); trace("]");
+ LIST_UNLINK(*toremove->node, toremove);
+}
+static void edgeend_attach(EdgeEnd *toattach, NodeSide *newtarget) {
+ trace("[attach:"); trace_edgeend(toattach);
+ trace("-"); trace_nodeside(newtarget); trace("]");
+ LIST_LINK_TAIL(*newtarget, toattach);
+ toattach->node= newtarget;
+}
+static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) {
+ edgeend_detach(tomove);
+ edgeend_attach(tomove,newtarget);
+}
+
+static void edge_delete(EdgeEnd *detachlast) {
+ Edge *edge;
+ edge= detachlast->edge;
+ edgeend_detach(&edge->ends[!detachlast->end]);
+ edgeend_detach(detachlast);
+ trace("[delete:"); trace_edge(edge); trace("]");
+}
+
+static void node_surely_orphaned(Node *node) {
+ trace("[nodeorphan:"); trace_node(node); trace("]");
+ assert(!node->sides[0].head);
+ assert(!node->sides[1].head);
+ LIST_UNLINK(all_nodes, node);
+}
+
+/*---------- operations - heavyweight graph redaction ----------*/
+
+ /* We combine the individual moveable features in each segment into
+ * a single `feature' with the cross-product of all of the
+ * positions. The new feature does not appear in
+ * Segment->[n_]movfeats, but Edge->subseg and Edge->movpos are
+ * updated (ie Edge->subseg->segment->movfeats is the original array
+ * containing only the actual features, and so does not contain
+ * Edge->subseg). It is often printed as if its name was `*' (which
+ * is not legal in input files etc.). The positions of the
+ * *-feature are numbered according to the obvious arithmetic coding
+ * of the individual actual feature positions. See also
+ * hostside/safety.h.
+ *
+ * The conversion has two stages:
+ *
+ * FIRST STAGE (movfeatsplitedges):
+ *
+ * We multiply up each edge of any segment with moveable features to
+ * be an edge which is a position of the *-feature.
+ *
+ * For example, if segment A1 has feature P with states 0 and 1
+ * and feature J with states 0 and 1, then the edges are translated
+ * as follows
+ * old edge new edges
+ * A1 A1/P0J0 A1/P0J1 A1/P1J0 A1/P1J1
+ * A1/P0 A1/P0J0 A1/P0J1
+ * A1/P1 A1/P1J0 A1/P1J1
+ * A1/J0 A1/P0J0 A1/P1J0
+ * A1/J1 A1/P0J1 A1/P1J1
+ * Eg,
+ * *----A1/P0----* becomes *----A1/P0J0----*
+ * `---A1/P0J1---'
+ *
+ * SECOND STAGE (movfeatrmstubs):
+ *
+ * We remove stub moveable edges: whenever, at a node which has only
+ * edges which are part of the same segment, we find an edge on one
+ * side in which is not matched exactly (moveable feature settings
+ * and direction) by an edge on the other side, we delete that extra
+ * edge:
+ *
+ * is split into one node
+ * for each position and direction (directions are
+ * end0-to-side0+end1-to-side1 and end0-to-side1+end1-to-side0), to
+ * which the corresponding edges are connected. Any resulting node
+ * which has only one edge is removed together with the edge.
+ *
+ * For example (neglecting direction for the purposes of the
+ * example), when we start with:
*
- * <---l---> <----l'----> <--------(l+l')------>
+ * ,---A1/P0J0---.
+ * ...*----A1/P0J1----*---A1/P0J1---*...
+ * `---A1/P1J0---' `--A1/P1J1--'
+ * `--A1/P1J1--'
*
- * *----A1---*----A1/P0--* becomes *--------A1/P0----------*
- * `---A1/P1---* `-------A1/P1-----------*
+ * the edges A1/P0J0 and A1/P1J1 are not matched on the RHS of the node,
+ * so they are removed:
*
- * <----l''---> <--------(l+l'')------>
+ * ...*----A1/P0J1----*---A1/P0J1---*...
+ * `---A1/P1J0---' `--A1/P1J1--'
+ *
+ *
+ * THIRD STAGE:
+ *
+ * We split nodes: every node which has only edges which are part of
+ * the same segment is split into one node for each kind of edge
+ * which goes through it. The 2nd stage ensures that this is always
+ * straightforward.
+ *
+ * Our example above turns into:
+ *
+ * ...*----A1/P0J1----*---A1/P0J1---*...
+ * `---A1/P1J0----*---A1/P1J1--'
*/
- for (;;) {
- pass++;
- for (node=nodes_head; node; node=node->next) {
- for (rightside=0; rightside<2; rightside++) {
- trace("extendsplit pass %d node ",pass); trace_node(node);
- trace("/%d ",rightside);
- if ((n= count_edges(&node->sides[!rightside])) != 1) {
- trace("no: lhs edges=%d\n", n);
- goto no_extend_this;
+static void movfeatsplitedges(void) {
+ Node *node;
+ int side, l, i, weight, combpos, end;
+ EdgeEnd *edgeend;
+ Edge *edge, *newedge;
+ Segment *segment;
+ MovFeat *subseg, *starfeature, *loopfeat;
+ char *featstr;
+
+ trace("movfeatsplitedges ...\n");
+ FOR_ALL_NODES(node) {
+ FOR_EDGES(edge, node,side,edgeend) {
+ subseg= edge->subseg;
+ segment= subseg->segment;
+
+ trace("movfeatsplitedges "); trace_edge(edge);
+ trace(" segment %s ", segment->segname);
+ if (segment->n_movfeats<=1) { trace("no moveables\n"); continue; }
+ if (subseg == segment->starfeature) { trace("*-feature\n"); continue; }
+
+ starfeature= segment->starfeature;
+ if (starfeature) {
+ trace("old");
+ } else {
+ trace("new");
+ starfeature= MMALLOC(sizeof(*starfeature));
+ starfeature->segment= segment;
+
+ l=2; starfeature->n_positions=1;
+ FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
+ if (!loopfeat->movfeat) continue;
+ l += strlen(loopfeat->movfeat);
+ starfeature->n_positions *= loopfeat->n_positions;
}
- leftedge= node->sides[!rightside].head;
- if (leftedge->edge->movfeatpos) {
- trace("no: lhs moveable\n");
- goto no_extend_this;
+
+ starfeature->movfeat= featstr= MMALLOC(l);
+ strcpy(featstr, "*");
+
+ FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
+ if (!loopfeat->movfeat) continue;
+ strcat(featstr, loopfeat->movfeat);
}
- if (!node->sides[rightside].head) {
- trace("no: rhs absent\n");
- goto no_extend_this;
+
+ segment->starfeature= starfeature;
+ }
+ trace(" %s(%d) ", starfeature->movfeat, starfeature->n_positions);
+
+ if (subseg->movfeat) {
+ weight= 1;
+ FOR_SEGMENT_MOVFEATS(i,loopfeat, segment) {
+ if (loopfeat == subseg) goto found;
+ weight *= loopfeat->n_positions;
}
- for (rightedge= node->sides[rightside].head;
- rightedge;
- rightedge= rightedge->next) {
- if (!rightedge->edge->movfeatpos) {
- trace("no: rhs fixed ("); trace_edgeend(rightedge); trace(")\n");
- goto no_extend_this;
- }
- if (strcmp(leftedge->edge->segment, rightedge->edge->segment)) {
- trace("no: lhs seg %s, rhs seg %s (",
- leftedge->edge->segment
- rightedge->edge->segment);
- trace_edgeend(rightedge); trace(")\n");
- goto no_extend_this;
- }
+ abort();
+ found:
+ trace("%s(x%d)",subseg->movfeat,weight);
+ } else {
+ weight= 1;
+ trace("fixed");
+ }
+
+ trace(" ...\n");
+
+ for (combpos=0; combpos<starfeature->n_positions; combpos++) {
+ trace("movfeatsplitedges "); trace_combpos(combpos,segment);
+ if ((combpos / weight) % subseg->n_positions != edge->movpos) {
+ trace(" excluded\n");
+ continue;
}
- goto extend_this;
+ newedge= edge_create(masprintf("%s/*%d",edge->pname,combpos),
+ edge->distance,
+ starfeature,
+ combpos);
+ FOR_BOTH(end)
+ edgeend_attach(&newedge->ends[end], edge->ends[end].node);
+ }
+ edge_delete(edgeend);
+ }
+ }
+ trace("movfeatsplitedges complete.\n");
+}
- no_extend_this:;
+static int movfeat_isinnernode(Node *node) {
+ int side;
+ EdgeEnd *edgeend;
+ Segment *all_segment, *segment;
+
+ trace_node(node);
+ all_segment= 0;
+ FOR_BOTH(side) {
+ if (!node->sides[side].head) {
+ trace(" %c terminus\n", "OI"[side]);
+ return 0;
+ }
+ }
+ FOR_NODE_EDGEENDS(side,edgeend, node) {
+ segment= edgeend->edge->subseg->segment;
+ if (!all_segment) {
+ all_segment= segment;
+ } else if (all_segment != segment) {
+ trace(" not inner: %s and %s\n",
+ all_segment->segname, segment->segname);
+ return 0;
+ }
+ }
+ if (!all_segment) {
+ trace(" not inner: no edges?!\n");
+ return 0;
+ }
+ trace(" inner %s ",all_segment->segname);
+ return 1;
+}
+
+static EdgeEnd *movfeat_findmate(EdgeEnd *key) {
+ Node *node;
+ EdgeEnd *mate;
+ int mateside;
+
+ node= key->node->node;
+ mateside= !key->node->side;
+
+ FOR_SIDE_EDGEENDS(mate, node,mateside) {
+ if (key->edge->subseg == mate->edge->subseg &&
+ key->edge->movpos == mate->edge->movpos &&
+ key->end != mate->end)
+ return mate;
+ }
+ return 0; /* no mate - must be a stub */
+}
+
+static void movfeatrmstubs(void) {
+ int pass, anychange, side;
+ Node *node;
+ Edge *edge;
+ EdgeEnd *edgeend, *mate;
+
+ pass= 0;
+ do {
+ anychange= 0;
+ pass++;
+ trace("movfeatrmstubs pass %d ...\n", pass);
+ FOR_ALL_NODES(node) {
+ trace("movfeatrmstubs ");
+ if (!movfeat_isinnernode(node)) continue;
+ FOR_NODE_EDGEENDS(side,edgeend, node) {
+ edge= edgeend->edge;
+ mate= movfeat_findmate(edgeend);
+ if (mate) {
+ trace("("); trace_edgeend(edgeend); trace(")");
+ continue;
+ }
+ edge_delete(edgeend);
+ anychange++;
}
+ trace("\n");
}
- return;
+ trace("movfeatrmstubs pass %d %s\n", pass, anychange?"changed":"alldone");
+ } while (anychange);
+}
- extend_this:
- trace("yes, lhs "); trace_edgeend(leftedge); trace(":\n");
- for (rightedge= node->sides[rightside].head;
- rightedge;
- rightedge= rightedge->next) {
- rightedge->edge->distance += leftedge->edge->distance;
- edge_replumb(rightedge, edgeend_otherend(leftedge)->node);
+static void movfeatsplitnodes(void) {
+ Node *node, *newnode;
+ EdgeEnd *edgeend, *mate;
+ Edge *edge;
+ int side;
+
+ FOR_ALL_NODES(node) {
+ trace("movfeatsplitnodes ");
+ if (!movfeat_isinnernode(node)) continue;
+ if (!node->sides[0].head->next) {
+ trace("pair-trivial\n");
+ continue;
+ }
+ FOR_NODE_EDGEENDS(side,edgeend, node) {
+ edge= edgeend->edge;
+ mate= movfeat_findmate(edgeend);
+ assert(mate);
+ newnode= node_create(masprintf("%sx%d",node->pname,edge->movpos));
+ edgeend_replumb(mate, &newnode->sides[mate->node->side]);
+ edgeend_replumb(edgeend, &newnode->sides[edgeend->node->side]);
}
- edge_delete(leftedge->edge);
- node_surely_orphaned(node);
- trace(" extendsplit operation complete\n");
}
}
-static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
- return &thisend->edge->ends[!thisend->end];
+/*---------- operations - trivial graph redaction etc. ----------*/
+
+static void trivpairnodes(void) {
+ /* Eliminate near-trivial nodes - in this case, ones which have only
+ * two edges, which come in on opposite sides, have the same
+ * subsegspec, and with the two ends identically aligned.
+ */
+ EdgeEnd *leftedge, *rightedge;
+ Node *node;
+
+ FOR_ALL_NODES(node) {
+ trace("trivpairnodes node "); trace_node(node); trace(" ");
+ if (!(count_edges(&node->sides[0])==1 &&
+ count_edges(&node->sides[1])==1)) {
+ trace("no, a non-unitary side\n");
+ continue;
+ }
+ leftedge= node->sides[0].head;
+ rightedge= node->sides[1].head;
+ if (leftedge->edge->subseg != rightedge->edge->subseg) {
+ trace("no, (sub)segments differ\n");
+ continue;
+ }
+ if (leftedge->edge->movpos != rightedge->edge->movpos) {
+ trace("no, movpos's differ\n");
+ continue;
+ }
+ if (leftedge->end == rightedge->end) {
+ trace("no, opposite alignment\n");
+ continue;
+ }
+ trace(" yes:\n");
+ if (!strchr(rightedge->edge->pname, '+')) {
+ rightedge->edge->pname=
+ masprintf("%s+", rightedge->edge->pname);
+ }
+ rightedge->edge->distance += leftedge->edge->distance;
+ edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
+ edge_delete(leftedge);
+ trace(" trivpairnodes operation complete\n");
+ }
}
-static void elimtrivial(void) {
- /* Eliminate trivial nodes: ones which have only two edges, which
- * come in on opposite sides, have the same subsegspec. The two
- * ends are supposed to be identically aligned.
-
- for $lk (@links) {
- $nodeentries[$lk->[0]][$lk->[1]]++;
- $nodeentries[$lk->[1]][$lk->[2]]++;
+static void trivnullnodes(void) {
+ /* Eliminate trivial nodes - ones which have no edges. */
+ Node *node;
+ int side;
+
+ trace("trivnullnodes ");
+ FOR_ALL_NODES(node) {
+ FOR_BOTH(side) {
+ if (node->sides[side].head)
+ goto non_null;
}
- for ($nodenum=0; $nodenum<@nodes; $nodenum++) {
+ node_surely_orphaned(node);
+ non_null:;
+ }
+ trace(" trivnullnodes done.\n");
+}
+
+static void check(const char *why) {
+ Node *node;
+ int alloc_edone, used_edone;
+ typedef struct { Edge *edge; int endsdone; } EdgeDone;
+ EdgeDone *edone, *search_edone;
+ int side;
+ EdgeEnd *edgeend;
+ Edge *edge;
+
+ edone= 0;
+ alloc_edone= used_edone= 0;
+
+ trace("consistency check (%s) ...\n",why);
+ FOR_ALL_NODES(node) {
+ trace(" consistency "); trace_node(node); trace("\n");
+ LIST_CHECKNODE(all_nodes,node);
+ FOR_BOTH(side) {
+ trace(" consistency "); trace_nodeside(&node->sides[side]); trace("\n");
+ assert(node->sides[side].node == node);
+ assert(node->sides[side].side == side);
+ FOR_SIDE_EDGEENDS(edgeend, node,side) {
+ trace(" consistency "); trace_nodeside(&node->sides[side]);
+ trace(" "); trace_edgeend(edgeend); trace("\n");
+ edge= edgeend->edge;
+ LIST_CHECKNODE(node->sides[side], edgeend);
+ assert(edgeend == &edge->ends[edgeend->end]);
+ assert(edgeend->node == &node->sides[side]);
+ if (used_edone==alloc_edone) {
+ alloc_edone += 2; alloc_edone *= 2;
+ edone= MREALLOC(edone, alloc_edone * sizeof(*edone));
+ }
+ for (search_edone= edone;
+ search_edone < edone + used_edone && search_edone->edge != edge;
+ search_edone++);
+ if (search_edone >= edone + used_edone) {
+ search_edone->edge= edge;
+ search_edone->endsdone= 0;
+ used_edone++;
+ }
+ search_edone->endsdone++;
+ assert(search_edone->endsdone <= 2);
+ }
+ }
+ }
+ for (search_edone= edone;
+ search_edone < edone + used_edone;
+ search_edone++) {
+ trace("consistency "); trace_edge(search_edone->edge);
+ trace(" count=%d\n", search_edone->endsdone);
+ assert(search_edone->endsdone == 2);
+ }
+ trace("consistency check (%s) ok\n",why);
+}
+
+static void consistency(void) {
+ check("command-line request");
+}
+
+/*---------- operations - output ----------*/
+
+static void printforneato(void) {
+ Node *node;
+ EdgeEnd *edgeend;
+ Edge *edge;
+ int side;
+
+ output("digraph L {\n");
+
+ FOR_ALL_NODES(node) {
+ output(" n%sO [label=\"%s\"];\n"
+ " n%sI [label=\"+\"];\n",
+ node->pname, node->pname, node->pname);
+ output(" n%sO -> n%sI [len=0.25 arrowsize=0];\n",
+ node->pname, node->pname);
+ FOR_EDGES(edge, node,side,edgeend) {
+ output(" n%s%c -> n%s%c [label=\"%s:",
+ edge->ends[0].node->node->pname,
+ "OI"[edge->ends[0].node->side],
+ edge->ends[1].node->node->pname,
+ "OI"[edge->ends[1].node->side],
+ edge->pname);
+ if (!edge->subseg->segment->segname) {
+ output("?");
+ } else {
+ output(edge->subseg->segment->segname);
+ if (edge->subseg->movfeat) {
+ output("/%s%d",edge->subseg->movfeat,edge->movpos);
+ }
+ }
+ output(":%.2f\"];\n",edge->distance);
+ }
+ }
+ output("}\n");
}
-static void
+
+static void printforforsafety(void) {
+ Node *node;
+ Edge *edge;
+ EdgeEnd *edgeend;
+ int side, end, weight, i;
+ Segment *segment;
+ MovFeat *movfeat;
+ FOR_ALL_NODES(node) {
+ FOR_EDGES(edge, node,side,edgeend) {
+ output("segment ");
+ FOR_BOTH(end) {
+ output("n%s.%d ",
+ edge->ends[end].node->node->pname,
+ edge->ends[end].node->side);
+ }
+ segment= edge->subseg->segment;
+ output(segment->segname);
+ if (segment->n_movfeats>1) {
+ if (!segment->starfeature) {
+ fprintf(stderr,"printforforsafety before movfeatsplitedges!\n");
+ exit(8);
+ }
+ output("/");
+ weight= 1;
+ FOR_SEGMENT_MOVFEATS(i,movfeat, segment) {
+ if (!movfeat->movfeat) continue;
+ output("%s%d", movfeat->movfeat,
+ (edge->movpos / weight) % movfeat->n_positions);
+ weight *= movfeat->n_positions;
+ }
+ output("*%d", edge->movpos);
+ }
+ output(" %f\n", edge->distance);
+ }
+ }
+ output("end\n");
+}
+static void printforlayoutsegjoins(void) {
+ Node *node;
+ EdgeEnd *edgeend, *edgeend2;
+ Segment **segmentp, *segment, *segment2;
+ int side, side2, order, max_order, colour, any_left;
+
+ /* we format segment->u as follows: */
+#define LSJ_U_VERTEXORDER_MASK 0x000000ff
+#define LSJ_U_COLOUR_SHIFT 8
+#define LSJ_U_COLOUR_BITS 16
+#define LSJ_U_COLOUR_UNIT (1<<LSJ_U_COLOUR_SHIFT)
+#define LSJ_U_COLOUR_MASK 0x00ffff00
+#define LSJ_U_SEGEND_DONE 0x01000000
+#define LSJ_U_COLOUR_CLASH 0x02000000
-
-
-
-
- if ((n= count_sides(&node->edges[rightside]))) {
-node->edges[rightside]
-
- $tracep= "extendsplits pass=$pass ".pnode($node)."/$rightback";
- if (@{ $node->{"Edges$leftback"} } != 1) {
- trace("$tracep >1 left edge");
- next;
- }
- ($leftedge,$leftthisfar)= @{ $node->{"Edges$leftback"}[0] };
- $leftthatfar= 1-$leftthisfar;
- $fixedseg= $leftedge->{SubSegSpec};
- @any_wrong= ();
- for $rightedgethisfar (@{ $node->{"Edges$rightback"} }) {
- ($rightedge,$rightthisfar) = @$rightedgethisfar;
- if ($rightedge->{SubSegSpec} !~ m,^(\-?\w+)/\w+$,) {
- @any_wrong= ($rightedge, $leftback, "not moveable");
- } elsif ($1 ne $fixedseg) {
- @any_wrong= ($rightedge, $leftback, "other segment");
- }
- last if @any_wrong;
- }
- if (@any_wrong) {
- trace("$tracep $any_wrong[2] ".
- pedge($any_wrong[0])."::$any_wrong[1]");
- next;
- }
- $any_found++;
- $dist= $leftedge->{Dist};
- ($leftnode,$leftnoderightback)=
- @{ $leftedge->{"Node$leftthatfar"} };
- deleteedge($leftedge);
- for $rightedgethisfar (@{ $node->{"Edges$rightback"} }) {
- ($rightedge,$rightthisfar) = @$rightedgethisfar;
- replumbedge($rightedge,$rightthisfar,
- $leftnode,$leftnoderightback);
-
-
- $rightedge->{Dist} += $leftedge->{Dist};
- $rightedge->{"Node$rightthisfar"}=
-
- $leftnode->{"Edges$leftnoderightback"} =
- [ grep {
- ($grepnode, $grepback) = @$_;
- !($grepnode == $node &&
- $grepback == $leftnoderightback);
- }
- @{ $leftnode->{"Edges$leftnoderightback"} }
- ];
-
-
+ max_order= 0;
+ FOR_ALL_SEGMENTS(segmentp,segment)
+ segment->u= 0;
+
+ FOR_ALL_NODES(node) {
+ output("layer ");
+ FOR_BOTH(side)
+ if (!node->sides[side].head) {
+ output("segterminus");
+ goto one_sided;
+ }
+ output("segjoin");
+ one_sided:
+ output("%d\n", (node->layermin + node->layermax)/2);
+
+ output("abs segjoin_%s %f %f %f\n",node->pname,
+ node->x,node->y,node->a);
+ FOR_NODE_EDGEENDS(side,edgeend, node) {
+ segment= edgeend->edge->subseg->segment;
+ if (segment->u & LSJ_U_SEGEND_DONE) continue;
+ segment->u |= LSJ_U_SEGEND_DONE;
+ assert(~segment->u & LSJ_U_VERTEXORDER_MASK); /* detect overflow */
+ segment->u++;
+ order= segment->u & LSJ_U_VERTEXORDER_MASK;
+ if (order > max_order) max_order= order;
+ output("segend segjoin_%s %s\n",node->pname, segment->segname);
+ }
+ output("\n");
+ FOR_ALL_SEGMENTS(segmentp,segment)
+ segment->u &= ~LSJ_U_SEGEND_DONE;
+ }
+
+ /* Welsh and Powell's graph colouring algorithm
+ * (Wikipedia Graph_coloring) */
+ output("# max-order %d\n",max_order);
+
+ for (colour=LSJ_U_COLOUR_UNIT, any_left=1;
+ any_left;
+ colour+=LSJ_U_COLOUR_UNIT) {
+ output("# colour %x\n", colour);
+ assert(!(colour & ~LSJ_U_COLOUR_MASK));
+ something_done:
+ any_left= 0;
+ FOR_ALL_SEGMENTS(segmentp,segment)
+ segment->u &= ~LSJ_U_COLOUR_CLASH;
+
+ FOR_ALL_NODES(node)
+ FOR_NODE_EDGEENDS(side,edgeend, node) {
+ segment= edgeend->edge->subseg->segment;
+ if (colour == (segment->u & LSJ_U_COLOUR_MASK)) {
+ output("# already %s\n", segment->segname);
+ FOR_NODE_EDGEENDS(side2,edgeend2, node) {
+ segment2= edgeend2->edge->subseg->segment;
+ output("# therefore-not %s\n", segment2->segname);
+ segment2->u |= LSJ_U_COLOUR_CLASH;
+ }
+ }
+ }
+
+ for (order=max_order; order>0; order--) { /* idiot-sort */
+ output("# order %d\n", order);
+ FOR_ALL_SEGMENTS(segmentp,segment)
+ if ((segment->u & LSJ_U_VERTEXORDER_MASK) == order) {
+ if (segment->u & LSJ_U_COLOUR_MASK) continue;
+ any_left= 1;
+ if (segment->u & LSJ_U_COLOUR_CLASH) {
+ output("# still-clashes %s\n", segment->segname);
+ continue;
+ }
+ segment->u |= colour;
+ output("# coloured %s\n", segment->segname);
+ goto something_done;
+ } else {
+ output("# (skip %s %x)\n", segment->segname,segment->u);
+ }
}
+ }
+
+ FOR_ALL_SEGMENTS(segmentp,segment) {
+ int tcolour= segment->u & LSJ_U_COLOUR_MASK;
+ const double val1=0.75, val2=0.50;
+ double value;
+ if (!tcolour) continue;
+ value= val1 +
+ (tcolour - LSJ_U_COLOUR_UNIT*2) * (val1-val2) /
+ (colour - LSJ_U_COLOUR_UNIT*2);
+ output("segcmap %s %f setgray\n", segment->segname,value);
+ }
+}
+
+/*---------- main program ----------*/
+
+typedef struct {
+ const char *name;
+ void (*fn)(void);
+} OpInfo;
+
+static const OpInfo opinfos[]= {
+#define OI(x) { #x, x },
+ OI(printforneato)
+ OI(printforforsafety)
+ OI(printforlayoutsegjoins)
+ OI(consistency)
+ OI(movfeatsplitedges)
+ OI(movfeatrmstubs)
+ OI(movfeatsplitnodes)
+ OI(trivpairnodes)
+ OI(trivnullnodes)
+ { 0,0 }
+};
+
+static void usage(void) {
+ const OpInfo *oi;
+
+ fprintf(stderr,
+ "usage: .../redactgraph <operation> [<operation>...]\n"
+ "operations:\n");
+ for (oi=opinfos; oi->name; oi++) {
+ fprintf(stderr," %s\n",oi->name);
+ }
+ fflush(stderr);
+ exit(8);
+}
+
+int main(int argc, const char *const *argv) {
+ const OpInfo *oi;
+ const char *arg;
+
+ if (!argv[0] || !argv[1]) usage();
+
+ while ((arg= *++argv)) {
+ for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
+ if (!oi->name) usage();
+ oi->fn();
+ }
+ trace("\n");
+ output("\n");
+ if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }
+ exit(0);
+}
~ijackson / trains.git / blobdiff