{"thread":{"id":"59356","subject":"Question: How range-diff lapjv algorithm work","startedAt":"2023-03-08T06:37:44Z","lastAt":"2023-03-28T13:22:59Z","messageCount":4,"participants":["ZheNing Hu","Martin Ågren","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"473168","messageId":"CAOLTT8TcX6Wit=AOFGNLjA4v9HAvJJxCEtt3JhgUR+3OARycNw@mail.gmail.com","threadId":"59356","inReplyTo":null,"subject":"Question: How range-diff lapjv algorithm work","fromName":"ZheNing Hu","fromEmail":"adlternative@gmail.com","sentAt":"2023-03-08T06:37:25Z","receivedAt":"2023-03-08T06:37:44Z","isPatch":false,"sender":{"key":"adlternative@gmail.com","avatar":"https://avatars.githubusercontent.com/u/58138461?v=4"},"body":"I was recently reading the source code of git-range-diff.\n\nIts Steps:\n1. Use git log <range> to generate two collections of patches for\nranges a and b.\n2. Use the hash table on both sets to find the commit with the exact\nsame patch as an \"exact match\".\n3. A cost matrix whose length and width are a.nr + b.br is generated.\nThe cost of a completely matched item is 0, and the cost between two\nsets of patches is represented by the diffsize(a, b) of the patch.\n4. Use the LAPJV algorithm to find the best match between multiple\npatches of the two sets.\n5. Output results.\n\nMy question is:\n1. In step 3, why is the matrix size (a.nr + b.br) * (a.nr + b.br)\ninstead of a.nr * b.nr?\n\n2. Why the cost(x,y) which satisfies \"x ∈ [a.nr, a.nr + b.nr) y ∈ [0,\nb.nr) || x ∈ [0, a.nr) y ∈ [b.nr, b. The cost of nr + a.nr)\" is set to\n\"diffsize(a or b) * creation_factor / 100 : COST_MAX\"? What is the\nrole of creation_factor? [1]\n\n3. How does LAPJV work here? [2]\n\n[1]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/range-diff.c#L310\n[2]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/linear-assignment.c#L15\n\nThanks.\n--\nZheNing Hu\n"},{"id":"473169","messageId":"CAN0heSoVBmkuEOkW3wRNXRRjG7y8UqvORie6ocYnmQRz4jEXkg@mail.gmail.com","threadId":"59356","inReplyTo":"CAOLTT8TcX6Wit=AOFGNLjA4v9HAvJJxCEtt3JhgUR+3OARycNw@mail.gmail.com","subject":"Re: Question: How range-diff lapjv algorithm work","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2023-03-08T07:47:16Z","receivedAt":"2023-03-08T07:47:34Z","isPatch":false,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"On Wed, 8 Mar 2023 at 07:50, ZheNing Hu <adlternative@gmail.com> wrote:\n>\n> My question is:\n> 1. In step 3, why is the matrix size (a.nr + b.br) * (a.nr + b.br)\n> instead of a.nr * b.nr?\n\nThere's some explanation of that in the man page for `git range-diff`,\nunder \"ALGORITHM\". Look for \"To explain also new commits, we introduce\ndummy nodes on both sides:\".\n\n> 2. Why the cost(x,y) which satisfies \"x ∈ [a.nr, a.nr + b.nr) y ∈ [0,\n> b.nr) || x ∈ [0, a.nr) y ∈ [b.nr, b. The cost of nr + a.nr)\" is set to\n> \"diffsize(a or b) * creation_factor / 100 : COST_MAX\"? What is the\n> role of creation_factor? [1]\n\nThe `--creation-factor` command line option is also described in the\nmanpage.  There was a thread on the mailing list with various\ndiscussions around this creation factor a while back. Maybe there's\nsomething interesting there [1].\n\n> 3. How does LAPJV work here? [2]\n>\n> [1]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/range-diff.c#L310\n> [2]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/linear-assignment.c#L15\n\nThis appears to be based on work by Jonker and Volgenant. Maybe\nsearching for those names online could find something. Maybe not\ngit-specific, but even if it's just the general algorithm as such, it\nmight be possible to find different explanations of the algorithm.\n\nI haven't really studied this algorithm, but since it's faster than the\nHungarian algorithm, I could imagine that either\n\n  * it's super-useful to first understand the Hungarian algorithm, then\n    understand why and how the Jonker-Volgenant algorithm does better,\n    or,\n\n  * it's completely useless to first understand the Hungarian algorithm,\n    since they're so different.\n\n:-)\n\n[1] https://lore.kernel.org/git/1196830250.20220726145447@yandex.ru/\n\nMartin\n"},{"id":"473272","messageId":"CAOLTT8QAd_dzmDrkLpyVCZykb_sPzR0VzsPf_jtQqim_NpqZFg@mail.gmail.com","threadId":"59356","inReplyTo":"CAN0heSoVBmkuEOkW3wRNXRRjG7y8UqvORie6ocYnmQRz4jEXkg@mail.gmail.com","subject":"Re: Question: How range-diff lapjv algorithm work","fromName":"ZheNing Hu","fromEmail":"adlternative@gmail.com","sentAt":"2023-03-09T10:38:08Z","receivedAt":"2023-03-09T10:39:13Z","isPatch":false,"sender":{"key":"adlternative@gmail.com","avatar":"https://avatars.githubusercontent.com/u/58138461?v=4"},"body":"Martin Ågren <martin.agren@gmail.com> 于2023年3月8日周三 15:47写道：\n\n\n>\n> On Wed, 8 Mar 2023 at 07:50, ZheNing Hu <adlternative@gmail.com> wrote:\n> >\n> > My question is:\n> > 1. In step 3, why is the matrix size (a.nr + b.br) * (a.nr + b.br)\n> > instead of a.nr * b.nr?\n>\n> There's some explanation of that in the man page for `git range-diff`,\n> under \"ALGORITHM\". Look for \"To explain also new commits, we introduce\n> dummy nodes on both sides:\".\n>\n\nThanks, I can understand why the length of the matrix is \"a.nr + b.nr\" now.\nPatches in one collection may have no matching patches in the other\ncollection, this mismatch situation (\"o--C\" in the documentation) should\nalso count the cost.\n\n> > 2. Why the cost(x,y) which satisfies \"x ∈ [a.nr, a.nr + b.nr) y ∈ [0,\n> > b.nr) || x ∈ [0, a.nr) y ∈ [b.nr, b. The cost of nr + a.nr)\" is set to\n> > \"diffsize(a or b) * creation_factor / 100 : COST_MAX\"? What is the\n> > role of creation_factor? [1]\n>\n> The `--creation-factor` command line option is also described in the\n> manpage.  There was a thread on the mailing list with various\n> discussions around this creation factor a while back. Maybe there's\n> something interesting there [1].\n>\n\nI understand it now. Because mismatch \"o--C\" \"1--0\" cost are generally\ngreater than the cost of two completely different patches \"1--C\" \"0--0\".\nUse the creation-factor to reduce the cost of \"0-C\" \"1--0\" make\n\"o--C\", \"1--0\" as matching result.\n\n> > 3. How does LAPJV work here? [2]\n> >\n> > [1]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/range-diff.c#L310\n> > [2]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/linear-assignment.c#L15\n>\n> This appears to be based on work by Jonker and Volgenant. Maybe\n> searching for those names online could find something. Maybe not\n> git-specific, but even if it's just the general algorithm as such, it\n> might be possible to find different explanations of the algorithm.\n>\n> I haven't really studied this algorithm, but since it's faster than the\n> Hungarian algorithm, I could imagine that either\n>\n>   * it's super-useful to first understand the Hungarian algorithm, then\n>     understand why and how the Jonker-Volgenant algorithm does better,\n>     or,\n>\n>   * it's completely useless to first understand the Hungarian algorithm,\n>     since they're so different.\n>\n> :-)\n>\n\nAh, I had a look at the Hungarian algorithm earlier, because it is the most\ntypical algorithm in linear assignment problem, it can still be understood.\nI didn't read that paper by Jonker and Volgenant, but I should try to read\nit later.\n\n> [1] https://lore.kernel.org/git/1196830250.20220726145447@yandex.ru/\n>\n> Martin\n\nThanks for the answer!\n\n--\nZheNing Hu\n"},{"id":"474277","messageId":"f4b5d082-ebff-bfbb-7ede-0838c7b28790@gmx.de","threadId":"59356","inReplyTo":"CAOLTT8QAd_dzmDrkLpyVCZykb_sPzR0VzsPf_jtQqim_NpqZFg@mail.gmail.com","subject":"Re: Question: How range-diff lapjv algorithm work","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2023-03-28T13:22:42Z","receivedAt":"2023-03-28T13:22:59Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 9 Mar 2023, ZheNing Hu wrote:\n\n> Martin Ågren <martin.agren@gmail.com> 于2023年3月8日周三 15:47写道：\n>\n> > On Wed, 8 Mar 2023 at 07:50, ZheNing Hu <adlternative@gmail.com> wrote:\n> > >\n> > > 3. How does LAPJV work here? [2]\n> > >\n> > > [1]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/range-diff.c#L310\n> > > [2]: https://github.com/git/git/blob/725f57037d81e24eacfda6e59a19c60c0b4c8062/linear-assignment.c#L15\n> >\n> > This appears to be based on work by Jonker and Volgenant. Maybe\n> > searching for those names online could find something. Maybe not\n> > git-specific, but even if it's just the general algorithm as such, it\n> > might be possible to find different explanations of the algorithm.\n> >\n> > I haven't really studied this algorithm, but since it's faster than the\n> > Hungarian algorithm, I could imagine that either\n> >\n> >   * it's super-useful to first understand the Hungarian algorithm, then\n> >     understand why and how the Jonker-Volgenant algorithm does better,\n> >     or,\n> >\n> >   * it's completely useless to first understand the Hungarian algorithm,\n> >     since they're so different.\n> >\n> > :-)\n> >\n>\n> Ah, I had a look at the Hungarian algorithm earlier, because it is the most\n> typical algorithm in linear assignment problem, it can still be understood.\n> I didn't read that paper by Jonker and Volgenant, but I should try to read\n> it later.\n\nOh wow, what a blast from the past.\n\nAs I had briefly mentioned in\nhttps://lore.kernel.org/git/nycvar.QRO.7.76.6.1805032227520.77@tvgsbejvaqbjf.bet/,\nthe code I contributed in\nhttps://lore.kernel.org/git/3f51970cbc44bfe34133c48c0844ed3723e83808.1525361419.git.johannes.schindelin@gmx.de/\nis a port from some Java code I had written earlier in my life which was\nbased on the Pascal code provided in the cited paper.\n\nMy recollection has faded somewhat in the past 9 years. But maybe the\nfollowing helps, or provides at least some entertainment.\n\nMy first version of a \"linear assignment problem\" solver _did_ implement\nthe Hungarian algorithm, and I cannot even find it anymore, it must have\nbeen in 2010 or 2011. I only remember that the O(n^4) runtime was\nprohibitively expensive: I wanted to automatically track cells in\nmicroscope recordings as they migrated over a plate of agar. I _seem_ to\nremember that it was kind of okay for up to a couple dozen, but we wanted\nto track hundreds, even thousands of cells, for extended amounts of time.\nWe _could_ do it, kind of, on a ridiculously expensive machine with 128GB\n(I _think_), but naturally time on that machine was limited.\n\nSo I set out to implement the Munkres & Kuhn algorithm (see\nhttps://github.com/fiji/fiji/blob/7d683d2ad46d22ec2e0bdffe1aa02072ab62e359/src-plugins/TrackMate_/fiji/plugin/trackmate/tracking/hungarian/MunkresKuhnAlgorithm.java)\nbecause it promised O(n^3) complexity, and it did allow us to track the\namount of cells we were studying at the time.\n\nIt took a _week_ to wrap my head around that paper, even if being somewhat\nfamiliar with the Hungarian algorithm probably helped. You will see\nextensive notes in the initial code comment that I wrote for my future\nself if I ever needed to understand the algorithm _again_. Reading over\nthose notes after more than a decade, I realize that while they are\nhelpful for _me_, they probably help others only in conjunction with some\nquality time studying the paper.\n\nHowever, later on our tests revealed that The Munkres & Kuhn algorithm,\nwhile cubic in complexity, was still much slower than the Jonker &\nVolgenant algorithm. This algorithm is also cubic in complexity, but with\na lower constant factor, and I could implement much quicker than the\nMunkres & Kuhn algorithm because I essentially could cheat a bit by\nstudying the the paper while taking frequent peeks at the code. That also\nexplains why I did not take extensive notes this time and only added a\nterse code comment, and the commit message is not much better, either:\nhttps://github.com/trackmate-sc/TrackMate/commit/e306a02f76a6b6e383c0d32efaba565aca01a773\n\nMy tests must have been quite convincing back then because I already\nswitched to Jonker & Volgenant on the same day that I finished the\nimplementation:\nhttps://github.com/trackmate-sc/TrackMate/commit/ad5012827417a40673901a37af44904a2de73095\n\n_Years_ later, I wanted to run `git tbdiff` and couldn't because it\nuses not only Python but `numpy`. And `numpy` is largely native code, not\nPython, and I had the choice of either getting `numpy` to build on\nWindows, or reimplement `tbdiff` in pure C as a new Git built-in, I chose\nthe latter (because it seemed much easier). And since `tbdiff` used the\n`hungarian` algorithm (https://pypi.org/project/hungarian/) that\nimplements Munkres' algorithm (which I assumed was a slight variation of\nMunkres & Kuhn, with the same performance characteristics), I undusted my\nJava code and ported it. When I say \"undusted\", I lie, because it is still\nin use today. But it basically went unchanged for years because it is bug\nfree ;-)\n\nSo now that you know about the provenance of the code we're discussing, I\nhave to admit that I can contribute only very little to understand it,\nother than providing a couple of pointers:\n\nhttps://en.wikipedia.org/wiki/Hungarian_algorithm has a pretty good, if\nquite mathematical description of the algorithm. (And now that I read it,\nI realize that I probably inadvertently attributed Tomizawa's improvements\nto Munkres & Kuhn.)\n\nIt is amazingly hard to find good explanations on the 'net that aren't\nusing hard-code mathematical symbols, but I think I found one that\nillustrates how the algorithm works:\nhttps://medium.com/@rajneeshtiwari_22870/linear-assignment-problem-in-metric-learning-for-computer-vision-eba7d637c5d4\n\nHopefully that helps.\n\nCiao,\nJohannes\n"}]}