smawk 0.3.3

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

//! Test functionality for generating random Monge matrices.

// The code is put here so we can reuse it in different integration
// tests, without Cargo finding it when `cargo test` is run. See the
// section on "Submodules in Integration Tests" in
// https://doc.rust-lang.org/book/ch11-03-test-organization.html

use ndarray::{s, Array2};
use num_traits::PrimInt;
use rand::distr::{Distribution, StandardUniform};
use rand::{Rng, RngExt};

/// A Monge matrix can be decomposed into one of these primitive
/// building blocks.
#[derive(Copy, Clone)]
pub enum MongePrim {
    ConstantRows,
    ConstantCols,
    UpperRightOnes,
    LowerLeftOnes,
}

impl MongePrim {
    /// Generate a Monge matrix from a primitive.
    pub fn to_matrix<T: PrimInt, R: Rng>(self, m: usize, n: usize, rng: &mut R) -> Array2<T>
    where
        StandardUniform: Distribution<T>,
    {
        let mut matrix = Array2::from_elem((m, n), T::zero());
        // Avoid panic in UpperRightOnes and LowerLeftOnes below.
        if m == 0 || n == 0 {
            return matrix;
        }

        match self {
            MongePrim::ConstantRows => {
                for mut row in matrix.rows_mut() {
                    if rng.random::<bool>() {
                        row.fill(T::one())
                    }
                }
            }
            MongePrim::ConstantCols => {
                for mut col in matrix.columns_mut() {
                    if rng.random::<bool>() {
                        col.fill(T::one())
                    }
                }
            }
            MongePrim::UpperRightOnes => {
                let i = rng.random_range(0..m + 1) as isize;
                let j = rng.random_range(0..n + 1) as isize;
                matrix.slice_mut(s![..i, -j..]).fill(T::one());
            }
            MongePrim::LowerLeftOnes => {
                let i = rng.random_range(0..m + 1) as isize;
                let j = rng.random_range(0..n + 1) as isize;
                matrix.slice_mut(s![-i.., ..j]).fill(T::one());
            }
        }

        matrix
    }
}

/// Generate a random Monge matrix.
pub fn random_monge_matrix<R: Rng, T: PrimInt>(m: usize, n: usize, rng: &mut R) -> Array2<T>
where
    StandardUniform: Distribution<T>,
{
    let monge_primitives = [
        MongePrim::ConstantRows,
        MongePrim::ConstantCols,
        MongePrim::LowerLeftOnes,
        MongePrim::UpperRightOnes,
    ];
    let mut matrix = Array2::from_elem((m, n), T::zero());
    for _ in 0..(m + n) {
        let monge = monge_primitives[rng.random_range(0..monge_primitives.len())];
        matrix = matrix + monge.to_matrix(m, n, rng);
    }
    matrix
}