On Tue, May 17, 2011 at 12:49 PM, Gael Varoquaux < gael.varoqu...@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
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
