| Type: | Package |
| Title: | Solves Minimum Cost Bipartite Matching Problems |
| Version: | 0.3 |
| Date: | 2023-09-05 |
| Maintainer: | Justin Silverman <JustinSilverman@psu.edu> |
| Copyright: | See file COPYRIGHT for details |
| Description: | Header library and R functions to solve minimum cost bipartite matching problem using Huhn-Munkres algorithm (Hungarian algorithm; https://en.wikipedia.org/wiki/Hungarian_algorithm; Kuhn (1955) <doi:10.1002/nav.3800020109>). This is a repackaging of code written by Cong Ma in the GitHub repo https://github.com/mcximing/hungarian-algorithm-cpp. |
| License: | GPL-2 | GPL-3 [expanded from: GPL (≥ 2)] |
| Imports: | Rcpp (≥ 1.0.1) |
| LinkingTo: | Rcpp |
| Suggests: | testthat (≥ 2.1.0), knitr, rmarkdown, ggplot2 |
| RoxygenNote: | 7.2.3 |
| VignetteBuilder: | knitr |
| URL: | https://github.com/jsilve24/RcppHungarian |
| NeedsCompilation: | yes |
| Packaged: | 2023-09-05 22:14:19 UTC; jds6696 |
| Author: | Justin Silverman [aut, cre], Cong Ma [ctb, cph], Markus Buehren [ctb, cph] |
| Repository: | CRAN |
| Date/Publication: | 2023-09-05 22:40:02 UTC |
RcppHungarian
Description
Header Library and R Functions to Solve Minimum Cost Bipartite Matching Problem using Huhn-Munkres algorithm (Hungarian algorithm; <https://en.wikipedia.org/wiki/Hungarian_algorithm>; Kuhn (1955) doi:10.1002/nav.3800020109). This is a repackaging of code written by Cong Ma in the GitHub repo <https://github.com/mcximing/hungarian-algorithm-cpp>.
Hungarian Algorithm Solver
Description
Solves weighted bipartite matching problems (e.g., optimal matching of people to cars or optimal matching of students to colleges, etc...)
Usage
HungarianSolver(costMatrix)
Arguments
costMatrix |
matrix giving cost of each possible pairing - can be rectangular |
Details
this is a copy/wrapper for the code developed by Cong Ma and made available as a github repository (mcximing/hungarian-algorithm-cpp). Code was changed to a header only file for use in other Rcpp packages.
Value
List with cost and parings, pairings are given as an Nx2 matrix giving edges that are matched (1-indexed rather than 0-indexed as it will be returned to R)
Examples
cost <- rbind(c(1, 2, 0),
c(2, 0, 1),
c(1, 4, 19))
soln <- HungarianSolver(cost)
soln