Source code

Revision control

Copy as Markdown

Other Tools

# SMAWK Algorithm in Rust
This crate contains an implementation of the [SMAWK algorithm][smawk] for
finding the smallest element per row in a totally monotone matrix.
The SMAWK algorithm allows you to lower the running time of some algorithms from
O(_n_²) to just O(_n_). In other words, you can turn a quadratic time complexity
(which is often too expensive) into linear time complexity.
Finding optimal line breaks in a paragraph of text is an example of an algorithm
which would normally take O(_n_²) time for _n_ words. With this crate, the
running time becomes linear. Please see the [textwrap crate][textwrap] for an
example of this.
## Usage
Add this to your `Cargo.toml`:
```toml
[dependencies]
smawk = "0.3"
```
You can now efficiently find row and column minima. Here is an example where we
find the column minima:
```rust
use smawk::Matrix;
let matrix = vec![
vec![3, 2, 4, 5, 6],
vec![2, 1, 3, 3, 4],
vec![2, 1, 3, 3, 4],
vec![3, 2, 4, 3, 4],
vec![4, 3, 2, 1, 1],
];
let minima = vec![1, 1, 4, 4, 4];
assert_eq!(smawk::column_minima(&matrix), minima);
```
The `minima` vector gives the index of the minimum value per column, so
`minima[0] == 1` since the minimum value in the first column is 2 (row 1). Note
that the smallest row index is returned.
### Cargo Features
This crate has an optional dependency on the
[`ndarray` crate](https://docs.rs/ndarray/), which provides an efficient matrix
implementation. Enable the `ndarray` Cargo feature to use it.
## Documentation
**[API documentation][api-docs]**
## Changelog
### Version 0.3.2 (2023-09-17)
This release adds more documentation and renames the top-level SMAWK functions.
The old names have been kept for now to ensure backwards compatibility, but they
will be removed in a future release.
- [#65](https://github.com/mgeisler/smawk/pull/65): Forbid the use of unsafe
code.
- [#69](https://github.com/mgeisler/smawk/pull/69): Migrate to the Rust 2021
edition.
- [#73](https://github.com/mgeisler/smawk/pull/73): Add examples to all
functions.
- [#74](https://github.com/mgeisler/smawk/pull/74): Add “mathematics” as a crate
category.
- [#75](https://github.com/mgeisler/smawk/pull/75): Remove `smawk_` prefix from
optimized functions.
### Version 0.3.1 (2021-01-30)
This release relaxes the bounds on the `smawk_row_minima`,
`smawk_column_minima`, and `online_column_minima` functions so that they work on
matrices containing floating point numbers.
- [#55](https://github.com/mgeisler/smawk/pull/55): Relax bounds to `PartialOrd`
instead of `Ord`.
- [#56](https://github.com/mgeisler/smawk/pull/56): Update dependencies to their
latest versions.
- [#59](https://github.com/mgeisler/smawk/pull/59): Give an example of what
SMAWK does in the README.
### Version 0.3.0 (2020-09-02)
This release slims down the crate significantly by making `ndarray` an optional
dependency.
- [#45](https://github.com/mgeisler/smawk/pull/45): Move non-SMAWK code and unit
tests out of lib and into separate modules.
- [#46](https://github.com/mgeisler/smawk/pull/46): Switch `smawk_row_minima`
and `smawk_column_minima` functions to a new `Matrix` trait.
- [#47](https://github.com/mgeisler/smawk/pull/47): Make the dependency on the
`ndarray` crate optional.
- [#48](https://github.com/mgeisler/smawk/pull/48): Let `is_monge` take a
`Matrix` argument instead of `ndarray::Array2`.
- [#50](https://github.com/mgeisler/smawk/pull/50): Remove mandatory
dependencies on `rand` and `num-traits` crates.
### Version 0.2.0 (2020-07-29)
This release updates the code to Rust 2018.
- [#18](https://github.com/mgeisler/smawk/pull/18): Make `online_column_minima`
generic in matrix type.
[Rust 2018][rust-2018] edition. We test against the latest stable and nightly
version of Rust.
- [#29](https://github.com/mgeisler/smawk/pull/29): Drop strict Rust 2018
compatibility by not testing with Rust 1.31.0.
- [#32](https://github.com/mgeisler/smawk/pull/32): Fix crash on overflow in
`is_monge`.
- [#33](https://github.com/mgeisler/smawk/pull/33): Update `rand` dependency to
latest version and get rid of `rand_derive`.
- [#34](https://github.com/mgeisler/smawk/pull/34): Bump `num-traits` and
`version-sync` dependencies to latest versions.
- [#35](https://github.com/mgeisler/smawk/pull/35): Drop unnecessary Windows
tests. The assumption is that the numeric computations we do are
cross-platform.
- [#36](https://github.com/mgeisler/smawk/pull/36): Update `ndarray` dependency
to the latest version.
- [#37](https://github.com/mgeisler/smawk/pull/37): Automate publishing new
releases to crates.io.
### Version 0.1.0 — August 7th, 2018
First release with the classical offline SMAWK algorithm as well as a newer
online version where the matrix entries can depend on previously computed column
minima.
## License
SMAWK can be distributed according to the [MIT license][mit]. Contributions will
be accepted under the same license.
[mit]: LICENSE