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