¿Cómo puedo escribir un algoritmo MST (Prim o de Kruskal) en Haskell?

Question

Puedo escribir tanto algoritmos de Kruskal de Prim y para encontrar un árbol de expansión mínima en C ++ o Java, pero me gustaría saber cómo ponerlas en práctica en Haskell con O (mlogm) o S (mlogn) (programas funcionales puro es mejor) . Muchas gracias.

Answer 1

Como sugiere Svenningsson, cola de búsqueda prioritaria es muy adecuado para ambas Kruskal de y Prim de (al menos el autor proclama en su papel .) El problema de Kruskal es que requiere que usted tiene una O (log n) unión-algoritmo . Una estructura de datos unión-con una interfaz puramente funcional se describe aquí , pero utiliza el estado mutable internamente, y una aplicación puramente funcional podría ser imposible y, de hecho, hay varios problemas en los que no se conoce una solución puramente funcional eficiente, como se discute en esta pregunta SO relacionado.

A alterenative no puro es implementar algoritmo de unión-en la mónada ST. Una búsqueda en Hackage encuentra que el href="http://hackage.haskell.org/package/equivalence" rel="nofollow noreferrer"> equivalencia paquete equivalencia paquete

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

Puede ser utilizado como esto:

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

y prueba de funcionamiento da:

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

Debe tenerse en cuenta que el tiempo de funcionamiento depende de los pesos que se ejecutan en O (1) tiempo, sin embargo fromL crea una función de ponderación que se ejecuta en tiempo O (log (n)), esto puede ser mejorado a O (1) tiempo utilizando matrices o simplemente no perder de vista el peso en la lista de entrada, pero no es realmente parte del algoritmo.

Answer 2

Esta es una aplicación de Kruskal crudo.

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

El primer paso es la clasificación de los bordes, que es O (n log n). El problema es encontrar una forma más rápida de consulta para los conjuntos de vértices en la función de extracción. No pude encontrar una solución más rápida para esto, tal vez alguien tiene una idea ...

[Actualización]

Para una implementación Scala que utiliza una estructura de datos en forma de mapa para (esperemos) un mejor rendimiento, pero por desgracia, utiliza conjuntos mutables, y no tengo ni idea de cómo traducir esto en Haskell. El código está en mi blog (lo siento, descripción está en alemán): http: / /dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Answer 3

creo una cola de prioridad de búsqueda es lo que estás buscando. Se puede implementar de manera óptima en un lenguaje funcional como se demuestra por Ralf Hinze en un documento . Parece que el documento sólo está disponible a través de la biblioteca de acm a un costo.