Reduce Redundant Array Flipping by Using a Planning Tree

[MatthewMcGonagle]

Try to reduce redundant array flipping by using a tree to store which parts of the array need to be flipped, and then do the flipping when the tree is large enough or for some other condition.

For example, suppose we have the array:

i     0 1 2 3 4 5 6 7 8 9
a[i]  0 1 2 3 4 5 6 7 8 9

and suppose we flip a[2:8] and then flip a[4:9]. We see that the sub-array a[4:8] gets flipped twice, which is unnecessary.

Now, when doing comparisons for energy increase/decrease, we need to know which direction the cycle is going; we don't want to reconnect in such a way that the cycle breaks into two closed cycles.

Perhaps, we can "plan" what to flip using a tree; the internal nodes represent splits in the direction of the array and also store which vertex they switch with. The internal nodes are ordered by the index of the vertex (before any flipping). Finally the leaf nodes represent the directions of the cycle relative to the array for array elements between closest internal nodes.

Let us look at the example above. The first flip a[2:8] gives a tree

    2 
  /  \
R      8
      /   \
    L      R

where R means the cycle moves to the right and L means the cycle moves to the left; we have intentionally left off the switch information from the internal nodes.

The next flip a[4:9] gives

    2
  /  \
R      8
      /     \
    4          9
  /  \        /  \
R     L     L    R

Given the planning tree, we should be able to make all flips without doing any redundant operations.

The tree should probably kept from growing larger than some size (say log(N) where N is the number of vertices). Also, we could force the flips to be done if the a vertex comes up again (or maybe one of its neighbors).

Note that the left endpoint of a flip causes a change in the direction to the right, and vice versa for the right endpoint of a flip.

Finally, if we decide to do all flips if we find the same vertex already in the tree, we must deal with whether the other vertex in the flip was added to the tree (or be careful not to do so until we know that both vertices in a flip aren't already in the tree).

Edit: Fixed order in tree for children of node 4. Note, putting a split at an "L" leaf node makes the new leaf nodes be in the opposite order "R" "L", i.e. left child = "R" and right child = "L".

Finally, should consider initializing the empty tree as an "R" node.

[MatthewMcGonagle]

This feature can probably be implemented by keeping a set of flip points (i.e. flip orientation between forwards and backwards). If we try to flip a point that is a neighbor of a previous flip point, then do all of the flips and restart the list with the new flips.

Edit: On second thought, a set isn't enough. We need to keep that hierarchical structure. For example, switching 3 and 7, and then switch 5 and 9. The orders of the segments are:

• (0,3) is forwards
• (3, 5) is forwards
• (5, 7) is backwards
• (7, 9) is backwards
• (9, n_verticies) is forwards

Edit2: We can see that for the case of a split point where both sides are moving away from the split point (i.e. left is backwards and the right is forwards) we will also need to deal with the order that we use the sides. Furthermore, as we reconstruct the cycle, we need to keep track of whether we are leaving for the first or second time.

For the purpose of including the flip point, we always do so when entering the first time or leaving the second time.

This info should be stored on the internal nodes of the graph. They will never need to be updated as we add nodes to the tree.

[MatthewMcGonagle]

Use a binary search tree of (directed) intervals. Splitting amounts to deleting intervals and added in splitted intervals with knowledge of order with respect to largest ancestor and smallest descendant.

[MatthewMcGonagle]

Going back to the original binary tree of split points, we store in internal nodes:

1. The point where splitting occurs.
2. Where the split goes.
3. Which direction to move after arriving at split destination (for the first time).

The leaf nodes like before represent the current orientation of intervals between split points. This can be used to decide on which information to give an internal node upon insertion.

For the example of splitting (3, 7) and then splitting on the pair (5, 9), we have:

                         3 -> 7 L
                        /         \
                     R                 7 -> 3 R
                                      /       \
                             5 -> 9 L        9 -> 5 R
                              /     \              /    \
                            R       L            L       R

Edit:

Another way to think about splits; it is a combination of two operations:

1. Split at pair of split points.
2. Gluing together pairs of segments from the split points. This falls into two possibilities:
   1. Glue together opposite sides.
   2. Glue together same sides.

Which type of gluing is done can be determined independent of which split point comes first in the cycle. All we need is the orientation of the cycle on the intervals the split points are located in (before doing the split).

Deciding how to glue is based only on two things:

1. Whether the split points are in the same or different intervals.
2. The orientation of the interval(s).

HOWEVER, the orientation of the split interval depends on the order in the cycle....