Munkres-simple (empty) → 0.1.0.0

raw patch · 4 files changed

+131/−0 lines, 4 filesdep +Munkresdep +arraydep +basesetup-changed

Dependencies added: Munkres, array, base, bimap, containers

Files

• LICENSE +30/−0
• Munkres-simple.cabal +26/−0
• Setup.hs +2/−0
• src/Data/Algorithm/Munkres/Simple.hs +73/−0

@@ -0,0 +1,30 @@+Copyright (c) 2014, Josh Kirklin++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Josh Kirklin nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,26 @@+name:                Munkres-simple+version:             0.1.0.0+synopsis:            Simple and typesafe layer over the Munkres package.+-- description:         +license:             BSD3+license-file:        LICENSE+author:              Josh Kirklin+maintainer:          jjvk2@cam.ac.uk+-- copyright:           +category:            Algorithms+build-type:          Simple+cabal-version:       >=1.10++library+  exposed-modules:     Data.Algorithm.Munkres.Simple++  build-depends:       base >=4.2 && <6.0, +                       containers >=0.4 && <6.0, +                       bimap >=0.2 && <0.3, +                       array, +                       Munkres >=0.1+  +  hs-source-dirs:      src+  +  default-language:    Haskell2010+  

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,73 @@+-- | A simple and typesafe layer over "Data.Algorithm.Munkres".++module Data.Algorithm.Munkres.Simple (+    -- * Problems+    Problem, +    problem, +    -- * Solutions+    Solution, associatedA, associatedB, associationList)+    where++import qualified Data.Set as S (Set, size, toAscList)+import qualified Data.Bimap as B (Bimap, lookup, lookupR, toList, fromList)+import qualified Data.Array.IArray as IA (array)++import Data.Algorithm.Munkres (hungarianMethodDouble)++-- | An association problem, consisting of two sets of items, and a weight function between them. Construct with 'problem'.++data Problem a b = Problem {+    setA :: S.Set a+  , setB :: S.Set b+  , weightFunction :: a -> b -> Double+}++-- | Constructs an association problem, checking whether the sets of objects are the same size first.++problem :: (Ord a, Ord b) => S.Set a -> S.Set b +                          -> (a -> b -> Double) +                          -> Problem a b+problem as bs df = +    if (S.size as) == (S.size bs) +        then Problem as bs df +        else error "Sets are of different size"++-- | The solution of an association problem.++data Solution a b = Solution {+    solutionBimap :: B.Bimap a b+  , solutionCost :: Double+}++-- | Solve an association problem.++solve :: (Ord a, Ord b) => Problem a b -> Solution a b+solve p = Solution solution cost+  where+    solution = B.fromList $ +        map (\(m,n) -> (snd $ as !! (m-1), snd $ bs !! (n-1))) intSolution++    (intSolution, cost) = hungarianMethodDouble +        $ IA.array ((1,1), (numA, numB)) assocs++    numA = S.size . setA $ p+    numB = S.size . setB $ p+    as = zip [1..] (S.toAscList . setA $ p)+    bs = zip [1..] (S.toAscList . setB $ p)+    +    assocs = [((m,n), weightFunction p a b) | (m,a) <- as, (n, b) <- bs]++-- | In a solution of type @Solution a b@, finds the a that a given b is paired with. Returns nothing if the given b was not a part of the initial problem.++associatedA :: (Ord a, Ord b) => Solution a b -> b -> Maybe a+associatedA s b = B.lookupR b . solutionBimap $ s++-- | In a solution of type @Solution a b@, finds the b that a given a is paired with. Returns nothing if the given a was not a part of the initial problem.++associatedB :: (Ord a, Ord b) => Solution a b -> a -> Maybe b+associatedB s a = B.lookup a . solutionBimap $ s++-- | A list of the pairs of items in a solution.++associationList :: Solution a b -> [(a,b)]+associationList = B.toList . solutionBimap