module Exercise_5 where
import Test.QuickCheck
import Data.List
import Data.Ord

{- H5.3 -}
{-WETT-}
type Vertex = Int
type Edge = (Vertex, Vertex)
type Graph = ([Vertex], [Edge])

-- backward traversal
longestPath :: Graph -> Vertex -> Int
longestPath g t = maximum $ step g [(t,0)]

step :: Graph -> [(Vertex,Int)] -> [Int]
step (vs,es) [] = []
step (vs,es) ((v,w):vws) = if null ops
                           then w : step (vs,es) vws
                           else step (vs,es) (nubBy (\(c,d) (e,f) -> c == e) (sortBy (comparing (Down . snd)) (ops ++ vws)))
                           where
    ops = reverse [(a,w+1) | (a,b) <- es, b == v]
	
-- forward traversal - doesn't work
{-
longestPath :: Graph -> Vertex -> Int
longestPath (vs,es) t = step [(1,0)] where
    step :: [(Vertex,Int)] -> Int
    step ((v,w):vws) | v == t = w
                     | otherwise = step $ sortBy (comparing (Down . snd)) (reverse [(b,w+1) | (a,b) <- es, a == v] ++ vws)
-}
{-TTEW-}

-- generates a DAG with u vertices and only one node without incoming edges
-- you can use this function to test your implementation using QuickCheck
genDag :: Int -> Gen Graph
genDag n = let v = [1..n] in
  do b <- mapM (\i -> choose (1,n-i)) [1..n-1]
     t <- mapM (\(c,i) -> vectorOf c (choose (i+1, n))) (zip b [1..n])
     let e = nub $ ([(1, i) | i<-[2..n]] ++ edges t 1 [])
     return $ (v,e)
  where
    edges [] _ acc = acc
    edges (ts:xs) i acc = edges xs (i+1) (acc ++ [(i,t) | t<-ts])