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 gs end
  | nodes == [] = 0
  | edges == [] = 0
  | otherwise = mx
    where
      mx = maxSteps nextSteps end
      nextSteps = [[(i,j) | (i,j) <- edges, j==x] | x <- nodes]
      -- beg = head [x | x <- nodes, x `notElem` reachable] -- get the starting element
      reachable = nub [j| (i,j) <- edges]
      nodes = fst gs
      edges = snd gs

maxSteps :: [[Edge]] -> Vertex -> Int
maxSteps cons cur
      | all == [] = 0
      | otherwise = 1 + maximum all
        where 
          all = [maxSteps cons i | (i,j) <- nexts]
          nexts = cons!!(cur - 1) 



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