# Difference between revisions of "99 questions/Solutions/81"

From HaskellWiki

< 99 questions | Solutions

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

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:45, 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)
```

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