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: 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::smawkcolumnminima;

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]; asserteq!(smawkcolumn_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, which provides an efficient matrix implementation. Enable the ndarray Cargo feature to use it.

Documentation

API documentation

Changelog

Version 0.3.0 (2020-09-02)

This release slims down the crate significantly by making ndarray an optional dependency.

#45: Move non-SMAWK code and unit tests out of lib and into separate modules.
#46: Switch smawk_row_minima and smawk_column_minima functions to a new Matrix trait.
#47: Make the dependency on the ndarray crate optional.
#48: Let is_monge take a Matrix argument instead of ndarray::Array2.
#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: Make online_column_minima generic in matrix type.
#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 rand dependency to latest version and get rid of rand_derive.
#34: Bump num-traits and version-sync dependencies to latest versions.
#35: Drop unnecessary Windows tests. The assumption is that the numeric computations we do are cross-platform.
#36: Update ndarray dependency to the latest version.
#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.