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

[Sameer Pradhan]

On Saturday, 20 February 2021 at 10:35:27 UTC, drug wrote:
> 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.
>> 


Thanks for your responses. I had one other related question: I 
also found a C-implementation of the algorithm. I have never 
written a Dlang binding for a C library, but since D has binary 
compatibility with a C library/object file, would it be easier to 
write a wrapper for this C library in D? Or there can be some 
gotchas that I need to keep in mind if I take this path?

--
Sameer