# Crate smawk[−][src]

This crate implements various functions that help speed up dynamic programming, most importantly the SMAWK algorithm for finding row or column minima in a totally monotone matrix with m rows and n columns in time O(m + n). This is much better than the brute force solution which would take O(mn). When m and n are of the same order, this turns a quadratic function into a linear function.

# Examples

Computing the column minima of an mn Monge matrix can be done efficiently with `smawk_column_minima`:

```use smawk::{Matrix, smawk_column_minima};

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.

# Definitions

Some of the functions in this crate only work on matrices that are totally monotone, which we will define below.

## Monotone Matrices

We start with a helper definition. Given an mn matrix `M`, we say that `M` is monotone when the minimum value of row `i` is found to the left of the minimum value in row `i'` where `i < i'`.

More formally, if we let `rm(i)` denote the column index of the left-most minimum value in row `i`, then we have

``````rm(0) ≤ rm(1) ≤ ... ≤ rm(m - 1)
``````

This means that as you go down the rows from top to bottom, the row-minima proceed from left to right.

The algorithms in this crate deal with finding such row- and column-minima.

## Totally Monotone Matrices

We say that a matrix `M` is totally monotone when every sub-matrix is monotone. A sub-matrix is formed by the intersection of any two rows `i < i'` and any two columns `j < j'`.

This is often expressed as via this equivalent condition:

``````M[i, j] > M[i, j']  =>  M[i', j] > M[i', j']
``````

for all `i < i'` and `j < j'`.

## Monge Property for Matrices

A matrix `M` is said to fulfill the Monge property if

``````M[i, j] + M[i', j'] ≤ M[i, j'] + M[i', j]
``````

for all `i < i'` and `j < j'`. This says that given any rectangle in the matrix, the sum of the top-left and bottom-right corners is less than or equal to the sum of the bottom-left and upper-right corners.

All Monge matrices are totally monotone, so it is enough to establish that the Monge property holds in order to use a matrix with the functions in this crate. If your program is dealing with unknown inputs, it can use `monge::is_monge` to verify that a matrix is a Monge matrix.

## Modules

 monge Functions for generating and checking Monge arrays.

## Traits

 Matrix Minimal matrix trait for two-dimensional arrays.

## Functions

 online_column_minima Compute upper-right column minima in O(m + n) time. smawk_column_minima Compute column minima in O(m + n) time. smawk_row_minima Compute row minima in O(m + n) time.