1#ifndef RNAPUZZLER_SIBLING_INTERSCTIONS_H
2#define RNAPUZZLER_SIBLING_INTERSCTIONS_H
3
4/*
5 *      RNApuzzler handle sibling intersections
6 *
7 *      c  Daniel Wiegreffe, Daniel Alexander, Dirk Zeckzer
8 *      ViennaRNA package
9 */
10
11#include <stdlib.h>
12#include <math.h>
13
14#include "ViennaRNA/utils/basic.h"
15
16#include "../headers/configtree_struct.h"
17#include "configtree.inc"
18#include "definitions.inc"
19#include "vector_math.inc"
20#include "intersectLevelTreeNodes.inc"
21#include "boundingWedge.inc"
22#include "calcDeltas.inc"
23#include "handleConfigChanges.inc"
24
25/**
26 * Check and fix intersections between all siblings of the current node.
27 *
28 * @param node: node to check
29 * @param puzzler: vrna_plot_options_puzzler_t
30 */
31PRIVATE short
32checkSiblings(treeNode                    *node,
33              vrna_plot_options_puzzler_t *puzzler);
34
35
36/**
37 * @brief fixIntersectionOfSiblings
38 *      Try to fix intersections of sibling subtrees at their common ancestor.
39 * @param tree
40 *      common ancestor of intersecting subtrees
41 * @param left
42 * @param right
43 * @param deltaCfg
44 * @param puzzler
45 * @return
46 *      1 if something was changed, 0 otherwise
47 */
48PRIVATE short
49fixIntersectionOfSiblings(treeNode                    *tree,
50                          const int                   left,
51                          const int                   right,
52                          double                      *deltaCfg,
53                          vrna_plot_options_puzzler_t *puzzler)
54{
55  double  wedgeMin, wedgeMax;
56
57  getBoundingWedge(tree, right, &wedgeMin, &wedgeMax);
58  double  minAngle = wedgeMin;
59  getBoundingWedge(tree, left, &wedgeMin, &wedgeMax);
60  double  maxAngle    = wedgeMax;
61  double  targetAngle = minAngle - maxAngle;
62
63  short   changed = 0;
64  if (targetAngle < 0) {
65    targetAngle = fmax(targetAngle, -MATH_PI_HALF);     /* limit the angle to avoid malformed structures */
66    double changedAngle = calcDeltas(tree,
67                                     getParent(tree),
68                                     left,
69                                     right,
70                                     (-1) * targetAngle,
71                                     puzzler,
72                                     deltaCfg);
73
74    if (changedAngle != 0.0) {
75      treeNode  *leftNode   = getChild(tree, left);
76      treeNode  *rightNode  = getChild(tree, right);
77
78      /* apply all changes */
79      changed = checkAndApplyConfigChanges(tree, deltaCfg, siblings, puzzler);
80    }
81  }
82
83  return changed;
84}
85
86
87/**
88 * @brief handleIntersectionOfSiblings
89 *      Try to fix intersections of sibling subtrees at their common ancestor.
90 * @param tree
91 *      common ancestor of intersecting subtrees
92 * @param listOfIntersections
93 *      list of pairs of indices of subtrees that are intersecting.
94 *      [numberOfIntersections, [i1, j1], [i2, j2], ...]
95 * @return
96 *      1 if something was changed, 0 otherwise
97 */
98PRIVATE short
99handleIntersectionOfSiblings(treeNode                     *tree,
100                             const int                    *listOfIntersections,
101                             vrna_plot_options_puzzler_t  *puzzler)
102{
103  char *fnName = "FIX INTERSECTION OF SIBLINGS";
104
105  /*
106   * idea:
107   * measure each intersection by calculating an overlap angle
108   * increase the spaces between intersectors and decrease spaces that are not between them
109   * distribute the overlap angle equally to all participating spaces
110   * check for new or remaining intersections (at the end)
111   */
112
113  if (puzzler->numberOfChangesAppliedToConfig > puzzler->maximumNumberOfConfigChangesAllowed)
114    return -1;
115
116  short   changed           = 0;
117  int     intersectionCount = listOfIntersections[0];
118
119  int     childCount  = tree->childCount;
120  int     configSize  = childCount + 1;
121
122  double  *deltaCfg = (double *)vrna_alloc(configSize * sizeof(double));
123
124  /* init deltas with zero */
125  for (int i = 0; i < configSize; i++)
126
127    deltaCfg[i] = 0.0;
128
129  /* fix intersections of siblings */
130  for (int k = 0; k < intersectionCount; k++) {
131    /* for all intersections - start */
132
133    int left  = listOfIntersections[2 * k + 1];
134    int right = listOfIntersections[2 * k + 2];
135
136    changed = fixIntersectionOfSiblings(tree, left, right, deltaCfg, puzzler);
137
138    if (changed)
139
140      break;
141  }
142
143  free(deltaCfg);
144
145  return changed;
146}
147
148
149PRIVATE short
150checkSiblings(treeNode                    *node,
151              vrna_plot_options_puzzler_t *puzzler)
152{
153  char  *fnName = "CHECK SIBLINGS";
154  short ret     = _false;
155
156  int   childCount = node->childCount;
157  /* create array to store all information about overlapping neighbors */
158  int   *intersectorsBranches = (int *)vrna_alloc((childCount * childCount) * sizeof(int));
159
160  for (int i = 0; i < childCount * childCount; i++)
161
162    intersectorsBranches[i] = -1;
163
164  /* actually check for those intersections */
165  for (int i = 0; i < childCount; i++) {
166    int intersectorsCount = 0;
167
168    for (int j = i + 1; j < childCount; j++) {
169      treeNode  *childI = getChild(node, i);
170      treeNode  *childJ = getChild(node, j);
171
172      if (intersectTrees(childI, childJ)) {
173        intersectorsBranches[i * childCount + intersectorsCount] = j;
174        intersectorsCount++;
175      }
176    }
177  }
178
179  /* and count them */
180  int intersectionCount = 0;
181
182  for (int i = 0; i < (childCount * childCount); i++) {
183    if (intersectorsBranches[i] != -1)
184
185      intersectionCount++;
186  }
187
188  if (intersectionCount > 0) {
189    ret |= _intersect;
190
191    /*
192     * transform intersection information into format
193     * [ count, [intersector_a, intersector_b], [intersector_a, intersector_b], ... ]
194     * where count states how many pairs of a/b are there
195     * the i-th intersection has index a=2*i+1; b=2*i+2
196     */
197    int *listOfIntersections = (int *)vrna_alloc((1 + 2 * intersectionCount) * sizeof(int));
198    listOfIntersections[0] = intersectionCount;
199
200    int counter = 0;
201    for (int i = 0; i < (childCount * childCount); i++) {
202      if (intersectorsBranches[i] != -1) {
203        listOfIntersections[2 * counter + 1]  = i / childCount;
204        listOfIntersections[2 * counter + 2]  = intersectorsBranches[i];
205        counter++;
206      }
207    }
208
209    /* resolve all of those intersections for this node's subtrees */
210    short retFix = handleIntersectionOfSiblings(node, listOfIntersections, puzzler);
211
212    if (retFix < 0)
213      ret = retFix;
214    else if (retFix)
215      ret |= _changed;
216
217    free(listOfIntersections);
218  }
219
220  free(intersectorsBranches);
221
222  return ret;
223}
224
225
226#endif
227