How to write an MST algorithm (Prim or Kruskal) in Haskell?

Question

I can write Prim and Kruskal algorithms to find the minimum spanning tree in C ++ or Java, but I want to know how to implement them in Haskell with O (mlogm) or O (mlogn) (functional programs work best), Thank you very much .

Answer 1

As svenningsson suggests, the priority search queue works well for both Kruskal and Prim (at least the author proclaims this in his paper .) The problem with Kruskal is that it requires you to have O (log n ) join-search algorithm . The structural structure of the association with a purely functional interface is described here, but it uses a volatile state within the country, and a purely functional implementation may not be possible, and in fact there are several problems when an effective purely functional solution is unknown, as discussed in this relevant SO issue .

An unclean alternative is to implement the union-find algorithm in ST monad. A search in Hackage discovers that the equivalence package meets our needs. The following is an implementation of Kruskal using Data.Equivalence.Monad from the equivalence package:

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 uv if eq then return False else equate uv >> return True 

It can be used as follows:

 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 

and current testing gives:

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

It should be noted that the runtime depends on the weight performed in O (1), however fromL creates a weight function executed in O (log (n)), this can be improved to O (1) using arrays or just tracking the weight in the list input, but this is not part of the algorithm.

Answer 2

Here is a rough implementation of Kruskal.

 import Data.List(sort) import Data.Set (Set, member, fromList, insert, union) data Edge a = Edge aa 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 pq _) = 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 fs (list, setp, setq) = let list' = if member ps || member qs then list else s:list setp' = if member ps then Just s else setp setq' = if member qs then Just s else setq in (list', setp', setq') 

The first step is sorting the edges, which is O (n log n). The problem is to find a faster search for vertex sets in the extract function. I could not find a faster solution for this, maybe someone has an idea ...

[Update]

To implement Scala, I used a map-like data structure for (hopefully) better performance, but unfortunately it uses mutable sets, and I don't know how to translate this into Haskell. The code is on my blog (sorry, the description is in German): http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Answer 3

I think the priority search queue is what you are looking for. It can be optimally implemented in a functional language, as Ralph Hinze showed in the document . Paper seems to be available only through the acm library for the price.