[Haskell-cafe] Depth first search

[mukesh tiwari]

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... at 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... at 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... at haskell.org
> >http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-C... at haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe