99 questions/Solutions/87
From HaskellWiki
< 99 questions  Solutions(Difference between revisions)
Jagbolanos (Talk  contribs) (Depth First Search in a graph) 
Jagbolanos (Talk  contribs) 

Line 1:  Line 1:  
−  type Node = Int 
+  <haskell> 
−  type Edge = (Node,Node) 
+  type Node = Int 
−  type Graph = ([Node],[Edge]) 
+  type Edge = (Node,Node) 
−  depthfirst :: Graph > Node > [Node] 
+  type Graph = ([Node],[Edge]) 
−  depthfirst (v,e) n 
+  
+  depthfirst :: Graph > Node > [Node] 

+  depthfirst (v,e) n 

 [xx<v,x==n] == [] = [] 
 [xx<v,x==n] == [] = [] 

 otherwise = dfrecursive (v,e) [n] 
 otherwise = dfrecursive (v,e) [n] 

−  dfrecursive :: Graph > [Node] > [Node] 
+  
−  dfrecursive ([],_) _ = [] 
+  dfrecursive :: Graph > [Node] > [Node] 
−  dfrecursive (_,_) [] = [] 
+  dfrecursive ([],_) _ = [] 
−  dfrecursive (v,e) (top:stack) 
+  dfrecursive (_,_) [] = [] 
+  dfrecursive (v,e) (top:stack) 

 [xx<v,x==top] == [] = dfrecursive (newv, e) stack 
 [xx<v,x==top] == [] = dfrecursive (newv, e) stack 

 otherwise = top : dfrecursive (newv, e) (adjacent ++ stack) 
 otherwise = top : dfrecursive (newv, e) (adjacent ++ stack) 

Line 15:  Line 15:  
adjacent = [x  (x,y)<e,y==top] ++ [x  (y,x)<e,y==top] 
adjacent = [x  (x,y)<e,y==top] ++ [x  (y,x)<e,y==top] 

newv = [xx<v,x/=top] 
newv = [xx<v,x/=top] 

−  +  </haskell> 

Call it: 
Call it: 

−  depthfirst ([1,2,3,4,5],[(1,2),(2,3),(1,4),(3,4),(5,2),(5,4)]) 1 
+  <haskell> 
+  depthfirst ([1,2,3,4,5],[(1,2),(2,3),(1,4),(3,4),(5,2),(5,4)]) 1 

+  </haskell> 
Latest revision as of 23:26, 5 March 2011
type Node = Int type Edge = (Node,Node) type Graph = ([Node],[Edge]) depthfirst :: Graph > Node > [Node] depthfirst (v,e) n  [xx<v,x==n] == [] = []  otherwise = dfrecursive (v,e) [n] dfrecursive :: Graph > [Node] > [Node] dfrecursive ([],_) _ = [] dfrecursive (_,_) [] = [] dfrecursive (v,e) (top:stack)  [xx<v,x==top] == [] = dfrecursive (newv, e) stack  otherwise = top : dfrecursive (newv, e) (adjacent ++ stack) where adjacent = [x  (x,y)<e,y==top] ++ [x  (y,x)<e,y==top] newv = [xx<v,x/=top]
Call it:
depthfirst ([1,2,3,4,5],[(1,2),(2,3),(1,4),(3,4),(5,2),(5,4)]) 1