Thank you David.I really liked the idea

let vsx = dfs' g x (x : vis) in dfs' g v vsx I am trying to grasp it. I wrote the stack based dfs which seems to work.

import Data.List import Data.Array import Control.Monad type Node = Int type Graph = Array Int [ Node ] 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 -> [ Node ] -> [ Node ] -> [ Node ] dfsSearch _ [] vis = vis dfsSearch g ( top : stack ) vis | elem top vis = dfsSearch g stack vis | otherwise = dfsSearch g ( ( g ! top ) ++ stack ) ( top : vis ) ghci>let g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , (0 , 4 ) ] False ghci>dfsSearch g [0] [] [1,2,3,4,0] ghci>let g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , (0 , 4 ) ] True ghci>dfsSearch g [0] [] [1,2,3,4,0] ghci>dfsSearch g [1] [] [1] ghci>dfsSearch g [2] [] [2] 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>let g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 3 , 4 ) , (4 , 5 ) ] False ghci>g array (0,5) [(0,[2,1]),(1,[0]),(2,[0]),(3,[4]),(4,[5,3]),(5,[4])] ghci>dfsSearch g [0] [] [1,2,0] ghci>dfsSearch g [1] [] [2,0,1] ghci>dfsSearch g [2] [] [1,0,2] ghci>dfsSearch g [3] [] [5,4,3] ghci>dfsSearch g [4] [] [3,5,4] In this dfs , I am returning list of elements in visited in last to first order. Regards Mukesh Tiwari On Nov 9, 5:08 am, David Barbour wrote:

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 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-C...@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe