Problem 81

Write a function that, given two nodes a graph, returns all the acyclic paths between the two nodes.

Example

paths : (Graph a) a a -> List (List a)

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

paths g81 'k' 'b' == [['k', 'f', 'c', 'b'], ['k', 'f', 'b']]

Unit Test

import Html
import List
import Set

-- Nodes of a graph must be of type comparable because we define 
type alias Edge comparable = (comparable, comparable)
type alias AdjList comparable = (List((comparable, List comparable)))
type alias Graph comparable = (List comparable, List (Edge comparable))


-- Given two nodes a graph, return all acyclic paths in the graph between the two nodes
findPaths : comparable -> comparable -> Graph comparable -> List (List comparable)
findPaths start goal graph = 
    -- your implemenation goes here
    []


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)
      [ List.sort (findPaths 'c' 'b' graph80) == [['c','b'],['c','f','b']]
      , List.sort (findPaths 'k' 'c' graph80) == [['k','f', 'b', 'c'],['k','f', 'c']]
      , List.sort (findPaths 'x' 'y' graph80) == []
      , List.sort (findPaths 'c' 'y' graph80) == []
      , List.sort (findPaths 'y' 'c' graph80) == []
      , List.sort (findPaths 'f' 'h' graph80b) == [ ['f', 'b', 'g', 'h']
                                                  , ['f', 'c', 'b', 'g', 'h']
                                                  , ['f', 'g', 'h']
                                                  ]
      ]


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

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

Solution

Solution