99 questions/Solutions/81
From HaskellWiki
< 99 questions  Solutions(Difference between revisions)
Line 19:  Line 19:  
 otherwise = (paths1 x b g (current++[a])) ++ (paths2 a b g current xs) 
 otherwise = (paths1 x b g (current++[a])) ++ (paths2 a b g current xs) 

</haskell> 
</haskell> 

−  +  paths :: Int > Int > [(Int , Int)] > [[Int]] 

+  paths start end zs = let (xs,ys) = partition (\(_,z) > z == end ) zs 

+  in map (++ [ end] ) ( concat . map (\(e, _) > if e == start then [[start]] else paths start e ys) $ xs ) 

This solution uses a representation of a (directed) graph as a list of arcs (a,b). 
This solution uses a representation of a (directed) graph as a list of arcs (a,b). 
Revision as of 05:41, 18 April 2011
(**) Path from one node to another one
Write a function that, given two nodes a and b in a graph, returns all the acyclic paths from a to b.
import List (elem) paths :: Eq a => a > a > [(a,a)] > [[a]] paths a b g = paths1 a b g [] paths1 :: Eq a => a > a > [(a,a)] > [a] > [[a]] paths1 a b g current = paths2 a b g current [ y  (x,y) < g, x == a ] paths2 :: Eq a => a > a > [(a,a)] > [a] > [a] > [[a]] paths2 a b g current []  a == b = [current++[b]]  otherwise = [] paths2 a b g current (x:xs)  a == b = [current++[b]]  elem a current = []  otherwise = (paths1 x b g (current++[a])) ++ (paths2 a b g current xs)
paths :: Int > Int > [(Int , Int)] > Int paths start end zs = let (xs,ys) = partition (\(_,z) > z == end ) zs
in map (++ [ end] ) ( concat . map (\(e, _) > if e == start then start else paths start e ys) $ xs )
This solution uses a representation of a (directed) graph as a list of arcs (a,b).