Re: Question: How range-diff lapjv algorithm work

Hi,

On Thu, 9 Mar 2023, ZheNing Hu wrote:

Martin Ågren [off-list ref] 于2023年3月8日周三 15:47写道：

quoted

On Wed, 8 Mar 2023 at 07:50, ZheNing Hu [off-list ref] wrote:

quoted

3. How does LAPJV work here? [2]

[1]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/range-diff.c#L310
[2]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/linear-assignment.c#L15

This appears to be based on work by Jonker and Volgenant. Maybe
searching for those names online could find something. Maybe not
git-specific, but even if it's just the general algorithm as such, it
might be possible to find different explanations of the algorithm.

I haven't really studied this algorithm, but since it's faster than the
Hungarian algorithm, I could imagine that either

  * it's super-useful to first understand the Hungarian algorithm, then
    understand why and how the Jonker-Volgenant algorithm does better,
    or,

  * it's completely useless to first understand the Hungarian algorithm,
    since they're so different.

:-)

Ah, I had a look at the Hungarian algorithm earlier, because it is the most
typical algorithm in linear assignment problem, it can still be understood.
I didn't read that paper by Jonker and Volgenant, but I should try to read
it later.

Oh wow, what a blast from the past.

As I had briefly mentioned in
https://lore.kernel.org/git/nycvar.QRO.7.76.6.1805032227520.77@tvgsbejvaqbjf.bet/ (local),
the code I contributed in
https://lore.kernel.org/git/3f51970cbc44bfe34133c48c0844ed3723e83808.1525361419.git.johannes.schindelin@gmx.de/ (local)
is a port from some Java code I had written earlier in my life which was
based on the Pascal code provided in the cited paper.

My recollection has faded somewhat in the past 9 years. But maybe the
following helps, or provides at least some entertainment.

My first version of a "linear assignment problem" solver _did_ implement
the Hungarian algorithm, and I cannot even find it anymore, it must have
been in 2010 or 2011. I only remember that the O(n^4) runtime was
prohibitively expensive: I wanted to automatically track cells in
microscope recordings as they migrated over a plate of agar. I _seem_ to
remember that it was kind of okay for up to a couple dozen, but we wanted
to track hundreds, even thousands of cells, for extended amounts of time.
We _could_ do it, kind of, on a ridiculously expensive machine with 128GB
(I _think_), but naturally time on that machine was limited.

So I set out to implement the Munkres & Kuhn algorithm (see
https://github.com/fiji/fiji/blob/7d683d2ad46d22ec2e0bdffe1aa02072ab62e359/src-plugins/TrackMate_/fiji/plugin/trackmate/tracking/hungarian/MunkresKuhnAlgorithm.java)
because it promised O(n^3) complexity, and it did allow us to track the
amount of cells we were studying at the time.

It took a _week_ to wrap my head around that paper, even if being somewhat
familiar with the Hungarian algorithm probably helped. You will see
extensive notes in the initial code comment that I wrote for my future
self if I ever needed to understand the algorithm _again_. Reading over
those notes after more than a decade, I realize that while they are
helpful for _me_, they probably help others only in conjunction with some
quality time studying the paper.

However, later on our tests revealed that The Munkres & Kuhn algorithm,
while cubic in complexity, was still much slower than the Jonker &
Volgenant algorithm. This algorithm is also cubic in complexity, but with
a lower constant factor, and I could implement much quicker than the
Munkres & Kuhn algorithm because I essentially could cheat a bit by
studying the the paper while taking frequent peeks at the code. That also
explains why I did not take extensive notes this time and only added a
terse code comment, and the commit message is not much better, either:
https://github.com/trackmate-sc/TrackMate/commit/e306a02f76a6b6e383c0d32efaba565aca01a773

My tests must have been quite convincing back then because I already
switched to Jonker & Volgenant on the same day that I finished the
implementation:
https://github.com/trackmate-sc/TrackMate/commit/ad5012827417a40673901a37af44904a2de73095

_Years_ later, I wanted to run `git tbdiff` and couldn't because it
uses not only Python but `numpy`. And `numpy` is largely native code, not
Python, and I had the choice of either getting `numpy` to build on
Windows, or reimplement `tbdiff` in pure C as a new Git built-in, I chose
the latter (because it seemed much easier). And since `tbdiff` used the
`hungarian` algorithm (https://pypi.org/project/hungarian/) that
implements Munkres' algorithm (which I assumed was a slight variation of
Munkres & Kuhn, with the same performance characteristics), I undusted my
Java code and ported it. When I say "undusted", I lie, because it is still
in use today. But it basically went unchanged for years because it is bug
free ;-)

So now that you know about the provenance of the code we're discussing, I
have to admit that I can contribute only very little to understand it,
other than providing a couple of pointers:

https://en.wikipedia.org/wiki/Hungarian_algorithm has a pretty good, if
quite mathematical description of the algorithm. (And now that I read it,
I realize that I probably inadvertently attributed Tomizawa's improvements
to Munkres & Kuhn.)

It is amazingly hard to find good explanations on the 'net that aren't
using hard-code mathematical symbols, but I think I found one that
illustrates how the algorithm works:
https://medium.com/@rajneeshtiwari_22870/linear-assignment-problem-in-metric-learning-for-computer-vision-eba7d637c5d4

Hopefully that helps.

Ciao,
Johannes