| Brian P. Gerkey | |
Home | |
| CV | |
| Publications | |
| Research | |
| Player/Stage | |
| Tools/Resources | |
| Photo gallery | |
| Adbusting | |
 |
A C implementation of the Hungarian Method
by brian gerkey gerkey@robotics.stanford.eduUPDATE: Try Myriam Abramson's Java implementation, with test data.
UPDATE: Check out Cyrill Stachniss's implementation, which does not suffer from the endless loop problem mentioned in the NOTE below.
This package contains a C implementation (plus, as of version 0.3, Python bindings written by Dylan Shell), of Harold Kuhn's well-known Hungarian Method for solving Optimal Assignment Problems. The running time for this algorithm on an mXn problem is O(m*n^2), which correlates well with my own experience with this implementation.
The API is straightforward; see test.c for an example.
NOTE: hungarian_solve() seems to hang on certain extreme (degenerate?) inputs, especially when the rating matrix is non-square. I don't know what's causing this problem.
Download:
| File (size) | Notes |
| libhungarian-0.3.tar.gz (17KB) | Includes Python bindings, courtesy of Dylan Shell. |
| libhungarian-0.2.tar.gz (14KB) | Solves both minimum and maximum cost assignment problems, depending on whether HUNGARIAN_MIN or HUNGARIAN_MAX is passed to hungarian_init(). |
| libhungarian-0.1.tar.gz (12KB) | Initial release |