import Control.SetFunctions -- The nodes of a graph data Node = A | B | C | D | E deriving (Eq,Show) -- The edges of a graph next :: Node -> Node next A = B next A = C next B = A next B = C next B = D next C = D next C = E next D = E next E = C type Path = [Node] -- Constrained Constructor: -- Cons for paths with fail if the result is cyclic. consNoCyclePath :: Node -> Path -> Path consNoCyclePath n p | all (/= n) p = n : p -- Returns a path from one node to another node. pathFromTo :: Node -> Node -> Path pathFromTo n1 n2 = extendPath n2 [n1] -- Extends a path (in reverse order) up to a target node. extendPath :: Node -> Path -> Path extendPath target path@(n:_) = if target == n then reverse path else extendPath target (next n `consNoCyclePath` path) -- Compute the shortest path: shortestPath :: Node -> Node -> Path shortestPath n1 n2 = minValueBy shorter ((set2 pathFromTo) n1 n2) where shorter p1 p2 = compare (length p1) (length p2)