Personal tools

99 questions/Solutions/81

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
 
(Add an additional recursive solution to the problem)
 
(3 intermediate revisions by 2 users not shown)
Line 21: Line 21:
   
 
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])
    ];