module Exercise_5 where
import Test.QuickCheck
import Data.List

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

longestPath :: Graph -> Vertex -> Int
longestPath g t = path (firstNode (fst g) (snd g)) t (snd g)

path :: Vertex -> Vertex -> [Edge] -> Int
path str end egs = if str == end then 0 else if length z > 0 then maximum z + 1 else 0
   where 
    z = pathparents (parents end egs) str egs
    pathparents [] _ _ = []
    pathparents (x:xs) str egs = (path str x egs) : pathparents xs str egs 

parents :: Vertex -> [Edge] -> [Vertex]
parents _ [] = []
parents v (e:es) = if snd e == v then (fst e ) : parents v es else parents v es

firstNode :: [Vertex] -> [Edge] -> Vertex
firstNode (v:vs) es = helpFirst v es 
  where 
    helpFirst v [] = v
    helpFirst v (a:as) = if v == snd a then firstNode vs es else helpFirst v as
      
{-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])