igraph/misc/
lsap.rs

1//! Linear sum assignment problem (`igraph_lsap.h`).
2
3use crate::{
4    error::{Error, Result},
5    ffi::*,
6    igraph_call,
7    matrix::Matrix,
8    vector::VectorInt,
9};
10
11/// Solves a balanced linear sum assignment problem with the Hungarian
12/// method.
13///
14/// `cost` is a square `n × n` matrix: rows are *agents*, columns are
15/// *tasks*, and `cost[(i, j)]` is the cost of agent `i` performing task `j`.
16/// The result assigns one distinct task to each agent (`result[i]` is the
17/// task of agent `i`, so the result is a permutation of `0..n`) so that the
18/// total cost `Σ cost[(i, result[i])]` is minimal.
19///
20/// - To *maximize* a profit instead, negate the matrix.
21/// - To forbid an assignment, give it a large finite cost (larger than
22///   the sum of all the other costs): infinite and NaN costs are rejected.
23/// - For an unbalanced problem with more agents than tasks, add dummy
24///   tasks (columns) of zero cost, and symmetrically for more tasks than
25///   agents.
26///
27/// This is the minimum weight perfect matching of the complete bipartite
28/// graph between agents and tasks; for sparse bipartite graphs see
29/// [`Graph::maximum_bipartite_matching`](crate::Graph::maximum_bipartite_matching)
30/// (which *maximizes* the total weight of a maximum matching).
31///
32/// Binds `igraph_solve_lsap` (declared in `igraph_lsap.h`, not in the HTML
33/// manual). Time complexity: `O(n³)`.
34///
35/// # Errors
36/// [`ErrorKind::InvalidValue`](crate::ErrorKind::InvalidValue) if the
37/// matrix is not square, or if a cost is NaN or infinite (checked in Rust:
38/// igraph 1.0.0 and 1.0.1 would loop forever).
39///
40/// # Examples
41///
42/// The example of igraph's own test suite:
43///
44/// ```
45/// use igraph::{misc, prelude::*};
46///
47/// let cost = Matrix::from_rows(&[
48///     [9.0, 2.0, 7.0, 8.0],
49///     [6.0, 4.0, 3.0, 7.0],
50///     [5.0, 8.0, 1.0, 8.0],
51///     [7.0, 6.0, 9.0, 4.0],
52/// ])?;
53/// let tasks = misc::solve_lsap(&cost)?;
54/// assert_eq!(tasks, vec![1, 0, 2, 3]);
55/// let total: f64 = tasks.iter().enumerate().map(|(i, &j)| cost[(i, j as usize)]).sum();
56/// assert_eq!(total, 13.0);
57/// # Ok::<(), igraph::Error>(())
58/// ```
59pub fn solve_lsap(cost: &Matrix) -> Result<Vec<i64>> {
60    let n = cost.nrow();
61    if cost.ncol() != n {
62        return Err(Error::invalid(format!(
63            "the cost matrix must be square, got {}x{}",
64            n,
65            cost.ncol()
66        )));
67    }
68    if n == 0 {
69        return Ok(Vec::new());
70    }
71    // The Hungarian method of igraph 1.0.0 and 1.0.1 loops forever on NaN or
72    // infinite costs (src/misc/lsap.c is unchanged in 1.0.1).
73    if !cost.as_slice().iter().all(|c| c.is_finite()) {
74        return Err(Error::invalid("the costs must be finite numbers"));
75    }
76    let mut res = VectorInt::new();
77    igraph_call!(igraph_solve_lsap(cost, n as igraph_int_t, &mut res))?;
78    Ok(res.into())
79}
igraph/misc/lsap.rs

igraph/misc/
lsap.rs
