smawk

Functions for finding row-minima in a totally monotone matrix

5 unstable releases

 0.3.2 Sep 17, 2023 Jan 30, 2021 Sep 2, 2020 Jul 29, 2020 Aug 7, 2018

#95 in Algorithms

Used in 667 crates (via textwrap)

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 `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.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 `smawk_` prefix from 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.

• #55: Relax bounds to `PartialOrd` instead of `Ord`.
• #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 `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.