LAPJV

https://docs.rs/lapjv/0.3.0
Admin
LAPJV is a Rust library implementing the Shortest Augmenting Path algorithm for solving Linear...
Tokens:11,866
Snippets:108
Trust Score:9.1
Update:5 months ago
Show doc for...
Tokens:
Raw
### Basic LAPJV Usage Example

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Demonstrates the basic usage of the `lapjv` function with a predefined cost matrix. Asserts the correctness of the resulting assignment and its cost.

```rust
let m = Matrix::from_shape_vec((3, 3), vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0])
            .unwrap();
let result = lapjv(&m).unwrap();
assert_eq!(result.0, vec![2, 0, 1]);
assert_eq!(result.1, vec![1, 2, 0]);
```

--------------------------------

### LAPJV Solve with Infinite Costs Example

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Tests the `lapjv` solver with a 10x10 cost matrix containing `std::f64::INFINITY` values. Asserts the calculated cost and the resulting assignment.

```rust
let c = vec![
            std::f64::INFINITY,
            643.0,
            717.0,
            2.0,
            946.0,
            534.0,
            242.0,
            235.0,
            376.0,
            839.0,
            std::f64::INFINITY,
            141.0,
            799.0,
            180.0,
            386.0,
            745.0,
            592.0,
            822.0,
            421.0,
            42.0,
            std::f64::INFINITY,
            369.0,
            831.0,
            67.0,
            258.0,
            549.0,
            615.0,
            529.0,
            458.0,
            524.0,
            std::f64::INFINITY,
            649.0,
            287.0,
            910.0,
            12.0,
            820.0,
            31.0,
            92.0,
            217.0,
            555.0,
            std::f64::INFINITY,
            81.0,
            568.0,
            241.0,
            292.0,
            653.0,
            417.0,
            652.0,
            630.0,
            788.0,
            std::f64::INFINITY,
            822.0,
            788.0,
            166.0,
            122.0,
            690.0,
            304.0,
            568.0,
            449.0,
            214.0,
            std::f64::INFINITY,
            469.0,
            584.0,
            633.0,
            213.0,
            414.0,
            498.0,
            500.0,
            317.0,
            391.0,
            std::f64::INFINITY,
            581.0,
            183.0,
            420.0,
            16.0,
            748.0,
            35.0,
            516.0,
            639.0,
            356.0,
            std::f64::INFINITY,
            921.0,
            67.0,
            33.0,
            592.0,
            775.0,
            780.0,
            335.0,
            464.0,
            788.0,
            123.0,
            455.0,
            950.0,
            25.0,
            22.0,
            576.0,
            969.0,
            122.0,
            86.0,
            74.0,
        ];
let m = Matrix::from_shape_vec((10, 10), c).unwrap();
let result = lapjv(&m).unwrap();
let cost = cost(&m, &result.0);
assert_eq!(cost, 1403.0);
assert_eq!(result.0, vec![7, 9, 3, 8, 1, 4, 5, 6, 2, 0]);
```

--------------------------------

### LAPJV Solve Random 10 Example

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Tests the `lapjv` solver with a predefined 10x10 cost matrix generated to have specific properties. Asserts the calculated cost and the resulting assignment.

```rust
let (m, result) = solve_random10();
let cost = cost(&m, &result.0);
assert_eq!(cost, 1071.0);
assert_eq!(result.0, vec![7, 9, 3, 4, 1, 0, 5, 6, 2, 8]);
```

--------------------------------

### LAPJV Cancellation Example

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Shows how to use the cancellation feature of the `LapJV` solver. This is useful for interrupting long-running computations. It asserts that the result is an error of kind `Cancelled`.

```rust
let m = Matrix::from_shape_vec((3, 3), vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0])
            .unwrap();
let lapjv = LapJV::new(&m);
let cancellation = lapjv.cancellation();
cancellation.cancel();
let result = lapjv.solve();
assert!(matches!(
            result,
            Err(LapJVError {
                kind: ErrorKind::Cancelled
            })
        ));
```

--------------------------------

### LapJV struct initialization and cancellation

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Initializes the `LapJV` struct with the cost matrix and sets up internal state. It also provides a way to get a cancellation token for interrupting the computation.

