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.  The two
 112    * ends are supposed to be identically aligned.
 113
 114     for $lk (@links) {
 115         $nodeentries[$lk->[0]][$lk->[1]]++;
 116         $nodeentries[$lk->[1]][$lk->[2]]++;
 117     }
 118     for ($nodenum=0; $nodenum<@nodes; $nodenum++) {
 119
 120 }
 121 static void
 122
 123
 124
 125
 126
 127
 128
 129         if ((n= count_sides(&node->edges[rightside]))) {
 130 node->edges[rightside]
 131
 132         $tracep= "extendsplits pass=$pass ".pnode($node)."/$rightback";
 133                 if (@{ $node->{"Edges$leftback"} } != 1) {
 134                     trace("$tracep >1 left edge");
 135                     next;
 136                 }
 137                 ($leftedge,$leftthisfar)= @{ $node->{"Edges$leftback"}[0] };
 138                 $leftthatfar= 1-$leftthisfar;
 139                 $fixedseg= $leftedge->{SubSegSpec};
 140                 @any_wrong= ();
 141                 for $rightedgethisfar (@{ $node->{"Edges$rightback"} }) {
 142                     ($rightedge,$rightthisfar) = @$rightedgethisfar;
 143                     if ($rightedge->{SubSegSpec} !~ m,^(\-?\w+)/\w+$,) {
 144                         @any_wrong= ($rightedge, $leftback, "not moveable");
 145                     } elsif ($1 ne $fixedseg) {
 146                         @any_wrong= ($rightedge, $leftback, "other segment");
 147                     }
 148                     last if @any_wrong;
 149                 }
 150                 if (@any_wrong) {
 151                     trace("$tracep $any_wrong[2] ".
 152                           pedge($any_wrong[0])."::$any_wrong[1]");
 153                     next;
 154                 }
 155                 $any_found++;
 156                 $dist= $leftedge->{Dist};
 157                 ($leftnode,$leftnoderightback)=
 158                     @{ $leftedge->{"Node$leftthatfar"} };
 159                 deleteedge($leftedge);
 160                 for $rightedgethisfar (@{ $node->{"Edges$rightback"} }) {
 161                     ($rightedge,$rightthisfar) = @$rightedgethisfar;
 162                     replumbedge($rightedge,$rightthisfar,
 163                                 $leftnode,$leftnoderightback);
 164
 165
 166                     $rightedge->{Dist} += $leftedge->{Dist};
 167                     $rightedge->{"Node$rightthisfar"}=
 168
 169                 $leftnode->{"Edges$leftnoderightback"} =
 170                     [ grep {
 171                         ($grepnode, $grepback) = @$_;
 172                         !($grepnode == $node &&
 173                           $grepback == $leftnoderightback);
 174                     }
 175                      @{ $leftnode->{"Edges$leftnoderightback"} }
 176                      ];
 177
 178
 179
 180     }