Doing a DFS from scratch ....

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Doing a DFS from scratch ....

Claudio Cesar de Sa
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: <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
Reply | Threaded
Open this post in threaded view
|

Re: Doing a DFS from scratch ....

Ut Primum
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

Mail priva di virus. www.avg.com

Il giorno mer 21 ott 2020 alle ore 00:37 Claudio Cesar de Sa <[hidden email]> 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: <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

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: 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

Mail priva di virus. www.avg.com

Il giorno mer 21 ott 2020 alle ore 08:52 Ut Primum <[hidden email]> 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

Mail priva di virus. www.avg.com

Il giorno mer 21 ott 2020 alle ore 00:37 Claudio Cesar de Sa <[hidden email]> 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: <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

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners