module Exercise_5 where

import Data.Array
import Data.List
import Data.Maybe
import Data.Ord
import Data.Tuple
import Test.QuickCheck

{- H5.3 -}
{-WETT-}
type Vertex = Int

type Edge = (Vertex, Vertex)

type Graph = ([Vertex], [Edge])

longestPath :: Graph -> Vertex -> Int
longestPath g v = helper (adjacencyList ! v) 1 0
  where
    helper nextNodes currentDepth maxFoundDepth
      | null nextNodes = maxFoundDepth
      | otherwise =
        helper
          (concatMap (adjacencyList !) nextNodes)
          (succ currentDepth)
          newMaxFoundDepth
      where
        newMaxFoundDepth =
          if startingNode `elem` nextNodes
            then currentDepth
            else maxFoundDepth
    adjacencyList =
      accumArray (flip (:)) [] (0, maximum vertices) $ map swap edges
    vertices = fst g
    edges = snd g
    startingNode = fromJust $ find (null . (adjacencyList !)) vertices

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