Problem 84 Solution
prim : comparable -> Graph comparable -> Graph comparable
prim start ( nodes, edges ) =
snd <| findMst ( ( nodes, edges ), ( [ start ], [] ) )
findMst : SpanningTree comparable -> SpanningTree comparable
findMst ( ( lNodes, lEdges ), ( rNodes, rEdges ) ) =
let
edges =
List.filter (hasOneNodeIn rNodes) lEdges
edge =
minimumBy (\( a, b, w ) -> w) edges
in
case edge of
Nothing ->
( ( lNodes, lEdges ), ( rNodes, rEdges ) )
Just e ->
let
rEdges' =
rEdges ++ [ e ]
rNodes' =
nodesOfEdges rEdges'
lEdges' =
Set.toList <| Set.remove e <| Set.fromList lEdges
in
if List.length lNodes <= List.length rNodes then
( ( lNodes, lEdges ), ( rNodes', rEdges' ) )
else
findMst ( ( lNodes, lEdges' ), ( rNodes', rEdges' ) )
hasOneNodeIn : List comparable -> Edge comparable -> Bool
hasOneNodeIn nodes ( a, b, w ) =
(List.member a nodes && (not (List.member b nodes)))
|| ((not (List.member a nodes)) && List.member b nodes)
nodesOfEdges : List (Edge comparable) -> List comparable
nodesOfEdges edges =
List.sort
<| Set.toList
<| Set.fromList
<| List.concatMap (\( a, b, w ) -> [ a, b ]) edges
minimumBy : (a -> comparable) -> List a -> Maybe a
minimumBy f ls =
let
minBy x ( y, fy ) =
let
fx =
f x
in
if fx < fy then
( x, fx )
else
( y, fy )
in
case ls of
[ l' ] ->
Just l'
l' :: ls' ->
Just <| fst <| List.foldl minBy ( l', f l' ) ls'
_ ->
Nothing
last : List a -> Maybe a
last list =
List.head (List.reverse list)
Back to problem