Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Doing a DFS from scratch .... (Claudio Cesar de Sa) 2. Re: Doing a DFS from scratch .... (Ut Primum) ---------------------------------------------------------------------- Message: 1 Date: Tue, 20 Oct 2020 19:36:08 -0300 From: Claudio Cesar de Sa <ccs1...@gmail.com> To: beginners@haskell.org Subject: [Haskell-beginners] Doing a DFS from scratch .... Message-ID: <cahqhj4pr2xn+g833lix3uxmd29ueqqs0+pwgnpzowvs5ku1...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" 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/ **************************************************************** ************* -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.haskell.org/pipermail/beginners/attachments/20201020/7f91e8c5/attachment-0001.html> ------------------------------ Message: 2 Date: Wed, 21 Oct 2020 08:52:54 +0200 From: Ut Primum <utpri...@gmail.com> To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <beginners@haskell.org> Subject: Re: [Haskell-beginners] Doing a DFS from scratch .... Message-ID: <CANjDmKJw6d8brSqG-hVqw6yrkVfCOoGwNnOBZhC=6hobxl1...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" 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> <#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2> Il giorno mer 21 ott 2020 alle ore 00:37 Claudio Cesar de Sa < ccs1...@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@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/20201021/c7da8251/attachment-0001.html> ------------------------------ Subject: Digest Footer _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners ------------------------------ End of Beginners Digest, Vol 147, Issue 1 *****************************************