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 <dmbarb...@gmail.com> 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 > <mukeshtiwari.ii...@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-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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe