[Haskell-cafe] Depth first search

[mukesh tiwari]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111109/6274508e/attachment.htm>