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();
    ...
}

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.