CODEWITHSUNDEEP
haskellbreadth-first-search
Kochev
Kochev

Reputation: 35

Breadth-first search on Haskell

Graph defined so: [("1",["2","3"]),("2",["1"]),("3",["1"])]

I want to write a breadth-first search.

Here is my code:

search_command graph start ""=(graph,"You didnt enter start vertex!\n")
search_command graph ""  end=(graph,"You didnt enter end vertex!\n")
search_command graph start end=
    if (has_element graph start)&&(has_element graph end) then 
            (graph,unwords (search graph [start] end [] []))
    else if (has_element graph end)==False then 
            (graph,"Element with "++end++" name not found!")
    else 
            (graph,"Element with "++start++" name not found!")


search [] _ _ [] result=result 
search (item:graph) (x:start) end use result=
    if (fst item==x)&&(elem x use)==False then
            search graph (get_connect_vertices graph graph (fst item) []) end (use++[x]) (result++[x])
    else if (fst item==end)&&(fst item==x) then
            search [] [] "" [] (result++[x]++[end])
    else
            search graph [x] end use (result)

But when i run it, i get exeption: Exception: D:\Workspace\Labwork2\src\Main.hs:(190,1)-(197,49): Non-exhaustive patterns in function search

What is my mistake?How to implement breadth-first search if the graph is given as I have?

Upvotes: 0

Views: 1459

Answers (2)

muhmuhten
muhmuhten

Reputation: 3341

As the exception suggests, your patterns are non-exhaustive. Specifically, you have the following patterns for search:

search []    _     _ [] _
search (_:_) (_:_) _ _  _

If the first argument is nil, the fourth must also be, and if the first argument is not nil, the second likewise must be not nil. The following cases are not covered:

search [] _ _ (_:_) _
search (_:_) [] _ _ _

You must either enforce an invariant to ensure that these cases never occur, or you should do something reasonable with them.

Running your program through -Wall should help you catch non-totality problems such as these.

(As for breadth-first searching: in Haskell, if you write a correct graph search where toplevel results don't depend on lower-level results, and you don't demand strictness, then whether it turns out breadth-first or depth-first or somewhere in between generally depends on how the result is used.)

(This is unrelated, but is having a vertex identified by the empty string really a problem? What if your graph had a vertex actually identified by the empty string? Is there an invariant which states that this is never the case?)

Upvotes: 5

seanmcl
seanmcl

Reputation: 9946

You don't have a case for 

search [item] [] _ _ _

Clearly your program is hitting this case. Do you have an invariant stating that if the graph is empty then the start symbols are exhausted?

Upvotes: 3

Related Questions