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() {
    // Build a forest consisting of 6 nodes with the following weights
    // (the numbers in parentheses are the weights of the nodes):
    let mut lctree: LinkCutTree<FindMax> = LinkCutTree::new();
    let a = lctree.make_tree(9.);
    let b = lctree.make_tree(1.);
    let c = lctree.make_tree(8.);
    let d = lctree.make_tree(10.);
    let e = lctree.make_tree(2.);
    let f = lctree.make_tree(4.);
    
    //  Link the nodes to form the following tree
    //            a(9)
    //           /    \
    //         b(1)    e(2)
    //        /   \      \
    //      c(8)  d(10)   f(4)
    lctree.link(b, a);
    lctree.link(c, b);
    lctree.link(d, b);
    lctree.link(e, a);
    lctree.link(f, e);

    // Checking connectivity:
    assert!(lctree.connected(c, f)); // connected

    // Find the node with the maximum weight on the path from c to f:
    let heaviest_node = lctree.path(c, f);
    assert_eq!(heaviest_node.idx, a);
    assert_eq!(heaviest_node.weight, 9.0);

    // Cut the edge between e and a:
    lctree.cut(e, a);

    // The forest should now look like this:
    //            a(9)
    //           /    
    //         b(1)      e(2)
    //        /   \        \
    //      c(8)  d(10)    f(4)

    // Now c and f should not be connected anymore:
    assert!(!lctree.connected(c, f)); // not connected anymore
}

Python

This library provides pre-built Rust bindings for Python using PyO3 and maturin:

pip install lctree-rs

The following example shows the equivalent usage in Python:

from lctree_rs import FindMaxTree # FindSumTree, FindXorTree

tree = FindMaxTree()
a = tree.make_tree(9.0)
b = tree.make_tree(1.0)
c = tree.make_tree(8.0)
d = tree.make_tree(10.0)
e = tree.make_tree(2.0)
f = tree.make_tree(4.0)

# Link the nodes to form the following tree:
#           a(9)
#           /  \
#         b(1)  e(2)
#        /   \    \
#      c(8)  d(10)  f(4)
tree.link(b, a)
tree.link(c, b)
tree.link(d, b)
tree.link(e, a)
tree.link(f, e)

# Check connectivity:
assert tree.connected(c, f)

# Find the node with the maximum weight on the path from c to f:
(max_idx, max_weight) = tree.find_max(c, f)
assert max_idx == a
assert max_weight == 9.0

# Cut the edge between e and a:
tree.cut(e, a)

# Now c and f should not be connected anymore:
assert not tree.connected(c, f)

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.