Struct LinkCutTree

pub struct LinkCutTree<P: Path> { /* private fields */ }

Implementations

impl<P: Path> LinkCutTree<P>

Link-cut-tree.

A 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.

Examples

use lctree::LinkCutTree;

// We form a link-cut tree for the following forest:
// (the numbers in parentheses are the weights of the nodes):
//            a(9)
//           /    \
//         b(1)    e(2)
//        /   \      \
//      c(8)  d(10)   f(4)
let mut lctree = LinkCutTree::default();
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.);

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

// Path aggregation:
// We find the node with max weight on the path between c to f,
// where a has the maximum weight of 9.0:
let heaviest_node = lctree.path(c, f);
assert_eq!(heaviest_node.idx, a);
assert_eq!(heaviest_node.weight, 9.0);

// We cut node e from its parent a:
lctree.cut(e, a);

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

// We check connectivity again:
assert!(!lctree.connected(c, f)); // not connected anymore

pub fn new() -> Self

Creates a new empty link-cut tree.

pub fn make_tree(&mut self, weight: f64) -> usize

Creates a new tree with a single node with the given weight and returns its id. If possible, reuses the space of a deleted node and returns its id.

Examples

use lctree::LinkCutTree;

let mut lctree = LinkCutTree::default();
let alice = lctree.make_tree(0.0);
let bob = lctree.make_tree(1.0);
let clay = lctree.make_tree(2.0);
assert_eq!([alice, bob, clay], [0, 1, 2]);

// Remove bob's tree from the forest
lctree.remove_tree(bob);

// Reuse the space of bob's tree (which was removed) to create a new tree:
let david = lctree.make_tree(4.0);
assert_eq!(david, bob);

pub fn extend_forest(&mut self, weights: &[f64]) -> Vec<usize>

Extends the forest with n new single-noded trees for the given weights.

Examples

use lctree::LinkCutTree;

let weights = vec![1.0, 2.0, 3.0];
let mut lctree = LinkCutTree::default();
let trees_ids = lctree.extend_forest(&weights);
assert_eq!(trees_ids, vec![0, 1, 2]);

pub fn remove_tree(&mut self, idx: usize)

Delete a tree with a single node with the given id.

Panics

Panics if the tree contains more than one node.

pub fn connected(&mut self, v: usize, w: usize) -> bool

Checks if two nodes are connected (i.e. in the same tree).

Examples

use lctree::LinkCutTree;

let mut lctree = LinkCutTree::default();
let alice = lctree.make_tree(0.0);
let bob = lctree.make_tree(1.0);
assert!(!lctree.connected(alice, bob)); // not connected yet

lctree.link(alice, bob);
assert!(lctree.connected(alice, bob)); // now connected

pub fn link(&mut self, v: usize, w: usize) -> bool

Merges two trees into a single tree.

Examples

use lctree::LinkCutTree;

let mut lctree = LinkCutTree::default();
let alice = lctree.make_tree(0.0);
let bob = lctree.make_tree(1.0);
let clay = lctree.make_tree(2.0);

lctree.link(alice, bob);
lctree.link(bob, clay);
assert!(lctree.connected(alice, clay));

pub fn linked(&mut self, v: usize, w: usize) -> bool

Checks if two nodes are connected by a link (i.e. v is the parent of w or vice versa).

Examples

use lctree::LinkCutTree;

let mut lctree = LinkCutTree::default();
let alice = lctree.make_tree(0.0);
let bob = lctree.make_tree(0.0);
let clay = lctree.make_tree(0.0);

lctree.link(alice, bob);
lctree.link(bob, clay);

assert!(lctree.linked(alice, bob)); // alice and bob are connected by a link
assert!(!lctree.linked(alice, clay)); // alice and clay are not connected by a link

pub fn cut(&mut self, v: usize, w: usize) -> bool

Cuts the link between two nodes (if it exists)

Examples

use lctree::LinkCutTree;

let mut lctree = LinkCutTree::default();
let alice = lctree.make_tree(0.0);
let bob = lctree.make_tree(1.0);
assert!(!lctree.connected(alice, bob)); // not connected yet

lctree.link(alice, bob);
assert!(lctree.connected(alice, bob)); // now connected

lctree.cut(alice, bob);
assert!(!lctree.connected(alice, bob)); // not connected again

pub fn path(&mut self, v: usize, w: usize) -> P

Performs path aggregation on a path between two nodes (if they are connected)

Examples

use lctree::{LinkCutTree, FindMax};

let mut lctree: LinkCutTree<FindMax> = LinkCutTree::new();
let alice = lctree.make_tree(0.0);
let bob = lctree.make_tree(10.0);
let clay = lctree.make_tree(1.0);
let dave = lctree.make_tree(2.0);

// Form a path from Alice to Dave:
lctree.link(alice, bob);
lctree.link(bob, clay);
lctree.link(clay, dave);

// Find the richest guy in the path from Alice to Dave:
let richest_guy = lctree.path(alice, dave);
assert_eq!(richest_guy.idx, bob);
assert_eq!(richest_guy.weight, 10.0);

pub fn findroot(&mut self, v: usize) -> usize

Finds the root of the tree that the query node is in.

Trait Implementations

impl Default for LinkCutTree<FindMax>

fn default() -> Self

Returns the “default value” for a type.