### 1 unstable release

new 0.1.0 | Aug 7, 2018 |
---|

#**22** in #optimization

**4** downloads per month

# 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.

## Usage

Add this to your `Cargo.toml`

:

```
[dependencies]
smawk = "0.1"
```

and this to your crate root:

```
extern crate smawk;
```

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

```
extern crate ndarray;
extern crate smawk;
use ndarray::arr2;
use smawk::smawk_column_minima;
let matrix = arr2(&[
[3, 2, 4, 5, 6],
[2, 1, 3, 3, 4],
[2, 1, 3, 3, 4],
[3, 2, 4, 3, 4],
[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.

## Documentation

## Release History

This is a changelog describing the most important changes per release.

### 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.

**MIT**license

#### Dependencies

- ndarray 0.10
- num-traits 0.1
- rand 0.3
- rand_derive 0.3

- dev version-sync 0.3