layout/redactgraph.c

   1 /**/
   2
   3 typedef struct Edge Edge;
   4 typedef struct EdgeEnd EdgeEnd;
   5 typedef struct Node Node;
   6 typedef struct NodeSideRef NodeSideRef;
   7
   8 struct EdgeEnd {
   9   EdgeNode *back, *next; /* other ends at same side of same node */
  10   Edge *edge; /* edge->ends[end].edge==edge */
  11   int end; /* edge->ends[end].edge==end */
  12   NodeSide *node;
  13 };
  14
  15 struct Edge {
  16   double distance;
  17   const char *segment, *movfeatpos;
  18   EdgeEnd ends[2];
  19 };
  20
  21 typedef struct {
  22   Node *node; /* node->edges[side].node==node */
  23   int side; /* node->edges[side].side==side */
  24   EdgeEnd *head, *tail;
  25 } NodeSide;
  26
  27 struct Node {
  28   Node *back, *next;
  29   NodeSide sides[2];
  30 };
  31
  32 static Node *nodes_head, *nodes_tail;
  33
  34 static void extendsplits(void) {
  35   /*
  36    * Whenever we have a node which has one or more moveable feature
  37    * subsegments, part of the same moveable feature, on one side, and
  38    * fixed portion of the same segment on the other, we eliminate
  39    * the fixed portion and add its length to both the moveables,
  40    * so that we have one subsegspec for the whole of each position:
  41    *
  42    *    <---l---> <----l'--->             <---------(l+l')------>
  43    *
  44    *   *----A1---*----A1/P0--*  becomes  *--------A1/P0----------*
  45    *              `---A1/P1---*           `-------A1/P1-----------*
  46    *
  47    *              <----l''--->            <---------(l+l'')------>
  48    */
  49
  50   for (;;) {
  51     pass++;
  52     for (node=nodes_head; node; node=node->next) {
  53       for (rightside=0; rightside<2; rightside++) {
  54         trace("extendsplit pass %d node ",pass); trace_node(node);
  55         trace("/%d ",rightside);
  56         if ((n= count_edges(&node->sides[!rightside])) != 1) {
  57           trace("no: lhs edges=%d\n", n);
  58           goto no_extend_this;
  59         }
  60         leftedge= node->sides[!rightside].head;
  61         if (leftedge->edge->movfeatpos) {
  62           trace("no: lhs moveable\n");
  63           goto no_extend_this;
  64         }
  65         if (!node->sides[rightside].head) {
  66           trace("no: rhs absent\n");
  67           goto no_extend_this;
  68         }
  69         for (rightedge= node->sides[rightside].head;
  70              rightedge;
  71              rightedge= rightedge->next) {
  72           if (!rightedge->edge->movfeatpos) {
  73             trace("no: rhs fixed ("); trace_edgeend(rightedge); trace(")\n");
  74             goto no_extend_this;
  75           }
  76           if (strcmp(leftedge->edge->segment, rightedge->edge->segment)) {
  77             trace("no: lhs seg %s, rhs seg %s (",
  78                   leftedge->edge->segment
  79                   rightedge->edge->segment);
  80             trace_edgeend(rightedge); trace(")\n");
  81             goto no_extend_this;
  82           }
  83         }
  84         goto extend_this;
  85
  86       no_extend_this:;
  87       }
  88     }
  89     return;
  90
  91   extend_this:
  92     trace("yes, lhs "); trace_edgeend(leftedge); trace(":\n");
  93     for (rightedge= node->sides[rightside].head;
  94          rightedge;
  95          rightedge= rightedge->next) {
  96       rightedge->edge->distance += leftedge->edge->distance;
  97       edge_replumb(rightedge, edgeend_otherend(leftedge)->node);
  98     }
  99     edge_delete(leftedge->edge);
 100     node_surely_orphaned(node);
 101     trace(" extendsplit operation complete\n");
 102   }
 103 }
 104
 105 static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) {
 106   return &thisend->edge->ends[!thisend->end];
 107 }
 108
 109 static void elimtrivial(void) {
 110   /* Eliminate trivial nodes: ones which have only two edges, which
 111    * come in on opposite sides, have the same subsegspec, and with the
 112    * two ends identically aligned.
 113    */
 114   for (node=nodes_head; node; node=next_node) {
 115     next_node=node->next;
 116     trace("elimtrivial node "); trace_node(node); trace(" ");
 117     if (!(count_edges(&node->sides[0])==1 &&
 118           count_edges(&node->sides[1])==1)) {
 119       trace("no, a non-unitary side\n");
 120       continue;
 121     }
 122     leftedge= node->sides[0].head;
 123     rightedge= node->sides[0].head;
 124     if (strcmp(leftedge->edge.segment,rightedge->edge.segment)) {
 125       trace("no, segments differ\n");
 126       continue;
 127     }
 128     if (!!leftedge->edge.movfeatpos != !!rightedge->edge.movfeatpos ||
 129         strcmp(leftedge->edge.movfeatpos, rightedge->edge.movfeatpos)) {
 130       trace("no, movfeatpos's differ\n");
 131       continue;
 132     }
 133     if (leftedge->end == rightedge->end) {
 134       trace("no, opposite alignment\n");
 135       continue;
 136     }
 137     trace(" yes:\n");
 138     rightedge->edge->distance += leftedge->edge->distance;
 139     edge_replumb(rightedge, edgeend_otherend(leftedge)->node);
 140     edge_delete(leftedge->edge);
 141     node_surely_orphaned(node);
 142     trace(" elimtrivial operation complete\n");
 143   }
 144 }
 145
 146
 147
 148
 149
 150
 151         if ((n= count_sides(&node->edges[rightside]))) {
 152 node->edges[rightside]
 153
 154         $tracep= "extendsplits pass=$pass ".pnode($node)."/$rightback";
 155                 if (@{ $node->{"Edges$leftback"} } != 1) {
 156                     trace("$tracep >1 left edge");
 157                     next;
 158                 }
 159                 ($leftedge,$leftthisfar)= @{ $node->{"Edges$leftback"}[0] };
 160                 $leftthatfar= 1-$leftthisfar;
 161                 $fixedseg= $leftedge->{SubSegSpec};
 162                 @any_wrong= ();
 163                 for $rightedgethisfar (@{ $node->{"Edges$rightback"} }) {
 164                     ($rightedge,$rightthisfar) = @$rightedgethisfar;
 165                     if ($rightedge->{SubSegSpec} !~ m,^(\-?\w+)/\w+$,) {
 166                         @any_wrong= ($rightedge, $leftback, "not moveable");
 167                     } elsif ($1 ne $fixedseg) {
 168                         @any_wrong= ($rightedge, $leftback, "other segment");
 169                     }
 170                     last if @any_wrong;
 171                 }
 172                 if (@any_wrong) {
 173                     trace("$tracep $any_wrong[2] ".
 174                           pedge($any_wrong[0])."::$any_wrong[1]");
 175                     next;
 176                 }
 177                 $any_found++;
 178                 $dist= $leftedge->{Dist};
 179                 ($leftnode,$leftnoderightback)=
 180                     @{ $leftedge->{"Node$leftthatfar"} };
 181                 deleteedge($leftedge);
 182                 for $rightedgethisfar (@{ $node->{"Edges$rightback"} }) {
 183                     ($rightedge,$rightthisfar) = @$rightedgethisfar;
 184                     replumbedge($rightedge,$rightthisfar,
 185                                 $leftnode,$leftnoderightback);
 186
 187
 188                     $rightedge->{Dist} += $leftedge->{Dist};
 189                     $rightedge->{"Node$rightthisfar"}=
 190
 191                 $leftnode->{"Edges$leftnoderightback"} =
 192                     [ grep {
 193                         ($grepnode, $grepback) = @$_;
 194                         !($grepnode == $node &&
 195                           $grepback == $leftnoderightback);
 196                     }
 197                      @{ $leftnode->{"Edges$leftnoderightback"} }
 198                      ];
 199
 200
 201
 202     }