# 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 *m* ✕ *n* 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 *m* ✕ *n* 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( |

smawk_column_minima | Compute column minima in O( |

smawk_row_minima | Compute row minima in O( |