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
:
[]
= "0.2"
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 arr2;
use smawk_column_minima;
let matrix = arr2;
let minima = vec!;
assert_eq!;
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.2.0 (2020-07-29)
-
#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 ofrand_derive
. -
#34: Bump
num-traits
andversion-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.