"connected" is sometimes wrong, because tree edges are not always raised

[btrekkie]

The connected method sometimes returns the wrong result. This is because the cut() method does not raise the level of all of the level-i tree edges before searching level i for a replacement edge. However, Holm, de Lichtenberg, and Thorup directs us to do so: "Hence, preserving our invariants, we can take all edges of T_v of level i and increase their level to i + 1, so as to make T_v a tree in F_{i + 1}." Without raising the tree edges, invariant (i) can be violated: "F is a maximum (with respect to l) spanning forest of G, that is, if (v, w) is a nontree edge, v and w are connected in F_{l(v, w)}."

Here is my attempt at a minimal example where the connected method returns the wrong result:

const createVertex = require('dynamic-forest')

// This test only fails about 40% of the time, due to the randomized nature of
// treaps, so repeat it until it fails
let failed = false;
while (!failed) {
    const vertex1 = createVertex(1);
    const vertex2 = createVertex(2);
    const vertex3 = createVertex(3);
    const vertex4 = createVertex(4);
    const vertex5 = createVertex(5);
    const vertex6 = createVertex(6);
    const vertex7 = createVertex(7);
    const vertex8 = createVertex(8);
    const vertex9 = createVertex(9);
    const vertex10 = createVertex(10);
    const vertex11 = createVertex(11);

    // Create a path: 1 - 2 - 3 - 4 - 5
    vertex1.link(vertex2);
    let edge23 = vertex2.link(vertex3);
    const edge34 = vertex3.link(vertex4);
    vertex4.link(vertex5);

    // Cut edges in such a manner as to raise the levels of (1, 2) and (4, 5)
    edge23.cut();
    edge23 = vertex2.link(vertex3);
    edge34.cut();
    edge23.cut();

    // Extend the path: 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11
    const edge56 = vertex5.link(vertex6);
    vertex6.link(vertex7);
    vertex7.link(vertex8);
    vertex8.link(vertex9);
    vertex9.link(vertex10);
    vertex10.link(vertex11);

    edge23 = vertex2.link(vertex3);
    vertex3.link(vertex4);
    vertex2.link(vertex4);
    vertex2.link(vertex6);

    // Try to trick dynamic-forest into raising the level of edge (2, 4) without
    // also raising the level of (2, 3). This only happens about 40% of the
    // time, since it depends on the structure of the treap.
    edge56.cut();

    // If our trick worked, then we will only search level 0 for a replacement
    // edge, but the replacement edge (2, 4) is in level 1
    edge23.cut();

    // At this point, the graph looks like this:
    //
    //     +-------------------+
    //     |                   |
    // 1 - 2     3 - 4 - 5     6 - 7 - 8 - 9 - 10 - 11
    //     |         |
    //     +---------+
    if (!vertex2.connected(vertex4)) {
        console.log('"connected" should have returned true');
        failed = true;
    }
}

Maybe this is also the cause of #1? If the levels get out of sync, it might be possible to find a replacement edge in a higher-level forest, and then to create a cycle when adding it to a lower-level forest. It seems like creating a cycle in the lower-level "forest" could result in a malformed treap.

Unfortunately, it takes some extra work to be able to raise all of the same-level tree edges without affecting asymptotic performance. There must be separate lists for tree edges and nontree edges, and separate flags in the Euler tour nodes for tree edges and nontree edges.