[go: up one dir, main page]

smawk 0.3.1

Functions for finding row-minima in a totally monotone matrix.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

# SMAWK Algorithm in Rust

[![](https://github.com/mgeisler/smawk/workflows/build/badge.svg)][build-status]
[![](https://codecov.io/gh/mgeisler/smawk/branch/master/graph/badge.svg)][codecov]
[![](https://img.shields.io/crates/v/smawk.svg)][crates-io]
[![](https://docs.rs/smawk/badge.svg)][api-docs]

This crate contains an implementation of the [SMAWK algorithm][smawk]
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][textwrap] for an example of this.

## Usage

Add this to your `Cargo.toml`:
```toml
[dependencies]
smawk = "0.3"
```

You can now efficiently find row and column minima. Here is an example
where we find the column minima:

```rust
use smawk::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.

### Cargo Features

This crate has an optional dependency on the [`ndarray`
crate](https://docs.rs/ndarray/), which provides an efficient matrix
implementation. Enable the `ndarray` Cargo feature to use it.

## Documentation

**[API documentation][api-docs]**

## Changelog

### 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](https://github.com/mgeisler/smawk/pull/55): Relax bounds to
  `PartialOrd` instead of `Ord`.
* [#56](https://github.com/mgeisler/smawk/pull/56): Update
  dependencies to their latest versions.
* [#59](https://github.com/mgeisler/smawk/pull/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](https://github.com/mgeisler/smawk/pull/45): Move non-SMAWK
  code and unit tests out of lib and into separate modules.
* [#46](https://github.com/mgeisler/smawk/pull/46): Switch
  `smawk_row_minima` and `smawk_column_minima` functions to a new
  `Matrix` trait.
* [#47](https://github.com/mgeisler/smawk/pull/47): Make the
  dependency on the `ndarray` crate optional.
* [#48](https://github.com/mgeisler/smawk/pull/48): Let `is_monge` take
  a `Matrix` argument instead of `ndarray::Array2`.
* [#50](https://github.com/mgeisler/smawk/pull/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](https://github.com/mgeisler/smawk/pull/18): Make
  `online_column_minima` generic in matrix type.
* [#23](https://github.com/mgeisler/smawk/pull/23): Switch to the
  [Rust 2018][rust-2018] edition. We test against the latest stable
  and nightly version of Rust.
* [#29](https://github.com/mgeisler/smawk/pull/29): Drop strict Rust
  2018 compatibility by not testing with Rust 1.31.0.
* [#32](https://github.com/mgeisler/smawk/pull/32): Fix crash on
  overflow in `is_monge`.
* [#33](https://github.com/mgeisler/smawk/pull/33): Update `rand`
  dependency to latest version and get rid of `rand_derive`.
* [#34](https://github.com/mgeisler/smawk/pull/34): Bump `num-traits`
  and `version-sync` dependencies to latest versions.
* [#35](https://github.com/mgeisler/smawk/pull/35): Drop unnecessary
  Windows tests. The assumption is that the numeric computations we do
  are cross-platform.
* [#36](https://github.com/mgeisler/smawk/pull/36): Update `ndarray`
  dependency to the latest version.
* [#37](https://github.com/mgeisler/smawk/pull/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][mit].
Contributions will be accepted under the same license.

[build-status]: https://github.com/mgeisler/smawk/actions?query=branch%3Amaster+workflow%3Abuild
[crates-io]: https://crates.io/crates/smawk
[codecov]: https://codecov.io/gh/mgeisler/smawk
[textwrap]: https://crates.io/crates/textwrap
[smawk]: https://en.wikipedia.org/wiki/SMAWK_algorithm
[api-docs]: https://docs.rs/smawk/
[rust-2018]: https://doc.rust-lang.org/edition-guide/rust-2018/
[mit]: LICENSE