Problem 87a

Extract nodes from a graph into a list in depth-first order, without repeating any nodes. Search the children of each node in order from lowest to highest.

Example

g87 = ([1,2,3,4,5,6,7], [(1,2),(2,3),(1,4),(3,4),(5,2),(5,4),(6,7)])

depthFirst g87 == [1, 2, 3, 4, 5]

Unit Test

import Html
import List
import Set
import String


type alias Edge comparable =
    ( comparable, comparable )


type alias Graph comparable =
    ( List comparable, List (Edge comparable) )


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


main : Html.Html a
main =
    Html.text
        <| case test of
            0 ->
                "Your implementation passed all tests."

            1 ->
                "Your implementation failed one test."

            x ->
                "Your implementation failed " ++ (toString x) ++ " tests."


test : Int
test =
    List.length
        <| List.filter ((==) False)
            [ String.fromList (depthFirst 'g' graph80) == "gh"
            , String.fromList (depthFirst 'h' graph80) == "hg"
            , String.fromList (depthFirst 'g' graph84) == "gbcfkh"
            , String.fromList (depthFirst 'c' graph84) == "cbfghk"
            , String.fromList (depthFirst 'f' graph84) == "fbcghk"
            , String.fromList (depthFirst 'h' graph84) == "hgbcfk"
            , String.fromList (depthFirst 'k' graph84) == "kfbcgh"
            , String.fromList (depthFirst 'b' graph80) == "bcfk"
            , String.fromList (depthFirst 'c' graph80) == "cbfk"
            , String.fromList (depthFirst 'f' graph80) == "fbck"
            , String.fromList (depthFirst 'k' graph80) == "kfbc"
            , String.fromList (depthFirst 'k' graph80) == "kfbc"
            , String.fromList (depthFirst 'g' graph81) == "gh"
            , String.fromList (depthFirst 'h' graph81) == "hg"
            , String.fromList (depthFirst 'b' graph84) == "bcfghk"
            , String.fromList (depthFirst 'a' graph87) == "abdc"
            ]


graph80 =
    ( [ 'b', 'c', 'd', 'f', 'g', 'h', 'k' ]
    , [ ( 'b', 'c' )
      , ( 'b', 'f' )
      , ( 'c', 'f' )
      , ( 'f', 'k' )
      , ( 'g', 'h' )
      ]
    )


graph81 =
    -- has a loop and parallel edges
    ( [ 'b', 'c', 'd', 'f', 'g', 'h', 'k' ]
    , [ ( 'b', 'c' )
      , ( 'b', 'f' )
      , ( 'c', 'f' )
      , ( 'f', 'k' )
      , ( 'g', 'h' )
      , ( 'g', 'h' )
      , ( 'g', 'g' )
      ]
    )


graph84 =
    ( [ 'b', 'c', 'd', 'f', 'g', 'h', 'k' ]
    , [ ( 'b', 'c' )
      , ( 'b', 'f' )
      , ( 'b', 'g' )
      , ( 'c', 'f' )
      , ( 'f', 'g' )
      , ( 'f', 'k' )
      , ( 'g', 'h' )
      ]
    )


{-| Simple graph, in dfs - "abdc", in bfs "abcd" -}
graph87 =
    ( [ 'a', 'b', 'c', 'd' ]
    , [ ( 'a', 'b' )
      , ( 'a', 'c' )
      , ( 'b', 'd' )
      ]
    )

Hint

1. Track of all nodes you have already visited as you traverse the graph to avoid cyclic paths.

Solution

Solution