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
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.
code.
edition.
functions.
category.
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.
instead of `Ord`.
latest versions.
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.
tests out of lib and into separate modules.
and `smawk_column_minima` functions to a new `Matrix` trait.
`ndarray` crate optional.
`Matrix` argument instead of `ndarray::Array2`.
dependencies on `rand` and `num-traits` crates.
### Version 0.2.0 (2020-07-29)
This release updates the code to Rust 2018.
generic in matrix type.
[Rust 2018][rust-2018] edition. We test against the latest stable and nightly
version of Rust.
compatibility by not testing with Rust 1.31.0.
`is_monge`.
latest version and get rid of `rand_derive`.
`version-sync` dependencies to latest versions.
tests. The assumption is that the numeric computations we do are
cross-platform.
to the latest version.
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