### 4 releases (2 breaking)

0.3.1 | Jan 30, 2021 |
---|---|

0.3.0 | Sep 2, 2020 |

0.2.0 | Jul 29, 2020 |

0.1.0 | Aug 7, 2018 |

#**702** in Algorithms

**305,947** downloads per month

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

**MIT**license

35KB

597 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``::`smawk_column_minima`;`
`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.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