[Haskell-cafe] Depth first search

[David Barbour]

Major error is in the line of code: `| otherwise =  dfs' g y ( v : vis )`

You need something closer to:
   let vsx = dfs' g x (x : vis) in
   dfs' g v vsx

That is, first visit everything you can reach from x, then backtrack to add
anything else you can reach from v. This implementation will forget which
nodes you've already visited from v, though that might not be a big issue.
If you want to fix it, separate the `list = g ! v` into the caller, rather
than the callee, such that there are two lists at `dfs'` - a to-visit list
and a visited list.

This fixes a few minor errors (you did not define y, and you added `v` to
the visitors list).

Also, fix dfsSearch:
  dfsSearch g v = reverse $ dfs' g v [v]

That is, add the node you're starting with to those you've already visited,
and since you're adding to the front of the list the element visited last,
you may wish to fix that.

Order in this case is [0,4,3,2,1] due to the order from buildGraph.


On Tue, Nov 8, 2011 at 1:04 PM, mukesh tiwari
<mukeshtiwari.iiitm at gmail.com>wrote:

> Hello all
> I am trying to implement depth search in Haskell.  My issue here is kind
> of backtracking.  Haskell code for depth first search
>
> import Data.List
> import Data.Array
> import Control.Monad
>
>
> type Node = Int
> type Graph = Array Int [  Node  ]
>
> dfs' ::  Graph -> Node -> [ Node ] -> [ Node ]
> dfs' g v vis = dfsfun lst where
> lst = g ! v
> dfsfun [] = vis
> dfsfun ( x : xs )
>   | elem x vis = dfsfun xs
>   | otherwise =  dfs' g y ( v : vis )
>
> --set the flag true if the graph is direct otherwise false
> buildGraph :: ( Int , Int ) -> [ ( Node , Node ) ] -> Bool ->  Graph
> buildGraph bnds xs f
>  | f =  accumArray ( flip (:) ) []  bnds xs  --direct graph a->b
>  | otherwise = accumArray ( flip (:) ) []  bnds xss where   --indirect a
> -> b and b -> a
> xss =  foldr ( \ ( x , y ) b -> ( y , x ) : b ) xs xs
>
> dfsSearch :: Graph -> Int -> [ Node ]
> dfsSearch g v = dfs' g v []
>
> Lets create a indirect graph
> ghci>let g = buildGraph  ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , (
> 0 , 4 ) ] False
> ghci>g
> array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])]
>
> ghci>dfsSearch g 0
> [0]
> Here  I am getting only 0 but  it should return [ 0 , 1 , 2 , 3 , 4 ] .
> What is happening here when i am passing  0 as root node to function , at
> first level i get
>  lst = [ 4 , 3, 2, 1 ]  . First element of this list is 4 so 0 is added to
> vis list and now 4 is passed to dfs' as parent. When it goes down , we get
> lst = [0] and since 0 is member of vis list so it returns the vis as result
> .  When we write dfs in c/c++ then it returns to calling function and again
> loops through remaining element which i am not able visualize in Haskell.
>  Could some one please help me how to solve this issue .
>
> Regards
> Mukesh Tiwari
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111108/9caf0dc6/attachment.htm>