module Exercise_5 where
import Test.QuickCheck
import Data.List
import Data.Array

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


topOrd :: Graph -> [Vertex]
topOrd (vs, es) = fst (foo 1 (zip vs (repeat False)))
  where
    foo v visited
      | snd (visited !! (v-1)) = ([], visited)
      | null (nexts v es) = ([v], (mark v visited))
      | otherwise = (v : fst bar, snd bar)
         where bar = (foldl (\acc x -> ((fst (foo x (snd acc)) ++ fst acc), snd (foo x (snd acc))) ) ([], (mark v visited)) (nexts v es))


--count starts with 1
mark :: Int -> [(Vertex, Bool)] -> [(Vertex, Bool)]
mark i list = take (i - 1) list ++ ([(fst (list !! (i - 1)), True)] ++ (drop (i) list))


-- outgoing neighbors
nexts :: Vertex -> [Edge] -> [Vertex]
nexts v es = [snd e | e <- es, fst e == v]   


--incoming neighbors
inc_neighbors :: Vertex -> [Edge] -> [Vertex]
inc_neighbors v es = [fst e | e <- es, snd e == v]  


longestPath :: Graph -> Vertex -> Int
longestPath (vs,es) v = head [snd x | x <- longestPaths (reverse (topOrd (vs,es))) es, fst x == v]


--takes reversed topologically ordered vertices and edge list as arguments
longestPaths :: [Vertex] -> [Edge] -> [(Vertex,Int)]
longestPaths [] es = []
longestPaths [v] es = [(v,0)]
longestPaths (v:vs) es = (v, maximum(0: [snd x | x <- longestPaths vs es, prev <- inc_neighbors v es, fst x == prev]) + 1) : (longestPaths vs es)


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