Problem 88 Solution

{-| Given a graph, return connected subsets of nodes.
-}
connected : Graph comparable -> List (List comparable)
connected (nodes, edges) =
    case nodes of
        [] ->
            []

        n::ns ->
            let 
                subNodes = depthFirst n (nodes, edges)
            in
                subNodes :: connected ((diff nodes subNodes), edges)   


{-| return the set of elements of a list not found in another list 
-}
diff : List comparable -> List comparable -> List comparable
diff minuend subtraend =
    Set.toList <| Set.diff (Set.fromList minuend) (Set.fromList subtraend)


{-| Given a graph and a starting node, return all nodes in depth-first order.
-}
depthFirst : comparable -> Graph comparable -> List comparable
depthFirst start (nodes, edges) =
    List.reverse (depthFirst_ [start] [] (nodes, edges))


{-| Helper function for depthFirst that recordes visited nodes to avoid
    cyclic paths.
-}
depthFirst_ : List comparable -> List comparable -> Graph comparable -> List comparable
depthFirst_ unvisited visited ( nodes, edges ) =
    case unvisited of
        [] ->
            visited

        u::us ->
            let
                nextNodes = unique
                    <| List.map (Tuple.second)
                    <| (++) (List.filter (\( a, b ) -> a == u) edges)
                    <| List.map (\x -> ( Tuple.second x, Tuple.first x ))
                    <| List.filter (\( a, b ) -> b == u) edges

                newNodes = List.sort
                    <| List.filter (\x -> not (List.member x (u::visited))) nextNodes
            in
                depthFirst_ (remove u (newNodes ++ unvisited)) (u::visited) (nodes, edges)


remove : a -> List a -> List a
remove x =
  List.filter ((/=) x)


{-| Given a list, return all unique values in the list.
-}
unique : List comparable -> List comparable
unique list =
    Set.toList <| Set.fromList list

Back to problem