-/**/
+/*
+ * 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.
+ */
#include <stdarg.h>
#include <string.h>
return count;
}
-static Edge *makeedge(const char *pname, double distance,
- MovFeat *subseg, int movpos) {
+static Edge *edge_create(const char *pname, double distance,
+ MovFeat *subseg, int movpos) {
Edge *e;
int end;
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;
+}
+
+/* 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);
edgeend_attach(tomove,newtarget);
}
-static void edge_delete(Edge *edge) {
- edgeend_detach(&edge->ends[0]);
- edgeend_detach(&edge->ends[1]);
+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("]");
}
LIST_UNLINK(all_nodes, node);
}
-/*---------- operations ----------*/
+/*---------- 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
*
* The conversion has two stages:
*
- * FIRST STAGE (movfeatmultedges):
+ * 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.
* *----A1/P0----* becomes *----A1/P0J0----*
* `---A1/P0J1---'
*
- * SECOND STAGE:
+ * SECOND STAGE (movfeatrmstubs):
*
- * We split nodes: every node which has (only) edges which are part
- * of the same segment 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.
+ * 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:
*
- * For example, when we start with:
+ * 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.
*
- * ,---A1/P0J0---.
- * ...*----A1/P0J1----*---A1/P0J1---*...
- * `---A1/P1J0---' `--A1/P1J1--'
- * `--A1/P1J1--'
+ * For example (neglecting direction for the purposes of the
+ * example), when we start with:
*
- * the middle node is split like this (neglecting directions for
- * clarity):
+ * ,---A1/P0J0---.
+ * ...*----A1/P0J1----*---A1/P0J1---*...
+ * `---A1/P1J0---' `--A1/P1J1--'
+ * `--A1/P1J1--'
*
- * ,---A1/P0J0----*
- * ...*----A1/P0J1----*---A1/P0J1---*...
- * `---A1/P1J0----* /
- * `--A1/P1J1----*---A1/P1J1-'
+ * the edges A1/P0J0 and A1/P1J1 are not matched on the RHS of the node,
+ * so they are removed:
*
- * and then the stub edges and nodes are removed, leaving this:
+ * ...*----A1/P0J1----*---A1/P0J1---*...
+ * `---A1/P1J0---' `--A1/P1J1--'
*
- * ...*----A1/P0J1----*---A1/P0J1---*...
- * \ /
- * `--A1/P1J1----*---A1/P1J1-'
*
- * The actual implementation of the second stage simply considers
- * whether to create each node as it goes along, rather than
- * inventing nodes merely to delete them.
+ * 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--'
*/
-static void movfeatmultedges(void) {
+static void movfeatsplitedges(void) {
Node *node;
int side, l, i, weight, combpos, end;
EdgeEnd *edgeend;
MovFeat *subseg, *starfeature, *loopfeat;
char *featstr;
- trace("movfeatmultedges ...\n");
+ trace("movfeatsplitedges ...\n");
FOR_ALL_NODES(node) {
FOR_EDGES(edge, node,side,edgeend) {
subseg= edge->subseg;
segment= subseg->segment;
- trace("movfeatmultedges "); trace_edge(edge);
+ 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; }
trace(" ...\n");
for (combpos=0; combpos<starfeature->n_positions; combpos++) {
- trace("movfeatmultedges "); trace_combpos(combpos,segment);
+ trace("movfeatsplitedges "); trace_combpos(combpos,segment);
if ((combpos / weight) % subseg->n_positions != edge->movpos) {
trace(" excluded\n");
continue;
}
- newedge= makeedge(masprintf("%s/*%d",edge->pname,combpos),
- edge->distance,
- starfeature,
- combpos);
+ 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(edge);
- /* edge_delete doesn't destroy or modify this edge node,
- * so we can safely carry on with this loop, which will
- * now carry on with the next edge - either one we've just
- * added, or the one which was next before we started messing
- * about.
- */
+ edge_delete(edgeend);
+ }
+ }
+ trace("movfeatsplitedges complete.\n");
+}
+
+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");
+ }
+ trace("movfeatrmstubs pass %d %s\n", pass, anychange?"changed":"alldone");
+ } while (anychange);
+}
+
+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]);
}
}
- trace("movfeatmultedges 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, and with the
- * two ends identically aligned.
+/*---------- 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, *next_node;
+ Node *node;
FOR_ALL_NODES(node) {
- next_node=node->next;
- trace("elimtrivial node "); trace_node(node); trace(" ");
+ 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;
}
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->edge);
+ edge_delete(leftedge);
+ trace(" trivpairnodes operation complete\n");
+ }
+}
+
+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;
+ }
node_surely_orphaned(node);
- trace(" elimtrivial operation complete\n");
+ non_null:;
}
-}
+ trace(" trivnullnodes done.\n");
+}
static void check(const char *why) {
Node *node;
trace(" consistency "); trace_nodeside(&node->sides[side]); trace("\n");
assert(node->sides[side].node == node);
assert(node->sides[side].side == side);
- for (edgeend=node->sides[side].head; edgeend; edgeend=edgeend->next) {
+ FOR_SIDE_EDGEENDS(edgeend, node,side) {
trace(" consistency "); trace_nodeside(&node->sides[side]);
trace(" "); trace_edgeend(edgeend); trace("\n");
check("command-line request");
}
+/*---------- operations - output ----------*/
+
static void printforneato(void) {
Node *node;
EdgeEnd *edgeend;
output("}\n");
}
+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
+
+ 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",node->pname);
+ FOR_NODE_EDGEENDS(side,edgeend, node)
+ output("_%s",edgeend->edge->subseg->segment->segname);
+ output(" %f %f %f\n", 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 %s\n",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);
static const OpInfo opinfos[]= {
#define OI(x) { #x, x },
OI(printforneato)
+ OI(printforforsafety)
+ OI(printforlayoutsegjoins)
OI(consistency)
- OI(movfeatmultedges)
- OI(elimtrivial)
+ OI(movfeatsplitedges)
+ OI(movfeatrmstubs)
+ OI(movfeatsplitnodes)
+ OI(trivpairnodes)
+ OI(trivnullnodes)
{ 0,0 }
};
~ijackson / trains.git / blobdiff