From cfbdb6bf8b495362d5906914609cccd15a950f84 Mon Sep 17 00:00:00 2001 From: ian Date: Sun, 13 Mar 2005 18:49:06 +0000 Subject: [PATCH] C redactgraph going well I think --- layout/extractgraph | 82 -------------------- layout/redactgraph.c | 180 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 180 insertions(+), 82 deletions(-) create mode 100644 layout/redactgraph.c diff --git a/layout/extractgraph b/layout/extractgraph index c4399a8..c070dd9 100755 --- a/layout/extractgraph +++ b/layout/extractgraph @@ -154,90 +154,8 @@ sub readin () { } } -sub extendsplits () { - # 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: - # - # <---l---> <----l'----> <--------(l+l')------> - # - # *----A1---*----A1/P0--* becomes *--------A1/P0----------* - # `---A1/P1---* `-------A1/P1-----------* - # - # <----l''---> <--------(l+l'')------> - - $pass= 0; - for (;;) { - $pass++; - trace("extendsplits pass $pass"); - $any_found= 0; - for $node (@nodes) { - for ($rightback=0; $rightback<2; $rightback++) { - $leftback= 1-$rightback; - $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"} } - ]; - - - - } -sub elimtrivial () { - # eliminate trivial nodes: ones which have only two edges, which - # come in on opposite sides, and have the same subsegspec - - for $lk (@links) { - $nodeentries[$lk->[0]][$lk->[1]]++; - $nodeentries[$lk->[1]][$lk->[2]]++; - } - for ($nodenum=0; $nodenum<@nodes; $nodenum++) { - -} readin(); splitcontin(); diff --git a/layout/redactgraph.c b/layout/redactgraph.c new file mode 100644 index 0000000..05acebf --- /dev/null +++ b/layout/redactgraph.c @@ -0,0 +1,180 @@ +/**/ + +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; +}; + +struct Edge { + double distance; + const char *segment, *movfeatpos; + EdgeEnd ends[2]; +}; + +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]; +}; + +static Node *nodes_head, *nodes_tail; + +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: + * + * <---l---> <----l'----> <--------(l+l')------> + * + * *----A1---*----A1/P0--* becomes *--------A1/P0----------* + * `---A1/P1---* `-------A1/P1-----------* + * + * <----l''---> <--------(l+l'')------> + */ + + 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; + } + leftedge= node->sides[!rightside].head; + if (leftedge->edge->movfeatpos) { + trace("no: lhs moveable\n"); + goto no_extend_this; + } + if (!node->sides[rightside].head) { + trace("no: rhs absent\n"); + goto no_extend_this; + } + 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; + } + } + goto extend_this; + + no_extend_this:; + } + } + return; + + 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); + } + 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]; +} + +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]]++; + } + for ($nodenum=0; $nodenum<@nodes; $nodenum++) { + +} +static void + + + + + + + + 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"} } + ]; + + + + } -- 2.30.2