-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Munkres' assignment algorithm (hungarian method)
--   
--   The Munkres algorithm solves the weighted minimum matching problem in
--   a complete bipartite graph, in O(n^3) time. This problem is often
--   called the 'assignment problem'. See eg.
--   <a>http://en.wikipedia.org/wiki/Hungarian_algorithm</a>.
@package Munkres
@version 0.1


-- | The Munkres version of the Hungarian Method for weighted minimal
--   bipartite matching. The implementation is based on Robert A. Pilgrim's
--   notes, <a>http://216.249.163.93/bob.pilgrim/445/munkres.html</a>
--   (mirror:
--   <a>http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html</a>).
module Data.Algorithm.Munkres

-- | Needs a rectangular array of <i>nonnegative</i> weights, which encode
--   the weights on the edges of a (complete) bipartitate graph. The
--   indexing should start from <tt>(1,1)</tt>. 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
--   <tt>Unboxed</tt> type class, and thus the contexts <tt>IArray UArray
--   e</tt> and <tt>MArray (STUArray s) e (ST s)</tt> do not know about
--   each other. (And I have problems with the <tt>forall s</tt> part,
--   too).
hungarianMethodInt :: UArray (Int, Int) Int -> ([(Int, Int)], Int)
hungarianMethodFloat :: UArray (Int, Int) Float -> ([(Int, Int)], Float)
hungarianMethodDouble :: UArray (Int, Int) Double -> ([(Int, Int)], Double)

-- | The same as 'hungarianMethod&lt;Type&gt;', but uses boxed values (thus
--   works with any data type which an instance of <a>Real</a>). The usage
--   of one the unboxed versions is recommended where possible, for
--   performance reasons.
hungarianMethodBoxed :: (Real e, IArray a e) => a (Int, Int) e -> ([(Int, Int)], e)