www.jammni.de

module Prim (
   prim,
   Edge(..)
) where

import Data.List(sort, deleteBy)
import Data.Set(member, empty, insert, singleton, Set)

data Edge a = Edge a a Double deriving (Eq, Show)

instance Ord a => Ord (Edge a) where
   compare (Edge a b c) (Edge d e f) = 
      (c, min a b, max a b) `compare` (f, min d e, max d e)

prim [] = []
prim edges = loop (sort edges) [] startSet where
   startSet = singleton (startNode edges)
   startNode ((Edge node _ _):_) = node 

loop [] solution _ = solution
loop edges solution vertices = 
   let (e,x) = findNextEdge edges vertices
       vertices\' = x `insert` vertices
       cyclicEdge (Edge a b _) = a `member` vertices\' && 
                                 b `member` vertices\' 
       edges\' = filter (not.cyclicEdge) edges 
   in loop edges\' (e:solution) vertices\'   

findNextEdge [] vs = error (\"Disjunct graph with island \" ++ show vs)                               
findNextEdge (e@(Edge a b _):edges) vertices 
    | a `member` vertices = (e,b)
    | b `member` vertices = (e,a)
    | otherwise = findNextEdge edges vertices