munkres 0.5.2

Kuhn-Munkres (aka Hungarian) algorithm for solving the Assignment Problem in O(n^3)
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
137
138
139
140

use crate::Position;
use fixedbitset::FixedBitSet;

#[derive(Debug)]
pub struct Coverage {
    n: usize,
    /// A bit is set, if the row is uncovered.
    uncovered_rows: FixedBitSet,
    /// A bit is set, if the column is uncovered.
    uncovered_columns: FixedBitSet,
}

impl Coverage {
    #[inline]
    pub fn n(&self) -> usize {
        self.n
    }

    pub fn new(n: usize) -> Coverage {
        assert!(n > 0);

        // We start with all bits set (all rows/columns) uncovered.
        let mut all_rows_uncovered = FixedBitSet::with_capacity(n);
        all_rows_uncovered.set_range(.., true);

        // We can simply clone the rows as we work on square matrices
        let all_columns_uncovered = all_rows_uncovered.clone();

        Coverage {
            n: n,
            uncovered_rows: all_rows_uncovered,
            uncovered_columns: all_columns_uncovered,
        }
    }

    /// Find the first uncovered cell. Iterates in column-major order.
    #[inline]
    pub fn find_uncovered_cell_column_row_order<F>(&self, mut f: F) -> Option<Position>
    where
        F: FnMut(Position) -> bool,
    {
        for column in self.uncovered_columns.ones() {
            for row in self.uncovered_rows.ones() {
                let pos = Position { row, column };
                if f(pos) {
                    return Some(pos);
                }
            }
        }

        return None;
    }

    /// iterates over all uncovered (row, column) pairs in row, column order
    #[inline]
    pub fn iter_uncovered_row_column_order<F>(&self, mut f: F)
    where
        F: FnMut(Position),
    {
        for row in self.uncovered_rows.ones() {
            for column in self.uncovered_columns.ones() {
                f(Position { row, column });
            }
        }
    }

    /// iterates over all uncovered (row, column) pairs in row, column order, and set covered if f returns true.
    #[inline]
    pub fn iter_uncovered_row_column_and_cover<F>(&mut self, mut f: F)
    where
        F: FnMut(Position) -> bool,
    {
        let n = self.n();

        for row in 0..n {
            if self.is_row_covered(row) {
                continue;
            }

            'column: for column in 0..n {
                if self.is_column_covered(column) {
                    continue;
                }

                let pos = Position { row, column };
                if f(pos) {
                    self.cover(pos);
                    // the complete row is covered! break the loop!
                    break 'column;
                }
            }
        }
    }

    #[inline]
    pub fn is_row_covered(&self, row: usize) -> bool {
        debug_assert!(row < self.n());
        !self.uncovered_rows.contains(row)
    }

    #[inline]
    pub fn is_column_covered(&self, column: usize) -> bool {
        debug_assert!(column < self.n());
        !self.uncovered_columns.contains(column)
    }

    #[inline]
    pub fn cover(&mut self, pos: Position) {
        self.cover_row(pos.row);
        self.cover_column(pos.column);
    }

    #[inline]
    pub fn cover_column(&mut self, column: usize) {
        debug_assert!(column < self.n());
        self.uncovered_columns.set(column, false);
    }

    #[inline]
    pub fn uncover_column(&mut self, column: usize) {
        debug_assert!(column < self.n());
        self.uncovered_columns.set(column, true);
    }

    #[inline]
    pub fn cover_row(&mut self, row: usize) {
        debug_assert!(row < self.n());
        self.uncovered_rows.set(row, false);
    }

    pub fn clear(&mut self) {
        self.uncovered_rows.set_range(.., true);
        self.uncovered_columns.set_range(.., true);
    }

    pub fn all_uncovered(&self) -> bool {
        self.uncovered_rows.count_ones(..) + self.uncovered_columns.count_ones(..)
            == (self.n + self.n)
    }
}