[Haskell-beginners] Doing a DFS from scratch ....

[Ut Primum]

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).

import Data.Maybe

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

<http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
Mail
priva di virus. www.avg.com
<http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
<#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>

Il giorno mer 21 ott 2020 alle ore 08:52 Ut Primum <utprimum at gmail.com> ha
scritto:

> 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
>
>
> <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail> Mail
> priva di virus. www.avg.com
> <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
> <#m_1000941696827786327_DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
>
> Il giorno mer 21 ott 2020 alle ore 00:37 Claudio Cesar de Sa <
> ccs1664 at gmail.com> ha scritto:
>
>> 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).
>>
>> This DFS keeps a boolean list to mark the nodes already visited and
>> another with current or valid nodes ( the stack of DFS classic).
>>
>> 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: +55 47 992451825 <%2B55%2047%2092451825>*
>> https://claudiocesar.wordpress.com/ (my links HERE)
>> https://github.com/claudiosa
>> https://www.udemy.com/picat-uma-linguagem-de-programacao-multiparadigma/
>> ****************************************************************
>> *************
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20201024/3fd6f7a7/attachment.html>