```rust
impl<'a, T> LapJV<'a, T>
where
    T: LapJVCost,
{
    pub fn new(costs: &'a Matrix<T>) -> Self {
        let dim = costs.dim().0; // square matrix dimensions
        let free_rows = Vec::with_capacity(dim); // list of unassigned rows.
        let v = Vec::with_capacity(dim);
        let in_row = vec![0; dim];
        let in_col = Vec::with_capacity(dim);
        let cancellation = Cancellation(Default::default());
        Self {
            costs,
            dim,
            free_rows,
            v,
            in_col,
            in_row,
            cancellation,
        }
    }

    /// Returns a `Cancellation` token which can be cancelled from another thread.
    pub fn cancellation(&self) -> Cancellation {
        self.cancellation.clone()
    }

    fn check_cancelled(&self) -> Result<(), LapJVError> {
        if self.cancellation.is_cancelled() {
            return Err(LapJVError {
                kind: ErrorKind::Cancelled,
            });
        }
        Ok(())
    }

    pub fn solve(mut self) -> Result<(Vec<usize>, Vec<usize>), LapJVError> {
        if self.costs.dim().0 != self.costs.dim().1 {
            return Err(LapJVError {
                kind: ErrorKind::Msg("Input error: matrix is not square"),
            });
        }
        self.ccrrt_dense();

        let mut i = 0;
        while !self.free_rows.is_empty() && i < 2 {
            self.check_cancelled()?;
            self.carr_dense();
            i += 1;
        }

        if !self.free_rows.is_empty() {
            self.ca_dense()?;
        }

        Ok((self.in_row, self.in_col))
    }

    // Column-reduction and reduction transfer for a dense cost matrix
    fn ccrrt_dense(&mut self) {
        let mut unique = vec![true; self.dim];
        let mut in_row_not_set = vec![true; self.dim];

        for row in self.costs.lanes(ndarray::Axis(0)) {
            let (min_index, min_value) = row.indexed_iter().skip(1).fold(
                (0, row[0]),
                |(old_idx, old_min), (new_idx, &new_min)| {
                    if new_min < old_min {
                        (new_idx, new_min)
                    } else {
                        (old_idx, old_min)
                    }
                },
            );
            self.in_col.push(min_index);
            self.v.push(min_value);
        }
    }
}
```

--------------------------------

### LAPJV Library Setup and Type Definitions

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Defines necessary traits, types, and structures for the LAPJV algorithm, including cost matrix type, error handling, and the main `LapJV` struct.

```rust
use num_traits::Float;
use log::trace;

use std::fmt;
use std::ops;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};

pub type Matrix<T> = ndarray::Array2<T>;

pub trait LapJVCost: Float + ops::AddAssign + ops::SubAssign + std::fmt::Debug {}
impl<T> LapJVCost for T where T: Float + ops::AddAssign + ops::SubAssign + std::fmt::Debug {}

#[derive(Debug, Copy, Clone)]
pub enum ErrorKind {
    Msg(&'static str),
    Cancelled,
}

#[derive(Debug)]
pub struct LapJVError {
    kind: ErrorKind,
}

impl LapJVError {
    pub fn kind(&self) -> ErrorKind {
        self.kind
    }
}

impl std::fmt::Display for LapJVError {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        match self.kind {
            ErrorKind::Msg(string) => write!(f, "{}", string),
            ErrorKind::Cancelled => write!(f, "cancelled"),
        }
    }
}

impl std::error::Error for LapJVError {}

pub struct LapJV<'a, T: 'a> {
    costs: &'a Matrix<T>,
    dim: usize,
    free_rows: Vec<usize>,
    v: Vec<T>,
    in_col: Vec<usize>,
    in_row: Vec<usize>,
    cancellation: Cancellation,
}

#[derive(Clone)]
pub struct Cancellation(Arc<AtomicBool>);

impl Cancellation {
    pub fn cancel(&self) {
        self.0.store(true, Ordering::SeqCst)
    }

    pub fn is_cancelled(&self) -> bool {
        self.0.load(Ordering::SeqCst)
    }
}
```

--------------------------------

### LAPJV Find UMINs Plain Example

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Demonstrates the `find_umins_plain` function, which is a helper for finding minimum values in a row of the cost matrix. It asserts the returned tuple of minimum values.

```rust
let m = Matrix::from_shape_vec((3, 3), vec![25.0, 0.0, 15.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0])
            .unwrap();
let result = find_umins_plain(m.row(0), &vec![0.0, 0.0, 0.0]);
println!("Result: {:?}", result);
assert_eq!(result, (0.0, 15.0, 1, Some(2)));
```

--------------------------------

### Get Description - LapJVError (Deprecated)

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Provides a string description of the error. This method is deprecated and users should prefer using the Display implementation or `to_string()`.

```rust
fn description(&self) -> &str
```

--------------------------------

### Get Cost in LAPJV

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Retrieves the cost between two points (row i, column j) from the cost matrix.

```rust
fn cost(&self, i: usize, j: usize) -> T {
        self.costs[(i, j)]
    }
```

--------------------------------

### Any Trait Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Provides the `type_id` method for getting the `TypeId` of `self`. This is a blanket implementation for any type `T` that is `'static`.

```rust
fn type_id(&self) -> TypeId
```

--------------------------------

### Find Closest Free Column (Dense Matrix)

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Implements a modified Dijkstra shortest path algorithm to find the closest free column for a given starting row in a dense cost matrix. Returns the index of the closest free column.

