module Exercise_5 where
import Test.QuickCheck
import Data.List
import qualified Data.IntMap.Strict as IntMap

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

longestPathSimple :: Graph -> Vertex -> Int
longestPathSimple (_, []) t = 0
longestPathSimple (_, es) t = if null outs then 0 else 1 + maximum [longestPathSimple ([], rests) (fst e) | e <- outs]
    where (outs, rests) = partition (\e -> snd e == t) es

longestPath :: Graph -> Vertex -> Int
longestPath (_, []) t = 0
longestPath (_, es) t = walk m t
    where m = IntMap.fromListWith (++) (map (\(a, b) -> (b,[a])) es)

walk m t = if null nexts then 0 else maximum [1 + walk rest next | next <- nexts]
    where nexts = IntMap.findWithDefault [] t m
          rest = IntMap.delete t m
{-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])