These pages are no longer maintained. See my new webpage
Brian P. Gerkey

Photo gallery

A C implementation of the Hungarian Method

by brian gerkey

UPDATE: 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.


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

Last updated $Date: 2004/12/08 16:16:39 $