### 5 unstable releases

0.3.2 | Sep 17, 2023 |
---|---|

0.3.1 | Jan 30, 2021 |

0.3.0 | Sep 2, 2020 |

0.2.0 | Jul 29, 2020 |

0.1.0 | Aug 7, 2018 |

#**95** in Algorithms

**1,192,686** downloads per month

Used in **667** crates
(via textwrap)

**MIT**license

39KB

609 lines

# SMAWK Algorithm in Rust

This crate contains an implementation of the SMAWK algorithm 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 for an
example of this.

## Usage

Add this to your

:`Cargo.toml`

`[``dependencies``]`
`smawk ``=` `"`0.3`"`

You can now efficiently find row and column minima. Here is an example where we find the column minima:

`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

vector gives the index of the minimum value per column, so
`minima`

since the minimum value in the first column is 2 (row 1). Note
that the smallest row index is returned.`minima [0] == 1`

### Cargo Features

This crate has an optional dependency on the

crate, which provides an efficient matrix
implementation. Enable the `ndarray`

Cargo feature to use it.`ndarray`

## Documentation

## 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: Forbid the use of unsafe code.
- #69: Migrate to the Rust 2021 edition.
- #73: Add examples to all functions.
- #74: Add “mathematics” as a crate category.
- #75: Remove

prefix from optimized functions.`smawk_`

### Version 0.3.1 (2021-01-30)

This release relaxes the bounds on the

,
`smawk_row_minima`

, and `smawk_column_minima`

functions so that they work on
matrices containing floating point numbers.`online_column_minima`

- #55: Relax bounds to

instead of`PartialOrd`

.`Ord` - #56: Update dependencies to their latest versions.
- #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

an optional
dependency.`ndarray`

- #45: Move non-SMAWK code and unit tests out of lib and into separate modules.
- #46: Switch

and`smawk_row_minima`

functions to a new`smawk_column_minima`

trait.`Matrix` - #47: Make the dependency on the

crate optional.`ndarray` - #48: Let

take a`is_monge`

argument instead of`Matrix`

.`ndarray`Array2`::` - #50: Remove mandatory
dependencies on

and`rand`

crates.`num-traits`

### Version 0.2.0 (2020-07-29)

This release updates the code to Rust 2018.

- #18: Make

generic in matrix type.`online_column_minima` - #23: Switch to the Rust 2018 edition. We test against the latest stable and nightly version of Rust.
- #29: Drop strict Rust 2018 compatibility by not testing with Rust 1.31.0.
- #32: Fix crash on overflow in

.`is_monge` - #33: Update

dependency to latest version and get rid of`rand`

.`rand_derive` - #34: Bump

and`num-traits`

dependencies to latest versions.`version-sync` - #35: Drop unnecessary Windows tests. The assumption is that the numeric computations we do are cross-platform.
- #36: Update

dependency to the latest version.`ndarray` - #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. Contributions will be accepted under the same license.

#### Dependencies

~0–300KB