lctree

Rust implementation of Link-cut tree: self-balancing data structure to maintain a dynamic forest of (un)rooted trees under the following operations that take O(logn) amortized time:

• link(v, w): creates an edge between nodes v and w.
• cut(v, w): removes the edge between nodes v and w.
• connected(v, w): returns true if nodes v and w are in the same tree.
• path(v, w): performs calculations on a path between nodes v and w.

Usage

This example shows how to link and cut edges:

use lctree::LinkCutTree;

fn main() {
    // We form a link-cut tree from the following rooted tree:
    //     0
    //    / \
    //   1   4
    //  / \   \
    // 2   3   5
    //        /
    //       6
    let mut lctree = lctree::LinkCutTree::default();
    for i in 0..7 {
        lctree.make_tree(i as f64);
    }
    lctree.link(1, 0);
    lctree.link(2, 1);
    lctree.link(3, 1);
    lctree.link(4, 0);
    lctree.link(5, 4);
    lctree.link(6, 5);

    // Checking connectivity:
    assert!(lctree.connected(2, 6)); // connected

    // We cut node 4 from its parent 0:
    lctree.cut(4, 0);

    // The forest should now look like this:
    //     0
    //    /   
    //   1     4
    //  / \     \
    // 2   3     5
    //          /
    //         6

    // We check connectivity again:
    assert!(!lctree.connected(2, 6)); // not connected anymore
}

Advanced usage include operations on paths:

Various kinds of calculations can be performed on a path between two nodes, provided as findmax, findmin, or findsum:

use lctree::{LinkCutTree, FindMax, FindMin, FindSum};

fn main() {
    // We form a link-cut tree from the following rooted tree
    // (the numbers in parentheses are the weights of the nodes):
    //           0(9)
    //           /  \
    //         1(1)  4(2)
    //        /   \    \
    //      2(8)  3(0)  5(4)
    //                  /
    //                6(3)

    // Replace FindMax with FindMin or FindSum, depending on your usage:
    let mut lctree: LinkCutTree<FindMax> = lctree::LinkCutTree::new();
    let weights = [9.0, 1.0, 8.0, 0.0, 2.0, 4.0, 3.0];
    for i in 0..weights.len() {
        lctree.make_tree(weights[i]);
    }
    lctree.link(1, 0);
    lctree.link(2, 1);
    lctree.link(3, 1);
    lctree.link(4, 0);
    lctree.link(5, 4);
    lctree.link(6, 5);

    // We find the node with max weight on the path between 2 to 6,
    // where 0 has the maximum weight of 9.0:
    assert_eq!(lctree.path(2, 6).max_weight, 9.0);
    assert_eq!(lctree.path(2, 6).max_weight_idx, 0);
}

A custom path aggregate function can be defined by using the Path trait:

use lctree::{LinkCutTree, Path};

#[derive(Copy, Clone)]
pub struct FindXor {
    pub xor: u64,
}

impl Path for FindXor {
    fn default(weight: f64, _: usize) -> Self {
        FindXor {
            xor: weight as u64,
        }
    }

    fn aggregate(&mut self, other: Self) {
        self.xor ^= other.xor;
    }
}

fn main() {
    let mut lctree: LinkCutTree<FindXor> = LinkCutTree::new();
    ...
}

Benchmark

This benchmark report contains overall running time analysis of Link-Cut trees in comparison to its brute-force counterpart (iMac 24", M1, 2021, 16Gb). Each test performs a number of random operations (link(v, w), cut(v, w), connected(v, w) or findmax(v, w)) on forests of varying sizes (check benchmark details here).

Credits

This crate applies the core concepts and ideas presented in the following sources:

• "A data structure for dynamic trees" by D. Sleator and R. E. TarJan (published in STOC '81).
• Link-cut tree source code by the author D. Sleator.
• MIT's lecture on dynamic graphs: lecture, notes, and source code.
• Helpful blog posts on the concepts of rooted trees, rerooting and splay operations.

License

This project is licensed under the Apache License, Version 2.0 - See the LICENSE.md file for details.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be licensed as above, without any additional terms or conditions.