module Exercise_5 where
import Test.QuickCheck
import Data.List

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

getRoot :: Graph -> Vertex
getRoot (vs, es) = head (filter (\x -> (not (elem  x (map (\(v1, v2) -> v2) es)))) vs)

getNeighbours :: Graph -> Vertex -> [Vertex]
getNeighbours (vs, es) v = map (\(_, v1) -> v1) (filter (\(v1, _) -> v1==v) es) 

lpnh :: Graph -> Vertex -> Vertex -> Int
lpnh (vs, es) v g = if (v==g) then 0
					else if (length list > 0) then
						if maximum list == -1 then -1
						else (maximum list)+1
					else -1
					where list = [lpnh (vs, es) v1 g | v1 <- getNeighbours (vs, es) v]

longestPathNaive :: Graph -> Vertex -> Int
longestPathNaive g v = lpnh g (getRoot g) v


getPrev :: Graph -> Vertex -> [Vertex]
getPrev (vs, es) v = map (\(v1, _) -> v1) (filter (\(_, v1) -> v1==v) es)


getAdjList :: Graph -> [[Vertex]]
getAdjList (vs, es) = [getPrev (vs, es) v | v <- vs]

lph :: [[Vertex]] -> Vertex -> Vertex -> Int
lph adjList v g = if (v==g) then 0
					else if (length list > 0) then
						if maximum list == -1 then -1
						else (maximum list)+1
					else -1
					where list = [lph adjList v1 g| v1 <- adjList!!(v-1)] 

longestPath :: Graph -> Vertex -> Int
longestPath g v = lph (getAdjList g) v (getRoot g)

testGen :: Int -> Property
testGen size =
  1 <= size && size < 20
  ==> do g@(vs, _) <- genDag size
         v <- elements vs
         return $ longestPath g v === longestPathNaive g v

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