Re: [Haskell-cafe] Depth first search
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 ) ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , (0 , 4 ) ] False ghcidfsSearch g [0] [] [1,2,3,4,0] ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , (0 , 4 ) ] True ghcidfsSearch g [0] [] [1,2,3,4,0] ghcidfsSearch g [1] [] [1] ghcidfsSearch g [2] [] [2] ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , (0 , 4 ) ] False ghcig array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])] ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 3 , 4 ) , (4 , 5 ) ] False ghcig array (0,5) [(0,[2,1]),(1,[0]),(2,[0]),(3,[4]),(4,[5,3]),(5,[4])] ghcidfsSearch g [0] [] [1,2,0] ghcidfsSearch g [1] [] [2,0,1] ghcidfsSearch g [2] [] [1,0,2] ghcidfsSearch g [3] [] [5,4,3] ghcidfsSearch 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.comwrote: 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 ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False ghcig array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])] ghcidfsSearch 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] Depth first search
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 ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False ghcig array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])] ghcidfsSearch 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Depth first search
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.comwrote: 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 ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False ghcig array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])] ghcidfsSearch 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
