search

yongyanghz / LAPJV-algorithm-c

Jonker-Volgenant / LAPJV algorithm for the linear assignment problem, in C language
32 stars 11 forks source link

Ported to Javascript #2

Closed Fil closed 7 years ago

Fil commented 7 years ago

Hello, I've just ported your implementation to Javascript here https://github.com/Fil/lap-jv

I had to work around rounding errors that were leading to infinite loops — I don't know if they also appear in the CPP version.

Thank you!

yongyanghz commented 7 years ago

Hi Phil, Sorry for late reply. But Have you solved your problem or find errors in my code? If not I will check the code again. Please let me know if your code work or not. Thanks.

Yong Yang

On Wed, Jan 4, 2017 at 12:50 AM, Philippe Rivière notifications@github.com wrote:

Hello, I've just ported your implementation to Javascript here https://github.com/Fil/lap-jv

I had to work around rounding errors that were leading to infinite loops — I don't know if they also appear in the CPP version.

Thank you!

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/yongyanghz/LAPJV-algorithm-c/issues/2, or mute the thread https://github.com/notifications/unsubscribe-auth/ARBagHK6b83WNuWJPFDqOUNxlasqLLSrks5rOnxvgaJpZM4LZzUR .

Fil commented 7 years ago

Please check the value of epsilon in my version. Without it my tests were quite often going into infinite loops, because of rounding errors. With epsilon I don't have this problem anymore. I'm sorry I don't have a reproductible example at hand, I think it was when there were around 5000 positions to optimize.

Fil commented 7 years ago

Here is a reproducible test: https://gist.github.com/Fil/377f9aa3f8f07c428d54eec3564f0eba

run it with node.js; if you change epsilon to 0 on line 82, you quite often get into an infinite loop because of rounding errors on the tests

yongyanghz commented 7 years ago

Hi Phil, I found a bug in my code, in lap.h file, the row and col type should be int, not double,I have fixed it and now the cpp version can work. Since I'm not familiar with java script, I haven't find error in your js version.

Fil commented 7 years ago

To be clear: the JS version works well.

However it is not strictly a port of your C code: the difference is this epsilon that I added, otherwise it would sometimes go into an infinite loop.

My question is if the C version also has this problem when two distances are very close and the comparison fails because of rounding.

yongyanghz commented 7 years ago

Hi Phil, I see you add epsilon as tolerance in js version. Some cases can cause Jonker's code to loop forever. According to Dr. Volgenant, "The failure is a consequence of a tolerance not suited for the data ... You have to reduce the value of the tolerance such that it is smaller than the smallest difference between any pair of cost elements in the cost matrix." You can also see Nota Bene part in this link.

Yong Yang

Fil commented 7 years ago

Thank you I will mention my solution there too. Maybe a good solution will come out of this!