[Numpy-discussion] Linear assignment problem: Jonker-Volgenant algorithm

[Benjamin Root]

On Tue, May 17, 2011 at 12:49 PM, Gael Varoquaux <
gael.varoquaux at normalesup.org> wrote:

> On Tue, May 17, 2011 at 09:36:40AM -0700, Hoyt Koepke wrote:
> > > OK, your input is making my motivation to fight with Jonker-Volgenant
> go
> > > down. I'll see with the other people involved if we still target
> > > Jonger-Volgenant, or if we stick with the hungarian algorithm, in which
> > > case the problem is solved.
>
> > I'd do that route. From my (somewhat anecdotal) observations, a well
> > coded version of the Hungarian algorithm will beat moderately
> > well-coded implementations of other algorithms on most common types of
> > problems; the data structures in other algorithms are harder to get
> > right.  Also, they often tend to show their strengths only on
> > sufficiently large problems.  I'd guess that for a speed up, your time
> > would be better spent profiling and maybe cythoning your current
> > implementation of the Hungarian algorithm.
>
> I had some time in a meeting today, and did just that:
>
> https://github.com/GaelVaroquaux/scikit-learn/blob/hungarian/scikits/learn/utils/hungarian.py
>
> https://github.com/GaelVaroquaux/scikit-learn/blob/hungarian/scikits/learn/utils/tests/test_hungarian.py
>
> There's maybe a factor of 2 to be gained in this implementation by
> writing a few helper functions in Cython. I decided that I would stop
> optimization it until it became an actual bottleneck somewhere.
>
> Cheers,
>
> Gaël
>

Is this hungarian method in an official scikits package, or is this just
your own thing?  I currently use an old tracking algorithm that uses the
hungarian method for solving the bipartite graph problem, and I have been
unsuccessful in wrapping its C++ library for python.  With your module, I
should then be able to port a decent implementation of the tracker into
Python.

Ben Root
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20110517/8496d66f/attachment.html>