import Control.Search.SetFunctions

-- Find a shortest path in a graph

-- The nodes:
data Node = A | B | C | D | E
 deriving (Eq,Show)

-- The edges:
-- data Edge = Edge Node Node

-- ..represented as a (non-deterministic) successor operation:
succ :: Node -> Node
succ A = B ? C
succ B = A ? C ? D
succ C = D ? E
succ D = E
succ E = C

-- Path from some node to another node:
pathFromTo :: Node -> Node -> [Node]
pathFromTo n1 n2 = extendPath n2 [n1]

extendPath :: Node -> [Node] -> [Node]
extendPath target path@(current:_) =
  if target == current
    then reverse path
    else extendPath target ((succ current) `consNoCycle` path)

consNoCycle :: Node -> [Node] -> [Node]
consNoCycle x xs | all (x/=) xs
                 = x : xs

-- Compute a shortest path:
shortestPathFromTo :: Node -> Node -> [Node]
shortestPathFromTo n1 n2 = minValueBy shorter ((set2 pathFromTo) n1 n2)
 where shorter p1 p2 = compare (length p1) (length p2)