### 13 releases

0.3.3 | Feb 7, 2024 |
---|---|

0.3.2 | Nov 6, 2023 |

0.2.4 | Nov 4, 2023 |

0.2.1 | Oct 19, 2023 |

0.1.3 | Oct 13, 2023 |

#**324** in Data structures

**67** downloads per month

**Apache-2.0**

52KB

870 lines

# 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

amortized time:`O (logn)`

: creates an edge between nodes`link``(`v`,`w`)`

and`v`

.`w`

: removes the edge between nodes`cut``(`v`,`w`)`

and`v`

.`w`

: returns`connected``(`v`,`w`)`

if nodes`true`

and`v`

are in the same tree.`w`

: performs calculations on a path between nodes`path``(`v`,`w`)`

and`v`

.`w`

## Usage

This example shows how to link and cut edges:

`use` `lctree``::`LinkCutTree`;`
`fn` `main``(``)`` ``{`
`//` 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
`}`

Advanced usage include operations on paths:

## Common path aggregates

Various kinds of calculations can be performed on a path between two nodes, such as

, `findmax`

, or `findmin`

:`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):
`//` a(9)
`//` / \
`//` b(1) e(2)
`//` / \ \
`//` c(8) d(10) f(4)
`//` Use FindMax, FindMin or FindSum, depending on your usage:
`let` `mut` lctree`:` `LinkCutTree``<`FindSum`>` `=` `lctree``::``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.``)``;`
lctree`.``link``(`b`,` a`)``;`
lctree`.``link``(`c`,` b`)``;`
lctree`.``link``(`d`,` b`)``;`
lctree`.``link``(`e`,` a`)``;`
lctree`.``link``(`f`,` e`)``;`
`//` We find the sum of the weights on the path between c to f,
`let` result `=` lctree`.``path``(`c`,` f`)``;`
`assert_eq!``(`result`.`sum`,` `8.` `+` `1.` `+` `9.` `+` `2.` `+` `4.``)``;`
`}`

## Custom path aggregate function

A custom path aggregate function can be defined by using the

trait:`Path`

`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``(``)`` ``{`
`//` We form a link-cut tree from the following rooted tree
`//` (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``<`FindXor`>` `=` `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.``)``;`
lctree`.``link``(`b`,` a`)``;`
lctree`.``link``(`c`,` b`)``;`
lctree`.``link``(`d`,` b`)``;`
lctree`.``link``(`e`,` a`)``;`
lctree`.``link``(`f`,` e`)``;`
`//` We find the xor of the weights on the path between c to f,
`let` result `=` lctree`.``path``(`c`,` f`)``;`
`assert_eq!``(`result`.`xor`,` `8` `^` `1` `^` `9` `^` `2` `^` `4``)``;`
`}`

## Benchmark

The overall running time for performing a number of random operations (

, `link``(`v`,` w`)`

, `cut``(`v`,` w`)`

or `connected``(`v`,` w`)`

) on forests of varying sizes (check benchmark details here).`findmax``(`v`,` w`)`

# Nodes | # Operations | lctree | brute-force |
---|---|---|---|

100 | 10K | 4.8161 ms | 18.013 ms |

200 | 20K | 11.091 ms | 69.855 ms |

500 | 50K | 31.623 ms | 429.53 ms |

1000 | 100K | 68.649 ms | 1.8746 s |

5000 | 500K | 445.83 ms | 46.854 s |

10K | 1M | 964.64 ms | 183.24 s |

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