```rust
    /// Single iteration of modified Dijkstra shortest path algorithm as explained in the JV paper
    /// return The closest free column index
    fn find_path_dense(&mut self, start_i: usize, pred: &mut [usize]) -> usize {
```

--------------------------------

### Get Source Error - LapJVError

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Returns the underlying source error if the LapJVError was caused by another error. This is useful for error chaining and debugging.

```rust
fn source(&self) -> Option<&(dyn Error + 'static)>
```

--------------------------------

### Get Cause Error - LapJVError (Deprecated)

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Returns the underlying cause of the error. This method is deprecated and replaced by `Error::source` which supports downcasting.

```rust
fn cause(&self) -> Option<&dyn Error>
```

--------------------------------

### Get Reduced Cost in LAPJV

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Calculates the reduced cost between two points (row i, column j) by subtracting the column's dual variable 'v[j]' from the original cost.

```rust
fn reduced_cost(&self, i: usize, j: usize) -> T {
        self.cost(i, j) - self.v[j]
    }
```

--------------------------------

### Get Error Kind - LapJVError

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Retrieves the specific kind of error from a LapJVError instance. This method is part of the public API for inspecting errors.

```rust
pub fn kind(&self) -> ErrorKind
```

--------------------------------

### LapJV::new

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Creates a new `LapJV` solver instance with the given cost matrix.

