# 99 questions/Solutions/81

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

Trackbully (Talk | contribs) (Add an additional recursive solution to the problem) |
|||

(2 intermediate revisions by 2 users not shown) | |||

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). |
||

+ | |||

+ | ---- |
||

+ | |||

+ | Here is another implementation using List's monadic behavior |
||

+ | |||

+ | <haskell> |
||

+ | import Data.List (partition) |
||

+ | |||

+ | pathsImpl :: Eq a => [a] -> a -> a -> [(a, a)] -> [[a]] |
||

+ | pathsImpl trail src dest clauses |
||

+ | | src == dest = [src:trail] |
||

+ | | otherwise = do |
||

+ | let (nexts, rest) = partition ((==src) . fst) clauses |
||

+ | next <- nexts |
||

+ | pathsImpl (src:trail) (snd next) dest rest |
||

+ | |||

+ | paths :: Eq a => a -> a -> [(a, a)] -> [[a]] |
||

+ | paths src dest clauses = map reverse (pathsImpl [] src dest clauses) |
||

+ | </haskell> |
||

+ | |||

+ | ---- |
||

+ | |||

+ | Here is another recursive implementation |
||

+ | <haskell> |
||

+ | paths :: Eq a =>a -> a -> [(a,a)] -> [[a]] |
||

+ | paths source sink edges |
||

+ | | source == sink = [[sink]] |
||

+ | | otherwise = [ |
||

+ | [source] ++ path | edge<-edges, (fst edge) == source, |
||

+ | path<-(paths (snd edge) sink [e|e<-edges, e/=edge]) |
||

+ | ]; |
||

+ | </haskell> |

## Latest revision as of 17:10, 4 January 2012

(**) 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)

This solution uses a representation of a (directed) graph as a list of arcs (a,b).

Here is another implementation using List's monadic behavior

import Data.List (partition) pathsImpl :: Eq a => [a] -> a -> a -> [(a, a)] -> [[a]] pathsImpl trail src dest clauses | src == dest = [src:trail] | otherwise = do let (nexts, rest) = partition ((==src) . fst) clauses next <- nexts pathsImpl (src:trail) (snd next) dest rest paths :: Eq a => a -> a -> [(a, a)] -> [[a]] paths src dest clauses = map reverse (pathsImpl [] src dest clauses)

Here is another recursive implementation

paths :: Eq a =>a -> a -> [(a,a)] -> [[a]] paths source sink edges | source == sink = [[sink]] | otherwise = [ [source] ++ path | edge<-edges, (fst edge) == source, path<-(paths (snd edge) sink [e|e<-edges, e/=edge]) ];