A C implementation of the Hungarian Methodby brian gerkey gerkey@robotics.usc.eduUPDATE: 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 of Harold Kuhn's wellknown 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 nonsquare. I don't know what's causing this problem. Download:
