sparse_linear_assignment/
lib.rs

1//! # Sparse linear assignment
2//! Solvers for weighted perfect matching problem ([linear assignment](https://en.wikipedia.org/wiki/Assignment_problem)) for bipartite graphs. Both solvers use variants of auction algorithm and implemented in Rust.
3//!
4//!    * [KhoslaSolver](KhoslaSolver) is best suited for asymmetric k-regular sparse graphs. The algorithm is presented in [this paper](https://arxiv.org/pdf/2101.07155.pdf). It stops in finite number of iterations.
5//!    * [ForwardAuctionSolver](ForwardAuctionSolver) works better for symmetric assignment problems. It uses ε-scaling to speedup the auction algorithm. The implementation is based on [sslap](https://github.com/OllieBoyne/sslap). When there is no perfect matching it enters in endless loop and stops after `max_iterations` number of iterations.
6
7#[cfg(feature = "khosla")]
8pub use crate::ksparse::KhoslaSolver;
9pub use crate::solution::AuctionSolution;
10pub use crate::solver::AuctionSolver;
11#[cfg(feature = "forward")]
12pub use crate::symmetric::ForwardAuctionSolver;
13
14#[cfg(feature = "khosla")]
15pub mod ksparse;
16pub mod solution;
17pub mod solver;
18#[cfg(feature = "forward")]
19pub mod symmetric;