[Haskell-cafe] Depth first search
mukesh tiwari
mukeshtiwari.iiitm at gmail.com
Wed Nov 9 16:44:54 CET 2011
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
More information about the Haskell-Cafe
mailing list