10 #include "graph-data.h"
12 /*---------- output processing ----------*/
14 static void voutputstuff(int trace, const char *fmt, va_list al) {
15 static struct OutputBuf {
21 char *s, *p, *newline;
25 r= vasprintf(&s,fmt,al); if (r<0) { perror("vasprintf"); exit(16); }
29 newline= strchr(p,'\n');
30 if (newline) { *newline= 0; }
32 if (l+b->used > b->allocd) {
34 b->buf= realloc(b->buf, b->allocd);
35 if (!b->buf) { perror("realloc voutputstuff"); exit(16); }
37 memcpy(b->buf+b->used, p, l);
42 if (trace) { fputs("# ",stdout); }
43 fwrite(b->buf, 1,b->used, stdout);
45 if (ferror(stdout) || fflush(stdout)) {
46 perror("stdout voutputstuff"); exit(12);
56 static void v##fn(const char *fmt, va_list al) { \
57 voutputstuff(tr,fmt,al); \
59 static void fn(const char *fmt, ...) { \
68 /*---------- general graph-manipulation and printing stuff ----------*/
70 static void trace_node(Node *node) {
74 static void trace_edgeend(EdgeEnd *edge) {
75 trace("n%p%c",edge->node->node,"OI"[edge->node->side]);
78 static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
79 return &thisend->edge->ends[!thisend->end];
82 static int count_edges(const NodeSide *node) {
86 for (count=0, edge=node->head;
88 count++, edge=edge->next);
92 static void edgeend_disconnect(EdgeEnd *toremove) {
93 LIST_UNLINK(*toremove->node, toremove);
96 static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) {
97 edgeend_disconnect(tomove);
98 LIST_LINK_TAIL(*newtarget, tomove);
99 tomove->node= newtarget;
102 static void edge_delete(Edge *edge) {
103 edgeend_disconnect(&edge->ends[0]);
104 edgeend_disconnect(&edge->ends[1]);
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);
113 /*---------- operations ----------*/
115 static void extendsplits(void) {
116 int pass=0, rightside, n;
118 EdgeEnd *leftedge, *rightedge;
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:
127 * <---l---> <----l'---> <---------(l+l')------>
129 * *----A1---*----A1/P0--* becomes *--------A1/P0----------*
130 * `---A1/P1---* `-------A1/P1-----------*
132 * <----l''---> <---------(l+l'')------>
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);
145 leftedge= node->sides[!rightside].head;
146 if (leftedge->edge->subseg->movfeat) {
147 trace("no: lhs moveable\n");
150 if (!node->sides[rightside].head) {
151 trace("no: rhs absent\n");
154 for (rightedge= node->sides[rightside].head;
156 rightedge= rightedge->next) {
157 if (!rightedge->edge->subseg->movfeat) {
158 trace("no: rhs fixed ("); trace_edgeend(rightedge); trace(")\n");
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");
178 trace("yes, lhs "); trace_edgeend(leftedge); trace(":\n");
179 for (rightedge= node->sides[rightside].head;
181 rightedge= rightedge->next) {
182 rightedge->edge->distance += leftedge->edge->distance;
183 edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node);
185 edge_delete(leftedge->edge);
186 node_surely_orphaned(node);
187 trace(" extendsplit operation complete\n");
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.
196 EdgeEnd *leftedge, *rightedge;
197 Node *node, *next_node;
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");
207 leftedge= node->sides[0].head;
208 rightedge= node->sides[1].head;
209 if (leftedge->edge->subseg != rightedge->edge->subseg) {
210 trace("no, (sub)segments differ\n");
213 if (leftedge->edge->movpos != rightedge->edge->movpos) {
214 trace("no, movpos's differ\n");
217 if (leftedge->end == rightedge->end) {
218 trace("no, opposite alignment\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");
230 static void consistency(void) {
233 static void printforneato(void) {
239 output("digraph L {\n");
241 for (node=all_nodes.head; node; node=node->next) {
242 output(" n%pO [label=\"O\"];\n"
243 " n%pI [label=\"+\"];\n",
245 output(" n%pO -> n%pI [len=0.25 arrowsize=0];\n",
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 */
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) {
257 output(edge->subseg->segment->segname);
258 if (edge->subseg->movfeat) {
259 output("/%s%d",edge->subseg->movfeat,edge->movpos);
274 static const OpInfo opinfos[]= {
275 #define OI(x) { #x, x },
283 static void usage(void) {
287 "usage: .../redactgraph <operation> [<operation>...]\n"
289 for (oi=opinfos; oi->name; oi++) {
290 fprintf(stderr," %s\n",oi->name);
296 int main(int argc, const char *const *argv) {
300 if (!argv[0] || !argv[1]) usage();
302 while ((arg= *++argv)) {
303 for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++);
304 if (!oi->name) usage();
309 if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); }