Munkres-0.1: Munkres' assignment algorithm (hungarian method)



The Munkres version of the Hungarian Method for weighted minimal bipartite matching. The implementation is based on Robert A. Pilgrim's notes, (mirror:



hungarianMethodInt :: UArray (Int, Int) Int -> ([(Int, Int)], Int)Source

Needs a rectangular array of nonnegative weights, which encode the weights on the edges of a (complete) bipartitate graph. The indexing should start from (1,1). Returns a minimal matching, and the cost of it.

Unfortunately, GHC is opposing hard the polymorphicity of this function. I think the main reasons for that is that the there is no Unboxed type class, and thus the contexts IArray UArray e and MArray (STUArray s) e (ST s) do not know about each other. (And I have problems with the forall s part, too).

hungarianMethodBoxed :: (Real e, IArray a e) => a (Int, Int) e -> ([(Int, Int)], e)Source

The same as 'hungarianMethod<Type>', but uses boxed values (thus works with any data type which an instance of Real). The usage of one the unboxed versions is recommended where possible, for performance reasons.