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