[prev in list] [next in list] [prev in thread] [next in thread]
List: haskell-beginners
Subject: Re: [Haskell-beginners] Doing a DFS from scratch ....
From: Ut Primum <utprimum () gmail ! com>
Date: 2020-10-24 14:42:30
Message-ID: CANjDmKL-8Dj6k+nMYmBpzqCsVKTYWHr6d5veLK5zB6TrU2p8SA () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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@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@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
> >
>
[Attachment #5 (text/html)]
<div dir="ltr"><div>Hi Claudio,</div><div>this is a code for the DFS search. It \
assumes the graph is represented, as in your code, as an edge list.</div><div>And, as \
in your code, the output is a path from a start_node to a finale_node (if it \
exists).</div><div><br></div>import Data.Maybe<br><br><div>dfs_search :: Int -> \
Int -> [(Int,Int)]-> [Int]<br>dfs_search sn fn graph = dfs_search_aux sn fn \
graph [sn] [sn]<br><br>dfs_search_aux :: Int -> Int -> [(Int,Int)] -> [Int] \
-> [Int] -> [Int]<br>dfs_search_aux sn fn graph visited path<br> |sn==fn \
= path<br> |not (isNothing neighbour) = dfs_search_aux x fn graph (x:visited) \
(path++[x])<br> |has_length_1 path = error "NO \
SOLUTION"<br> |otherwise = dfs_search_aux (last \
new_path) fn graph visited new_path<br> where neighbour=not_visited_neighbour \
sn visited graph<br> x = fromJust neighbour<br> \
new_path= init path<br> <br>not_visited_neighbour :: Int -> [Int] -> \
[(Int,Int)] -> Maybe Int<br>not_visited_neighbour _ _ [] = \
Nothing<br>not_visited_neighbour x visited ((a,b):xs) <br> | (x == a) && \
not (elem b visited) = Just b<br> | (x == b) && not (elem a visited) = \
Just a<br> | otherwise = not_visited_neighbour x visited xs<br><br>has_length_1 \
:: [Int]->Bool<br>has_length_1 [] = False<br>has_length_1 (x:xs) = \
xs==[]<br></div><div><br></div><div>Cheers,</div><div>Ut</div></div><div \
id="DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2"><br> <table style="border-top:1px solid \
#d3d4de"> <tr>
<td style="width:55px;padding-top:18px"><a \
href="http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail" \
target="_blank"><img \
src="https://ipmcdn.avast.com/images/icons/icon-envelope-tick-green-avg-v1.png" \
alt="" width="46" height="29" style="width: 46px; height: 29px;"></a></td> <td \
style="width:470px;padding-top:17px;color:#41424e;font-size:13px;font-family:Arial,Helvetica,sans-serif;line-height:18px">Mail \
priva di virus. <a href="http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail" \
target="_blank" style="color:#4453ea">www.avg.com</a> </td> </tr>
</table>
<a href="#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2" width="1" \
height="1"></a></div><br><div class="gmail_quote"><div dir="ltr" \
class="gmail_attr">Il giorno mer 21 ott 2020 alle ore 08:52 Ut Primum <<a \
href="mailto:utprimum@gmail.com">utprimum@gmail.com</a>> ha \
scritto:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi \
Claudio,<div>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).</div><div>I think that the definition of \
</div><div>dfs_search (x:xs) l_closed</div><div>is wrong. I'd start to write it \
from the beginning, instead of correcting this \
code.</div><div><br></div><div>Cheers,</div><div>Ut</div></div><div \
id="gmail-m_1000941696827786327DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2"><br> <table \
style="border-top:1px solid rgb(211,212,222)"> <tbody><tr>
<td style="width:55px;padding-top:18px"><a \
href="http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail" \
target="_blank"><img \
src="https://ipmcdn.avast.com/images/icons/icon-envelope-tick-green-avg-v1.png" \
alt="" width="46" height="29" style="width: 46px; height: 29px;"></a></td> <td \
style="width:470px;padding-top:17px;color:rgb(65,66,78);font-size:13px;font-family:Arial,Helvetica,sans-serif;line-height:18px">Mail \
priva di virus. <a href="http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail" \
style="color:rgb(68,83,234)" target="_blank">www.avg.com</a> </td> </tr>
</tbody></table>
<a href="#m_1000941696827786327_DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2" width="1" \
height="1"></a></div><br><div class="gmail_quote"><div dir="ltr" \
class="gmail_attr">Il giorno mer 21 ott 2020 alle ore 00:37 Claudio Cesar de Sa \
<<a href="mailto:ccs1664@gmail.com" target="_blank">ccs1664@gmail.com</a>> ha \
scritto:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div \
dir="ltr"><div><div><div>Hi everyone<br><br></div><div>Initially, I hope that this \
list is active yet. For some days, <br></div>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).<br><br></div>This DFS keeps a boolean list to \
mark the nodes already visited and another with current or valid nodes ( the stack of \
DFS classic).<br><br></div><div>The code is naive and well documented and is \
here:<br><br><a href="https://github.com/claudiosa/CCS/blob/master/haskell/dfs_graph.hs" \
target="_blank">https://github.com/claudiosa/CCS/blob/master/haskell/dfs_graph.hs</a><br></div><div>(excessively \
commented)<br></div><div><br></div><div>but unfortunately, it is not working. My \
guess is that the problem starts on <b>new_node</b> function. I am not sure if in \
DFS, when a current node gets a next neighbour to stack, it gets all the neighbours. \
<br></div><div>In this code, it is getting one node per time. <br><br></div><div>The \
functions next_node and one_node seem very non-sense. Could someone help me? \
<br><br></div><div>Thanks in advance<br></div><div><br clear="all"><br><br><div \
dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div \
dir="ltr"><div><div dir="ltr"><div><span></span><span></span>claudio \
<br><br><i>******************************</i><i>******************************</i><i>**********<br></i><div><i>Whatsapp: \
<a href="tel:%2B55%2047%2092451825" value="+554792451825" target="_blank">+55 47 \
992451825</a><br></i><a href="https://claudiocesar.wordpress.com/" \
target="_blank">https://claudiocesar.wordpress.com/</a> (my links \
HERE)</div><div><cite><a href="https://github.com/claudiosa" \
style="font-style:italic" \
target="_blank">https://github.com/claudiosa</a><br></cite></div><div><a \
href="https://www.udemy.com/picat-uma-linguagem-de-programacao-multiparadigma/" \
target="_blank">https://www.udemy.com/picat-uma-linguagem-de-programacao-multiparadigm \
a/</a><br></div><div><i>******************************</i><i>************************* \
*****</i><i>***********</i></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" \
target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br> \
</blockquote></div> </blockquote></div>
[Attachment #6 (text/plain)]
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic