## Project Euler Problem 107 ( Minimum Spanning Tree )

Project Euler Problem 107 is related to minimum spanning tree. Trying to solve some easy problems to cross the 200 mark. This is the first time I have implemented the graph algorithm in Haskell so it was kind of fun. Wrote Prim’s algorithm to calculated the minimum spanning tree. Replaced comma ( , ) in input file by space. See modified input file and total sum of inputs from ideone.

import Data.List import qualified Data.IntMap.Lazy as M import qualified Data.PQueue.Min as PQ import qualified Data.Bits as B buildGraph :: [ ( Int , Int , Int ) ] -> M.IntMap [ ( Int , Int ) ] buildGraph xs = M.fromListWith ( ++ ) . map f_1 $ xs where f_1 ( i , j , val ) = ( i , [ ( val , j ) ] ) visited :: Int -> Integer -> ( Bool , Integer ) visited x vis = ( t == 0 , vis' ) where t = ( B..&. ) ( B.shiftL ( 1 :: Integer ) x ) vis vis' = ( B..|. ) ( B.shiftL ( 1 :: Integer ) x ) vis primAlgorithm :: PQ.MinQueue ( Int , Int ) -> Integer -> Int -> M.IntMap [ ( Int , Int ) ] -> String primAlgorithm queue vis cost m | PQ.null queue = show cost ++ "\n" | t == False = primAlgorithm queue' vis' cost m | otherwise = primAlgorithm queue'' vis' ( cost + c ) m where ( ( c , x ) , queue' ) = PQ.deleteFindMin queue ( t , vis' ) = visited x vis queue'' = PQ.union queue' ( PQ.fromList . ( M.! ) m $ x ) test :: [ ( Int , Int , Int ) ] -> String test xs = primAlgorithm ( PQ.fromList [ ( 0 , 0 ) ] ) 0 0 ( buildGraph xs ) parseInput :: [ ( Int , String ) ] -> [ ( Int , Int ) ] parseInput [] = [] parseInput ( ( k , x ) : xs ) | x == "-" = parseInput xs | otherwise = ( k , readD x ) : parseInput xs where readD :: String -> Int readD = read fun :: Int -> [ [ ( Int , Int ) ] ] -> [ [ ( Int , Int , Int ) ] ] fun _ [] = [] fun k ( x : xs ) = ( map ( \( i , val ) -> ( k , i , val ) ) x ) : fun ( succ k ) xs main = interact $ primAlgorithm ( PQ.fromList [ ( 0 , 0 ) ] ) 0 0 . buildGraph . concat . fun 0 . map ( parseInput . zip [ 0 , 1 .. ] . words ) . lines

Macintosh-0026bb610428:Programming mukesh$ ghc-7.4.1 –make -O2 Prim.hs

[1 of 1] Compiling Main ( Prim.hs, Prim.o )

Linking Prim …

Macintosh-0026bb610428:Programming mukesh$ ./Prim < network.txt

2153

Advertisements

No comments yet.

## Leave a Reply