# My Weblog

## 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

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 )