Hi Brian, On Wed, 30 May 2018, brian m. carlson wrote: > On Wed, May 30, 2018 at 09:14:06AM -0700, Stefan Beller wrote: > > Good point. I remember my initial reaction to the file names was > > expecting some hungarian notation, which totally didn't make sense, so > > I refrained from commenting. Searching the web for the algorithm, > > maybe 'lapjv.c' is adequate? (short for "Linear Assignment Problem > > Jonker Volgenant") Matlab has a function named lapjv solving the same > > problem, so it would fall in line with the outside world. > > > > Out of interest, why is it called hungarian in the first place? (I > > presume that comes from some background of DScho in image processing > > or such, so the the answer will be interesting for sure:) > > I think it's because tbdiff uses the hungarian Python module, which > implements the Hungarian method, also known as the Kuhn-Munkres > algorithm, for solving the linear assignment problem. This is the > Jonker-Volgenant algorithm, which solves the same problem. It's faster, > but less tolerant. > > At least this is what I just learned after about ten minutes of > searching. You learned well. The Assignment Problem (or "Linear Assignment Problem") is generally solved by the Hungarian algorithm. I forgot why it is called that way. Kuhn-Munkres came up with a simplification of the algorithm IIRC but it still is O(N^4). Then Jonker-Volgenant took a very different approach that somehow results in O(N^3). It's been *years* since I studied both implementations, so I cannot really explain what they do, and how the latter achieves its order-of-magnitude better performance. And after reading these mails, I agree that the name "hungarian" might be confusing. I also think that "lapjv" is confusing. In general, I try to let Matlab conventions inform on my naming as little as possible, and I find my naming fu a lot better for it. So in this case, how about `linear-assignment.c`? Ciao, Dscho
