Come faccio a scrivere un algoritmo MST (Prim o Kruskal) in Haskell?

Question

posso scrivere entrambi gli algoritmi di Kruskal di Prim e per trovare un minimo spanning tree in C ++ o Java, ma io voglio sapere come realizzarle in Haskell con O (mlogm) o O (mlogn) (programmi funzionali puro è meglio) . Grazie mille.

Answer 1

Come suggerisce Svenningsson, coda di ricerca di priorità è adatto sia per Kruskal e Prim di (almeno i proclama autore nella sua carta .) Il problema di Kruskal è che richiede che si dispone di un O (log n) union-find algoritmo . Un datastructure union-find con un'interfaccia puramente funzionale è descritto qui , ma utilizza stato mutabile internamente e un'implementazione puramente funzionale potrebbe essere impossibile e infatti, ci sono diversi problemi dove una soluzione puramente funzionale efficace non è nota, come discusso in questo relativa domanda SO.

A alterenative non pura è quella di implementare l'algoritmo union-find in monade ST. Una ricerca su Hackage ritiene che la href="http://hackage.haskell.org/package/equivalence" rel="nofollow noreferrer"> equivalenza pacchetto si adatta alle nostre esigenze. Di seguito è un'implementazione di Kruskal utilizzando Data.Equivalence.Monad dal href="http://hackage.haskell.org/package/equivalence" rel="nofollow noreferrer"> equivalenza pacchetto :

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

Può essere utilizzato in questo modo:

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

e il test in esecuzione dà:

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

Si deve notare che il tempo di esecuzione dipende pesi esecuzione in O (1) tempo, tuttavia fromL crea una funzione peso esecuzione in O (log (n)), questo può essere migliorato a O (1) tempo mediante matrici o semplicemente tenere traccia del peso nella lista di input, ma non è realmente parte dell'algoritmo.

Answer 2

Ecco un'implementazione grezza Kruskal.

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') 

Il primo passo è l'ordinamento dei bordi, che è O (n log n). Il problema è quello di trovare una rapida ricerca per i set di vertici nella funzione di estratto. Non riuscivo a trovare una soluzione più veloce per questo, forse qualcuno ha un'idea ...

[Aggiornamento]

Per un'implementazione Scala ho usato una mappa-come struttura di dati per (si spera) migliore prestazione, ma purtroppo utilizza set mutevoli, e non ho idea di come tradurre questo in Haskell. Il codice è nel mio blog (mi dispiace, descrizione è in tedesco): http: / /dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Answer 3

Penso che una coda di ricerca prioritario è quello che stai cercando. Può essere implementato in modo ottimale in un linguaggio funzionale come dimostrato da Ralf Hinze in un documento . Sembra che la carta è disponibile solo tramite la biblioteca di ACM ad un costo.