Hi everyone Initially, I hope that this list is active yet. For some days, I had been trying to do a Depth First Search on a graph from scratch following something very didactical (clear, elegant - legible, any worry about efficiency).The code is naive and well documented and is here: https://github.com/claudiosa/CCS/blob/master/haskell/dfs_graph.hs (excessively commented) but unfortunately, it is not working. My guess is that the problem starts on new_node function. I am not sure if in DFS, when a current node gets a next neighbour to stack, it gets all the neighbours. In this code, it is getting one node per time. The functions next_node and one_node seem very non-sense. Could someone help me? Thanks in advance claudio ********************************************************************** Whatsapp: <a href="tel:%2B55%2047%2092451825" value="+554792451825" target="_blank">+55 47 992451825 https://claudiocesar.wordpress.com/ (my links HERE) *********************************************************************** _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Hi Claudio, I had a look at the code, and it looks that in dfs_search function, where the comment says that "BACTRACKING is happening HERE" there is something wrong (it looks neighbours are not all considered, because as you said next_node returns only one neighbour). I think that the definition of dfs_search (x:xs) l_closed is wrong. I'd start to write it from the beginning, instead of correcting this code. Cheers, Ut Il giorno mer 21 ott 2020 alle ore 00:37 Claudio Cesar de Sa <[hidden email]> ha scritto:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Hi Claudio, this is a code for the DFS search. It assumes the graph is represented, as in your code, as an edge list. And, as in your code, the output is a path from a start_node to a finale_node (if it exists). dfs_search :: Int -> Int -> [(Int,Int)]-> [Int] dfs_search sn fn graph = dfs_search_aux sn fn graph [sn] [sn] dfs_search_aux :: Int -> Int -> [(Int,Int)] -> [Int] -> [Int] -> [Int] dfs_search_aux sn fn graph visited path |sn==fn = path |not (isNothing neighbour) = dfs_search_aux x fn graph (x:visited) (path++[x]) |has_length_1 path = error "NO SOLUTION" |otherwise = dfs_search_aux (last new_path) fn graph visited new_path where neighbour=not_visited_neighbour sn visited graph x = fromJust neighbour new_path= init path not_visited_neighbour :: Int -> [Int] -> [(Int,Int)] -> Maybe Int not_visited_neighbour _ _ [] = Nothing not_visited_neighbour x visited ((a,b):xs) | (x == a) && not (elem b visited) = Just b | (x == b) && not (elem a visited) = Just a | otherwise = not_visited_neighbour x visited xs has_length_1 :: [Int]->Bool has_length_1 [] = False has_length_1 (x:xs) = xs==[] Cheers, Ut Il giorno mer 21 ott 2020 alle ore 08:52 Ut Primum <[hidden email]> ha scritto:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Free forum by Nabble | Edit this page |