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 = undefined

{-MCCOMMENT

Unfortunately, this did not compile on the server because of Data.Array.ST.

import Control.Monad (forM_, when)
import Control.Monad.ST (ST, runST)
import Data.Graph (topSort)
import Data.Array (array, (!))
import Data.Array.ST (STUArray, newArray, writeArray, readArray, getElems)

longestPath :: Graph -> Vertex -> Int
longestPath g v
  | le == 0 = 0
  | otherwise = maximum (runST distances)
  where
    distances = do
      dist <- newArray (1, lv) minBound :: ST s (STUArray s Int Int)
      _ <- writeArray dist v 0
      forM_ sortedVertices $ \u' ->
        forM_ (graphArray ! u') $ \v' -> do
          dV <- readArray dist v'
          dU <- readArray dist u'
          when (dU /= minBound && dV < dU + 1) $ writeArray dist v' (dU + 1)
      getElems dist
    sortedVertices = topSort graphArray
    findEdges v' = map fst (filter (\e -> snd e == v') edges)
    graphArray = array (1, lv) graphList
    graphList = map (\v' -> (v', findEdges v')) vertices
    vertices = fst g
    edges = snd g
    lv = length (fst g)
    le = length (snd g)
-}
{-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])