```APIDOC
## LapJV::new<'a, T>

### Description
Initializes a `LapJV` struct, which is used to solve the Linear Assignment Problem. It takes a reference to the cost matrix and sets up internal structures for the algorithm.

### Method Signature
```rust
pub fn new(costs: &'a Matrix<T>) -> Self
where
    T: LapJVCost,
```

### Parameters
- `costs` (*&'a Matrix<T>*): A reference to the cost matrix for the assignment problem. The matrix must be square.

### Returns
- `Self`: A new `LapJV` instance ready to solve the problem.
```

--------------------------------

### LapJV::new - Constructor

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Creates a new `LapJV` instance with the given cost matrix. The cost type `T` must implement `LapJVCost`.

```rust
pub fn new(costs: &'a Matrix<T>) -> Self
```

--------------------------------

### Create Matrix and Solve LAPJV

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Creates a square matrix from a vector of values and then solves the Linear Assignment Problem using the LAPJV algorithm. This is typically used for testing or demonstrating the core functionality.

```rust
fn test_solve_random10() -> (Matrix<f64>, Vec<(usize, usize)>) {
        let c = vec![258.0, 549.0, 615.0, 529.0, 458.0, 524.0, 231.0, 649.0, 287.0, 910.0, 12.0, 820.0,
            31.0, 92.0, 217.0, 555.0, 912.0, 81.0, 568.0, 241.0, 292.0, 653.0, 417.0, 652.0, 630.0,
            788.0, 32.0, 822.0, 788.0, 166.0, 122.0, 690.0, 304.0, 568.0, 449.0, 214.0, 441.0,
            469.0, 584.0, 633.0, 213.0, 414.0, 498.0, 500.0, 317.0, 391.0, 798.0, 581.0, 183.0,
            420.0, 16.0, 748.0, 35.0, 516.0, 639.0, 356.0, 351.0, 921.0, 67.0, 33.0, 592.0, 775.0,
            780.0, 335.0, 464.0, 788.0, 771.0, 455.0, 950.0, 25.0, 22.0, 576.0, 969.0, 122.0, 86.0,
            74.0,
        ];
        let m = Matrix::from_shape_vec((N, N), c).unwrap();
        let result = lapjv(&m).unwrap();
        (m, result)
    }
```

--------------------------------

### LAPJV Algorithm Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/fn.lapjv.html

This function implements the LAPJV algorithm to solve the Linear Assignment Problem. It requires a cost matrix and returns the optimal assignment and its cost. Ensure the cost matrix adheres to the LapJVCost trait.

```rust
pub fn lapjv<T>(
    costs: &Matrix<T>,
) -> Result<(Vec<usize>, Vec<usize>), LapJVError>
where
    T: LapJVCost,

```

--------------------------------

### Dijkstra Shortest Path in LAPJV

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Implements Dijkstra's shortest path algorithm to find an augmenting path in the context of the LAPJV algorithm. It runs until an unassigned column is added to the shortest path tree.

```rust
let dim = self.dim;
        let mut collist = Vec::with_capacity(dim); // list of columns to be scanned in various ways.
        let mut d = Vec::with_capacity(dim); // 'cost-distance' in augmenting path calculation.

        let mut lo = 0;
        let mut hi = 0;
        let mut n_ready = 0;

        // Dijkstra shortest path algorithm.
        // runs until unassigned column added to shortest path tree.
        for i in 0..dim {
            collist.push(i);
            d.push(self.reduced_cost(start_i, i));
            pred[i] = start_i;
        }

        trace!("d: {:?}", d);
        let mut final_j = None;
        while final_j.is_none() {
            if lo == hi {
                trace!("{}..{} -> find", lo, hi);
                n_ready = lo;
                hi = find_dense(dim, lo, &d, &mut collist);
                trace!("check {}..{}", lo, hi);
                // check if any of the minimum columns happens to be unassigned.
                // if so, we have an augmenting path right away.
                for &j in collist.iter().take(hi).skip(lo) {
                    if self.in_col[j] == usize::MAX {
                        final_j = Some(j);
                    }
                }
            }

            if final_j.is_none() {
                trace!("{}..{} -> scan", lo, hi);
                final_j = self.scan_dense(&mut lo, &mut hi, &mut d, &mut collist, pred);
            }
        }

        trace!("found final_j={:?}", final_j);
        trace!("cols={:?}", collist);
        let mind = d[collist[lo]];
        for &j in collist.iter().take(n_ready) {
            self.v[j] += d[j] - mind;
        }
        final_j.unwrap()
```

--------------------------------

### LapJV::new

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Constructs a new LapJV instance with the given cost matrix. The cost matrix should be of type `Matrix<T>` where `T` implements the `LapJVCost` trait.

```APIDOC
## LapJV::new

### Description
Constructs a new `LapJV` instance with the given cost matrix.

### Signature
```rust
pub fn new(costs: &'a Matrix<T>) -> Self
```

### Parameters
* `costs`: A reference to a `Matrix<T>` representing the cost matrix for the assignment problem.
```

--------------------------------

### lapjv

Source: https://docs.rs/lapjv/0.3.0/index.html

Solve LAP problem given cost matrix. This is an implementation of the LAPJV algorithm.

```APIDOC
## lapjv

### Description
Solve LAP problem given cost matrix. This is an implementation of the LAPJV algorithm described in: R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987).

### Function Signature
```rust
fn lapjv(cost_matrix: &Matrix) -> Result<(f64, Matrix), LapJVError>
```

### Parameters
* `cost_matrix` (*Matrix*) - A reference to the cost matrix.

### Returns
* `Result<(f64, Matrix), LapJVError>` - A Result containing a tuple of the optimal cost (f64) and the assignment matrix (Matrix), or a LapJVError if the problem could not be solved.
```

--------------------------------

### Find Dense Minimums in LAPJV

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Finds the minimum and second minimum values within a dense list of column costs. It rearranges the `collist` to place columns with the minimum cost at the beginning.

```rust
fn find_dense<T>(dim: usize, lo: usize, d: &[T], collist: &mut [usize]) -> usize
where
    T: LapJVCost,
{
    let mut hi = lo + 1;
    let mut mind = d[collist[lo]];
    for k in hi..dim {
        let j = collist[k];
        let h = d[j];
        if h <= mind {
            if h < mind {
                // new minimum.
                hi = lo; // restart list at index low.
                mind = h;
            }
            // new index with same minimum, put on undex up, and extend list.
            collist[k] = collist[hi];
            collist[hi] = j;
            hi += 1;
        }
    }
    hi
}
```

--------------------------------

### lapjv

Source: https://docs.rs/lapjv/0.3.0/lapjv

Solve LAP problem given cost matrix. This is an implementation of the LAPJV algorithm described in: R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987)

```APIDOC
## lapjv

### Description
Solve LAP problem given cost matrix. This is an implementation of the LAPJV algorithm described in: R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987)

### Function Signature
`fn lapjv(cost: &Matrix<f64>) -> (f64, Vec<i32>, Vec<i32>)`

### Parameters
* `cost` (Matrix<f64>) - A reference to the cost matrix.
```

--------------------------------

### Provide Error Context - LapJVError (Nightly)

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

An experimental, nightly-only API that provides type-based access to error context, intended for error reporting tools.

```rust
fn provide<'a>(&'a self, request: &mut Request<'a>)
```

--------------------------------

### Test Dimension Size Augmentation Path

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Tests the LAPJV algorithm with a specific matrix size (4x4) and a predefined set of values. This is useful for verifying the algorithm's behavior with different input dimensions.

```rust
fn dim_size_augmentation_path() {
        let m = vec![
            849.096136535884,
            964.7344199800348,
            1658.3745235461179,
            1324.4750426251608,
            1565.0473271789378,
            1777.6465563492143,
            4280.139067225529,
            3411.9521087119633,
            1360.3260879628992,
            1546.701932942709,
            1304.724155636392,
            1048.3839719313205,
            1559.5777872153571,
            1769.1684309771547,
            3663.2542984837355,
            2926.089718214265,
        ];
        let matrix = Matrix::from_shape_vec((4, 4), m).unwrap();
        let result = lapjv(&matrix);
        result.unwrap();
    }
```

--------------------------------

### Find Minimums and Second Minimums in a Row

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Finds the minimum and second minimum cost from a row, along with their corresponding column indices. This is used to efficiently determine potential assignments.

```rust
fn find_umins_plain<T>(local_cost: ndarray::ArrayView1<T>, v: &[T]) -> (T, T, usize, Option<usize>)
where
    T: LapJVCost,
{
    let mut umin = local_cost[0] - v[0];
    let mut usubmin = T::max_value();
    let mut j1 = 0;
    let mut j2 = None;
    for j in 1..local_cost.dim() {
        let h = local_cost[j] - v[j];
        if h < usubmin {
            if h >= umin {
                usubmin = h;
                j2 = Some(j);
            } else {
                usubmin = umin;
                umin = h;

```

--------------------------------

### Helper Function: solve_random10

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

A helper function that generates a 10x10 cost matrix and solves it using `lapjv`. This is used in the `test_solve_random10` test case.

```rust
fn solve_random10() -> (Matrix<f64>, (Vec<usize>, Vec<usize>)) {
    const N: usize = 10;
    let c = vec![
        612.0, 643.0, 717.0, 2.0, 946.0, 534.0, 242.0, 235.0, 376.0, 839.0, 224.0, 141.0,
        799.0, 180.0, 386.0, 745.0, 592.0, 822.0, 421.0, 42.0, 241.0, 369.0, 831.0, 67.0,
    ];
    // ... (rest of the function omitted for brevity in this example, but would typically include matrix creation and lapjv call)
```

--------------------------------

### cost

Source: https://docs.rs/lapjv/0.3.0/lapjv

Calculate solution cost by a result row

```APIDOC
## cost

### Description
Calculate solution cost by a result row.

### Function Signature
`fn cost(cost: &Matrix<f64>, row_ind: &[i32], col_ind: &[i32]) -> f64`

### Parameters
* `cost` (Matrix<f64>) - A reference to the cost matrix.
* `row_ind` (&[i32]) - A slice of row indices.
* `col_ind` (&[i32]) - A slice of column indices.
```

--------------------------------

### LapJV::solve

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Executes the LAPJV algorithm to find the optimal assignment and returns the resulting row and column assignments.

```APIDOC
## LapJV::solve(mut self)

### Description
Solves the Linear Assignment Problem using the initialized `LapJV` instance. It performs the necessary steps of the LAPJV algorithm and returns the optimal assignment.

### Method Signature
```rust
pub fn solve(mut self) -> Result<(Vec<usize>, Vec<usize>), LapJVError>
```

### Returns
- `Result<(Vec<usize>, Vec<usize>), LapJVError>`: A tuple containing two vectors: `in_row` and `in_col`, representing the optimal assignment. `in_row[i]` is the column assigned to row `i`, and `in_col[j]` is the row assigned to column `j`. Returns `LapJVError` if the matrix is not square or if the computation is cancelled.
```

--------------------------------

### LAPJV Random Matrix Generation

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Shows how to generate a large random cost matrix (512x512) for testing purposes. The resulting matrix is used with the `lapjv` function, though the result is not asserted in this snippet.

```rust
const DIM: usize = 512;
let mut m = Vec::with_capacity(DIM * DIM);
for _ in 0..DIM * DIM {
    m.push(rand::random::<f64>() * 100.0);
}
let m = Matrix::from_shape_vec((DIM, DIM), m).unwrap();
let _result = lapjv(&m).unwrap();
```

--------------------------------

### cost

Source: https://docs.rs/lapjv/0.3.0/index.html

Calculate solution cost by a result row.

```APIDOC
## cost

### Description
Calculate solution cost by a result row.

### Function Signature
```rust
fn cost(result_row: &Matrix) -> f64
```

### Parameters
* `result_row` (*Matrix*) - A reference to the result matrix.

### Returns
* `f64` - The calculated solution cost.
```

--------------------------------

### Solve LAP problem given cost matrix

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Provides a high-level function to solve the Linear Assignment Problem using the LAPJV algorithm. It takes a cost matrix and returns the optimal assignment.

```rust
/// Solve LAP problem given cost matrix
/// This is an implementation of the LAPJV algorithm described in:
/// R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for
/// Dense and Sparse Linear Assignment Problems. Computing 38, 325-340
/// (1987)
pub fn lapjv<T>(costs: &Matrix<T>) -> Result<(Vec<usize>, Vec<usize>), LapJVError>
where
    T: LapJVCost,
{
    LapJV::new(costs).solve()
}
```

--------------------------------

### LapJV::solve

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Solves the Linear Assignment Problem using the initialized cost matrix. Returns a `Result` containing the optimal assignment or a `LapJVError`.

```APIDOC
## LapJV::solve

### Description
Solves the LAP problem given the cost matrix. This is an implementation of the LAPJV algorithm.

### Signature
```rust
pub fn solve(self) -> Result<(Vec<usize>, Vec<usize>), LapJVError>
```

### Returns
A `Result` which is either:
- `Ok((Vec<usize>, Vec<usize>))` containing the row and column assignments.
- `Err(LapJVError)` if an error occurred during the solving process.
```

--------------------------------

### From Trait Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Provides the `from` method, which returns the argument unchanged. This is a blanket implementation for any type `T`.

```rust
fn from(t: T) -> T
```

--------------------------------

### Try Convert From Value - TryFrom Trait

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Attempts to perform a conversion from another type into the current type. Returns a `Result` to handle potential conversion failures.

```rust
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
```

--------------------------------

### lapjv

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Solves the Linear Assignment Problem (LAP) given a cost matrix. This function implements the LAPJV algorithm.

```APIDOC
## lapjv<T>

### Description
Solves the Linear Assignment Problem (LAP) given a cost matrix. This function implements the LAPJV algorithm described in R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987).

### Function Signature
```rust
pub fn lapjv<T>(costs: &Matrix<T>) -> Result<(Vec<usize>, Vec<usize>), LapJVError>
where
    T: LapJVCost,
```

### Parameters
- `costs` (*Matrix<T>*): A reference to a 2D ndarray matrix representing the costs. The matrix must be square.

### Returns
- `Result<(Vec<usize>, Vec<usize>), LapJVError>`: A tuple containing two vectors: the row assignments and the column assignments. Returns `LapJVError` if the matrix is not square or if the computation is cancelled.
```

--------------------------------

### lapjv function

Source: https://docs.rs/lapjv/0.3.0/lapjv/index.html

Solves the Linear Assignment Problem given a cost matrix. This function implements the LAPJV algorithm as described in R. Jonker and A. Volgenant's paper.

```APIDOC
## lapjv

### Description
Solve LAP problem given cost matrix. This is an implementation of the LAPJV algorithm described in: R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987)

### Parameters
* **cost_matrix** (Matrix) - The input cost matrix for the assignment problem.

### Returns
* A tuple containing the total minimum cost and the assignment vector.
```

--------------------------------

### Calculate Solution Cost

Source: https://docs.rs/lapjv/0.3.0/lapjv/fn.cost.html

Calculates the total cost of an assignment given a cost matrix and a solution row. Requires the cost type `T` to implement `LapJVCost`.

```rust
pub fn cost<T>(input: &Matrix<T>, row: &[usize]) -> T
where
    T: LapJVCost,

```

--------------------------------

### Into Trait Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Provides the `into` method, which calls `U::from(self)`. This is a blanket implementation for types `T` and `U` where `U` implements `From<T>`.

```rust
fn into(self) -> U
```

--------------------------------

### LapJV::cancellation - Cancellation Token

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Returns a `Cancellation` token that can be used to cancel the LAP solving process from another thread.

```rust
pub fn cancellation(&self) -> Cancellation
```

--------------------------------

### cost Function Signature

Source: https://docs.rs/lapjv/0.3.0/lapjv/fn.cost.html

Calculates the solution cost using the provided cost matrix and assignment row.

```APIDOC
## cost<T>

### Description
Calculate solution cost by a result row.

### Signature
```rust
pub fn cost<T>(input: &Matrix<T>, row: &[usize]) -> T
where
    T: LapJVCost,
```

### Parameters
* `input`: A reference to the cost matrix.
* `row`: A slice representing the assignment row.

### Returns
The calculated cost of type `T`.
```

--------------------------------

### cost

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Calculates the total cost of an assignment given a cost matrix and a row assignment vector.

```APIDOC
## cost<T>

### Description
Calculates the total cost of an assignment by summing the costs of the assigned pairs. It takes the original cost matrix and a vector representing the row assignments.

### Function Signature
```rust
pub fn cost<T>(input: &Matrix<T>, row: &[usize]) -> T
where
    T: LapJVCost,
```

### Parameters
- `input` (*&Matrix<T>*): A reference to the cost matrix.
- `row` (*&[usize]*): A slice representing the row assignments. `row[i]` is the column assigned to row `i`.

### Returns
- `T`: The total cost of the assignment.
```

--------------------------------

### Calculate solution cost by a result row

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Calculates the total cost of an assignment given a cost matrix and a row assignment vector. This is useful for verifying the solution.

```rust
/// Calculate solution cost by a result row
pub fn cost<T>(input: &Matrix<T>, row: &[usize]) -> T
where
    T: LapJVCost,
{
    (0..row.len()).fold(T::zero(), |acc, i| acc + input[(i, row[i])])
}
```

--------------------------------

### LapJV::solve - Solve LAP

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Solves the Linear Assignment Problem using the LAPJV algorithm. Returns a `Result` containing the optimal assignment or a `LapJVError`.

```rust
pub fn solve(self) -> Result<(Vec<usize>, Vec<usize>), LapJVError>
```

--------------------------------

### Augmenting Path for Dense Cost Matrix

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Finds an augmenting path for a dense cost matrix. This function is crucial for updating the current assignment in the linear assignment problem.

```rust
    fn ca_dense(&mut self) -> Result<(), LapJVError> {
        let dim = self.dim;
        let mut pred = vec![0; dim];

        let free_rows = std::mem::take(&mut self.free_rows);
        for freerow in free_rows {
            trace!("looking at freerow={}", freerow);

            self.check_cancelled()?;

            let mut i = usize::MAX;
            let mut k = 0;
            let mut j = self.find_path_dense(freerow, &mut pred);
            debug_assert!(j < dim);
            while i != freerow {
                i = pred[j];
                self.in_col[j] = i;
                std::mem::swap(&mut j, &mut self.in_row[i]);
                k += 1;
                if k > dim {
                    return Err(LapJVError {
                        kind: ErrorKind::Msg("Error: ca_dense will not finish"),
                    });
                }
            }
        }
        Ok(())
    }
```

--------------------------------

### Cancellation Methods

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.Cancellation.html

Provides methods to cancel an operation and check if it has been cancelled.

```APIDOC
## pub fn cancel(&self)

### Description
Marks the cancellation as requested.

### Method
`cancel`
```

```APIDOC
## pub fn is_cancelled(&self) -> bool

### Description
Returns `true` if cancellation has been requested.

### Method
`is_cancelled`

### Returns
- `bool`: `true` if cancelled, `false` otherwise.
```

--------------------------------

### Scan Dense Columns in LAPJV

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Scans columns to decrease the 'd' values of target columns using a 'scan' column. It updates 'd' and 'pred' arrays and identifies potential augmenting paths.

```rust
fn scan_dense(
        &self,
        plo: &mut usize,
        phi: &mut usize,
        d: &mut [T],
        collist: &mut [usize],
        pred: &mut [usize],
    ) -> Option<usize> {
        let mut lo = *plo;
        let mut hi = *phi;
        while lo != hi {
            let j = collist[lo];
            lo += 1;
            let i = self.in_col[j];
            let mind = d[j];
            let h = self.reduced_cost(i, j) - mind;
            // For all columns in TODO
            for k in hi..collist.len() {
                let j = collist[k];
                let cred_ij = self.reduced_cost(i, j) - h;
                if cred_ij < d[j] {
                    d[j] = cred_ij;
                    pred[j] = i;
                    if (cred_ij - mind).abs() < T::epsilon() {
                        // if cred_ij == mind {
                        if self.in_col[j] == usize::MAX {
                            return Some(j);
                        }
                        collist[k] = collist[hi];
                        collist[hi] = j;
                        hi += 1;
                    }
                }
            }
        }
        // Note: only change lo and hi if the item was not found
        *plo = lo;
        *phi = hi;
        None
    }
```

--------------------------------

### Convert To String - ToString Trait

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Converts the value into a `String` representation. This relies on the type implementing the `Display` trait.

```rust
fn to_string(&self) -> String
```

--------------------------------

### kind() method

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Retrieves the error kind from a LapJVError instance.

```APIDOC
### impl LapJVError

#### pub fn kind(&self) -> ErrorKind
Retrieves the specific kind of error represented by the `LapJVError`.
```

--------------------------------

### LapJV::cancellation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Returns a `Cancellation` token that can be used to cancel the ongoing LAPJV solve operation from another thread.

```APIDOC
## LapJV::cancellation

### Description
Returns a `Cancellation` token which can be cancelled from another thread.

### Signature
```rust
pub fn cancellation(&self) -> Cancellation
```

### Returns
A `Cancellation` token.
```

--------------------------------

### Augmenting Row Reduction for Dense Matrix

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Performs augmenting row reduction for dense cost matrices. This function is part of the core algorithm for solving the linear assignment problem.

```rust
    fn carr_dense(&mut self) {
        // AUGMENTING ROW REDUCTION
        // scan all free rows.
        // in some cases, a free row may be replaced with another one to be scanned next.
        trace!("carr_dense");
        let dim = self.dim;
        let mut current = 0;
        let mut new_free_rows = 0; // start list of rows still free after augmenting row reduction. 
        let mut rr_cnt = 0;
        let num_free_rows = self.free_rows.len();

        while current < num_free_rows {
            rr_cnt += 1;
            let free_i = self.free_rows[current];
            current += 1;
            // find minimum and second minimum reduced cost over columns.
            let (v1, v2, mut j1, j2) = find_umins_plain(self.costs.row(free_i), &self.v);

            let mut i0 = self.in_col[j1];
            let v1_new = self.v[j1] - (v2 - v1);
            let v1_lowers = v1_new < self.v[j1]; // the trick to eliminate the epsilon bug

            if rr_cnt < current * dim {
                if v1_lowers {
                    // change the reduction of the minimum column to increase the minimum
                    // reduced cost in the row to the subminimum.
                    self.v[j1] = v1_new;
                } else if i0 != usize::MAX && j2.is_some() {
                    // minimum and subminimum equal.
                    // minimum column j1 is assigned.
                    // swap columns j1 and j2, as j2 may be unassigned.
                    j1 = j2.unwrap();
                    i0 = self.in_col[j1];
                }
                if i0 != usize::MAX {
                    // minimum column j1 assigned earlier.
                    if v1_lowers {
                        // put in current k, and go back to that k.
                        // continue augmenting path i - j1 with i0.
                        current -= 1;
                        self.free_rows[current] = i0;
                    } else {
                        // no further augmenting reduction possible.
                        // store i0 in list of free rows for next phase.
                        self.free_rows[new_free_rows] = i0;
                        new_free_rows += 1;
                    }
                }
            } else if i0 != usize::MAX {
                self.free_rows[new_free_rows] = i0;
                new_free_rows += 1;
            }
            self.in_row[free_i] = j1;
            self.in_col[j1] = free_i;
        }
        self.free_rows.truncate(new_free_rows);
    }
```

--------------------------------

### cost function

Source: https://docs.rs/lapjv/0.3.0/lapjv/index.html

Calculates the total cost of a solution based on a given result row (assignment).

```APIDOC
## cost

### Description
Calculate solution cost by a result row.

### Parameters
* **result_row** (Matrix) - The assignment result row for which to calculate the cost.

### Returns
* The total cost of the assignment.
```

--------------------------------

### TryInto Trait Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Provides the `try_into` method for attempting conversion. The `Error` type is determined by `U`'s `TryFrom<T>` implementation. This is a blanket implementation for types `T` and `U` where `U` implements `TryFrom<T>`.

```rust
type Error = <U as TryFrom<T>>::Error
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
```

--------------------------------

### Borrow Trait Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Provides the `borrow` method for immutable borrowing. This is a blanket implementation for any type `T`.

```rust
fn borrow(&self) -> &T
```

--------------------------------

### BorrowMut Trait Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Provides the `borrow_mut` method for mutable borrowing. This is a blanket implementation for any type `T`.

```rust
fn borrow_mut(&mut self) -> &mut T
```

--------------------------------

### Format LapJVError for Display

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Implements the Display trait for LapJVError, enabling user-friendly string representations of the error. This is commonly used for error messages.

```rust
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>
```

--------------------------------

### LapJV::cancellation

Source: https://docs.rs/lapjv/0.3.0/src/lapjv/lib.rs.html

Returns a `Cancellation` token that can be used to cancel the ongoing LAPJV computation from another thread.

```APIDOC
## LapJV::cancellation(&self)

### Description
Provides a `Cancellation` token that allows for external cancellation of the LAPJV solving process. This is useful for long-running computations where early termination might be desired.

### Method Signature
```rust
pub fn cancellation(&self) -> Cancellation
```

### Returns
- `Cancellation`: A clone of the `Cancellation` token associated with this `LapJV` instance.
```

--------------------------------

### Try Convert Into Another Type - TryInto Trait

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJVError.html

Attempts to convert the current value into another type that implements `TryFrom<T>`. Returns a `Result` to handle potential conversion failures.

```rust
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
```

--------------------------------

### TryFrom Trait Implementation

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Provides the `try_from` method for attempting conversion. The `Error` type is `Infallible`. This is a blanket implementation for types `T` and `U` where `U` implements `Into<T>`.

```rust
type Error = Infallible
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
```

--------------------------------

### LapJVCost Trait Implementation for Generic Type T

Source: https://docs.rs/lapjv/0.3.0/lapjv/trait.LapJVCost.html

Shows a generic implementation of the LapJVCost trait for any type T that satisfies the Float, AddAssign, SubAssign, and Debug bounds.

```rust
impl<T> LapJVCost for T
where T: Float + AddAssign + SubAssign + Debug,
```

--------------------------------

### LapJVCost Trait Definition

Source: https://docs.rs/lapjv/0.3.0/lapjv/trait.LapJVCost.html

This snippet shows the definition of the LapJVCost trait, outlining its required supertraits.

```APIDOC
## Trait LapJVCost

```rust
pub trait LapJVCost: Float + AddAssign + SubAssign + Debug { }
```

### Description

The `LapJVCost` trait is a marker trait that requires implementing types to also implement `Float`, `AddAssign`, `SubAssign`, and `Debug`. This ensures that the types used for costs in the lapjv algorithm support necessary arithmetic operations and debugging capabilities.

### Dyn Compatibility

This trait is **not** dyn compatible, meaning it cannot be used with dynamic dispatch (e.g., `dyn LapJVCost`).
```

--------------------------------

### LapJV Struct Definition

Source: https://docs.rs/lapjv/0.3.0/lapjv/struct.LapJV.html

Defines the `LapJV` struct, which holds the cost matrix for the LAP. It is generic over the cost type `T` and has private fields.

```rust
pub struct LapJV<'a, T: 'a> { /* private fields */ }
```
Tokens:
Raw