Problem 84 Solution

prim : comparable -> Graph comparable -> Graph comparable
prim start ( nodes, edges ) =
    snd <| findMst ( ( nodes, edges ), ( [ start ], [] ) )


{-| given a SpanningTree, add the lowest weight edge from the left graph
    to the right graph until it includes all nodes
-}
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



{-| Find the first minimum element in a list using a comparable transformation
    (borrowed from List.Extra)
-}
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