Comment puis-je écrire un algorithme de MST (Prim ou Kruskal) dans Haskell?

Question

Je peux écrire à la fois les algorithmes de Prim et Kruskal pour trouver un arbre couvrant minimal en C ++ ou Java, mais je veux savoir comment les mettre en œuvre en Haskell avec O (mlogm) ou O (mlogn) (purs programmes fonctionnels est mieux) . Merci beaucoup.

Answer 1

Svenningsson suggère, file d'attente de recherche prioritaire est bien adapté pour les Kruskal et Prim de (atleast l'auteur proclame dans son papier .) Le problème avec Kruskal est qu'il exige que vous avez un O (log n) union-find algorithme . Une structure de données FIND union avec une interface purement fonctionnelle est décrit , mais utilise l'état mutable en interne, et une mise en œuvre purement fonctionnelle pourrait être impossible et en fait, il y a plusieurs problèmes où on ne connaît pas une solution purement fonctionnelle efficace, comme indiqué dans ce lié question SO.

A alterenative non-pure est de mettre en œuvre l'algorithme FIND syndical dans la monade ST. Une recherche sur Hackage trouve que le paquet équivalence convient à nos besoins. Ce qui suit est une implémentation de Kruskal utilisant Data.Equivalence.Monad du paquet équivalence :

import Data.Equivalence.Monad
import Data.Graph as G
import Data.List(sortBy)
import Data.Map as M
import Control.Monad(filterM)
import Data.Ord(comparing)

run = runEquivM (const ()) (const $ const ())

kruskal weight graph = run $
 filterM go (sortBy (comparing weight) theEdges)
     where
      theEdges = G.edges graph
      go (u,v) = do 
        eq <- equivalent u v
        if eq then return False else
         equate u v >> return True

Il peut être utilisé comme ceci:

fromL xs = fromJust . flip M.lookup (M.fromList xs)

testWeights = fromL [((1,2),1),((2,3),4),((3,4),5),((1,4),30),((1,3),4)]
testGraph = G.buildG  (1,4) [(1,2),(2,3),(3,4),(1,4),(1,3)]
test = kruskal testWeights testGraph

et le test en cours d'exécution donne:

[(1,2),(1,3),(3,4)]

Il convient de noter que le temps d'exécution dépend de poids en cours d'exécution en O (1) le temps, mais fromL crée une fonction de poids en cours d'exécution en O (log (n)), cela peut être amélioré à O (1) temps en utilisant des tableaux ou tout simplement garder une trace du poids dans la liste d'entrée, mais ce n'est pas vraiment partie de l'algorithme.

Answer 2

Voici une mise en œuvre Kruskal brut.

import Data.List(sort)
import Data.Set (Set, member, fromList, insert, union)

data Edge a = Edge a a Double deriving Show

instance (Eq a) => Eq (Edge a) where
  Edge x1 y1 z1 == Edge x2 y2 z2 = x1 == x2 && y1 == y2 && z1 == z2

instance Eq a => Ord (Edge a) where
  (Edge _ _ x) `compare` (Edge _ _ y) = x `compare` y

kruskal :: Ord a => [Edge a] -> [Edge a]
kruskal = fst . foldl mst ([],[]) . sort

mst :: Ord a => ([Edge a],[Set a]) -> Edge a -> ([Edge a],[Set a])
mst (es, sets) e@(Edge p q _) = step $ extract sets where
   step (rest, Nothing, Nothing) = (e : es, fromList [p,q] : rest)
   step (rest, Just ps, Nothing) = (e : es, q `insert` ps : rest)
   step (rest, Nothing, Just qs) = (e : es, p `insert` qs : rest)
   step (rest, Just ps, Just qs) | ps == qs = (es, sets) --circle
                                 | otherwise = (e : es, ps `union` qs : rest)
   extract = foldr f ([], Nothing, Nothing) where
       f s (list, setp, setq) =
            let list' = if member p s || member q s then list else s:list
                setp' = if member p s then Just s else setp
                setq' = if member q s then Just s else setq
            in (list', setp', setq') 

La première étape consiste à trier les bords, ce qui est O (n log n). Le problème est de trouver une recherche plus rapide pour les ensembles de sommets dans la fonction d'extraction. Je ne pouvais pas trouver une solution plus rapide pour cela, peut-être quelqu'un a une idée ...

[Mise à jour]

Pour une implémentation Scala j'ai utilisé une carte comme structure de données pour (espérons-le) de meilleures performances, mais malheureusement, il utilise des ensembles mutables, et je n'ai pas la moindre idée comment traduire en Haskell. Le code est dans mon blog (désolé, la description est en allemand): http: / /dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Answer 3

Je pense que une file d'attente de recherche prioritaire est ce que vous cherchez. Il peut être mis en œuvre de manière optimale dans un langage fonctionnel tel que démontré par Ralf Hinze un document . Il semble que le papier est disponible uniquement via la bibliothèque de acm à un coût.