yongyanghz / lapjv-algorithm-c Goto Github PK
View Code? Open in Web Editor NEWJonker-Volgenant / LAPJV algorithm for the linear assignment problem, in C language
Jonker-Volgenant / LAPJV algorithm for the linear assignment problem, in C language
During algorithm execution, according to cost
nature and range of values in assigncost, some variables can overflow, noticeably d
, v
.
For instance, if cost
is std::uintxx_t
I observed that some negative values can occurred when reducing cost. On the tests I did, it happened to work anyway due to modulo arithmetic with integers but I'm not sure that larger overflows can not occur, leading failure in the algorithm.
Even if cost
is double
or the largest possible integer, some computations may overflow (typically the final total cost).
Besides BIG
is not large enough. Why not set it to std::numeric_limits<cost>::max()
?
I don't understand the algorithm (neither from the code, nor the original paper) and I'm enable yet to determine if it has properties that limits the range of possible internal values according to input costs range.
Could it be possible to do this analysis and improve the computation safety (wrt overflows)?
Btw, free
could be holding booleans? Am I right? And it should be rename as it collisions with a langage keyword.
if assigncost rows != cols, the code could use?
The code is actually almost C and not C++. Would a translation to C++ be feasible (especially using modern data structures instead of dynamically allocated plain arrays)?
Hi @yongyanghz .
Is there an example code on how ti use the lap()
function to solve an assignment problem ?
Thanks.
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!
The comments in the example are misleading:
// A array to store row solution, 0 means not selected, 1 means selected
// A array to store column solution, 0 means not selected, 1 means selected
The arrays contain the picked indices within the row/column (so it is not 0 and 1).
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.