 | Munkres-0.1: Munkres' assignment algorithm (hungarian method) | Contents | Index |
|
|
|
| Description |
| The Munkres version of the Hungarian Method for weighted minimal
bipartite matching.
The implementation is based on Robert A. Pilgrim's notes,
http://216.249.163.93/bob.pilgrim/445/munkres.html
(mirror: http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html).
|
|
| Synopsis |
|
| hungarianMethodInt :: UArray (Int, Int) Int -> ([(Int, Int)], Int) | | | hungarianMethodFloat :: UArray (Int, Int) Float -> ([(Int, Int)], Float) | | | hungarianMethodDouble :: UArray (Int, Int) Double -> ([(Int, Int)], Double) | | | hungarianMethodBoxed :: (Real e, IArray a e) => a (Int, Int) e -> ([(Int, Int)], e) |
|
|
| Documentation |
|
| hungarianMethodInt :: UArray (Int, Int) Int -> ([(Int, Int)], Int) |
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).
|
|
| hungarianMethodFloat :: UArray (Int, Int) Float -> ([(Int, Int)], Float) |
|
| hungarianMethodDouble :: UArray (Int, Int) Double -> ([(Int, Int)], Double) |
|
| hungarianMethodBoxed :: (Real e, IArray a e) => a (Int, Int) e -> ([(Int, Int)], e) |
| 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.
|
|
| Produced by Haddock version 2.4.1 |