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

API 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