Kuhn-Munkres Algorithm (a.k.a. The Hungarian Algorithm)
Sameer Pradhan
pradhan at cemantix.org
Fri Feb 19 20:53:33 UTC 2021
Dear D-ers,
I wanted to port a currently Perl code used for scoring an NLP
task to D. A few folks have reimplemented it in Python but I
would like to create a D implementation.
The catch is that each of the above two routines relies on a
library or module that implements the Kuhn-Munkres assignment
algorithm (https://en.wikipedia.org/wiki/Hungarian_algorithm).
Both the Perl and Python implementations are based on the the
following (likely more general version the algorithm—I believe
one that handles rectangular matrices)
http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html
I did a quick search to find out whether there already exists a D
library that implements this routine. I did not find any
library satisfying this requirement. So, it is likely that I
would have to write it myself. My assumption is that it won't be
very complicated, but for the most efficient implementation I
would probably need to use the one of the D libraries that do
NumPy style, efficient computation over matrices. OR, I could
find a implementation in C and create a binding for it in D. I
am not sure what is the easiest and least effort path that would
ensure an accurate and optimal (in terms of speed) solution.
I have a feeling that someone one on this forum might have more
information that could shed some more light on the best path to
take.
--
Sameer
More information about the Digitalmars-d
mailing list