This repo implements the algorithm described in the paper 'Enumerating Prefix-Closed Regular Languages with Constant Delay' (see Resources) and therefore also implements all standard data-structures needed for the algorithm. I've also tried to get as close to the theoretical construction and complexity as possible.
- Range Minimum Query (O(n), O(1))
- Sparse Table
- Lowest Common Ancestor (O(n), O(1))
- Level Ancestor Query (O(n), O(1))
- Topological Sorting
- Tarjan's Algorithm for strongly connected components
- Construction of Cartesian trees on Arrays and edge-weighed Trees
- Decremental Connectivity (O(n), O(1))
- Even and Shiloach’s algorithm for decremental connectivity
To enumerate the paths on a test-graph, run
cargo run
To enumerate the paths of a different graph, build a Enumerate object and start_enumeration() will start the algorithm.
To get the html just run
cargo doc
Code to benchmark this project can be executed by running
cargo bench