Kuhn-Munkres Algorithm (a.k.a. The Hungarian Algorithm)

[drug]

On 2/19/21 11:53 PM, Sameer Pradhan wrote:
> 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
> 

As I understand all you need for efficient Hungarian algorithm 
implementation is a contiguous 2D array, not jagged one like built-in 2D 
array in D. All other operations (like conditional modification of a 
matrix element) are too trivial/specific to be highly optimized in 3rd 
party libraries (in contrast to finding the inverse of a matrix, for 
example). Also an operation like row modification should be well 
optimized by a compiler (ldc/gdc first of all). I would just take 
mir.ndslice to get a contiguous dynamic 2D array and implement the 
algorithm like in example you mentioned above. Or if your matrix has 
fixed size you can use gfm.math.Matrix for contiguous static arrays. gfm 
is less advanced than Mir because intended for 3D games first of all, 
but it can be much easier to use. Also gfm has only dependencies.