module Exercise_5 where

import Test.QuickCheck
import Data.List
import Data.Array
import Data.Graph hiding (Graph,Vertex,Edge)

{- H5.3 -}
{-WETT-}



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


cmp (a,_) (b,_) = compare a b
maxi::[Int]->Int
maxi [] = -1
maxi xs = maximum xs
longestPath :: Graph-> Vertex -> Int
longestPath (v,e) s = f s
  where min_v = minimum v
        max_v = maximum v
        graph = buildG (min_v,max_v) e
        tgraph = transposeG graph
        topo = topSort graph
        iTable = listArray (min_v,max_v) (map snd (sortBy cmp (zip topo [min_v..max_v])))
        f x = 1 + maxi [memo!(iTable!nxt)|nxt<-(tgraph ! x)]
        memo = listArray (min_v,max_v) (map f topo)

{-TTEW-}

testlP:: Int -> Int
testlP n = longestPath ([1..n],[(x,y)|x<-[1..n],y<-[x+1..n]]) n









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