module Exercise_5 where
import Test.QuickCheck
import Data.List

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

-- makes a set of all seconds 
setToList :: [Edge] -> [Vertex] 
setToList [] = [] 
setToList (x:xs) = [snd x] ++ setToList xs 

--([1..5], [(1,2),(2,3),(3,4),(4,5),(5,2),(5,3)])

-- finds the start
getStart :: Graph -> Vertex 
getStart (v, e) = head (v \\ (setToList e))

-- returns all childs of your vertex 
getChild :: Graph -> Vertex -> [Vertex] 
getChild (list, []) start = []
getChild (list, (x:xs)) start
    | fst x == start = [snd x] ++ getChild (list, xs) start
    | otherwise = getChild (list, xs) start 

findX :: Graph -> Vertex -> Vertex -> Int 
findX graph start end  --1 + max [ functions] 
    | start == end = 0
    | null (getChild graph start ) = -100
    | otherwise = 1 + maximum [findX graph x end | x <- (getChild graph start)]

longestPath :: Graph -> Vertex -> Int
longestPath g  t = findX g (getStart g) t 



{-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])