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

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


-- Another version without using Matrix (not optimised at all)
longestPath :: Graph -> Vertex -> Int
longestPath graph target = findPath (reverse table) (replicate len 0) !! getIndex table target
 where
  table = take len topo
  topo  = topoSort graph
  len   = 1 + fromJust (elemIndex target topo)

  findPath [] ans = ans
  findPath (n : ns) ans =
    increment (findPath ns ans) (snd <$> filter ((n ==) . fst) (snd graph)) n

  increment ans []       _ = ans
  increment ans (n : ns) c = if isNothing i
    then increment ans ns c
    else
      take ji ne
      ++ [max (1 + ne !! getIndex table c) (ne !! ji)]
      ++ drop (ji + 1) ne
   where
    i  = elemIndex n table
    ji = fromJust i
    ne = increment ans ns c

topoSort :: Graph -> [Vertex]
topoSort graph = reverse $ ts graph []

ts :: Graph -> [Vertex] -> [Vertex]
ts ([x], _ ) ans = x : ans
ts (xs , []) ans = xs ++ ans
ts g         ans = ts gra (ni : ans)
 where
  ni     = noInd g
  latter = filter ((ni /=) . fst) (snd g)
  former = filter (ni /=) (fst g)
  gra    = (former, latter)

noInd :: Graph -> Vertex
noInd g = findNoIn (fst g) (snd <$> snd g)
 where
  findNoIn []  _  = -1
  findNoIn vs  [] = head vs
  findNoIn [v] _  = v
  findNoIn (v : vs) e | v `elem` e = findNoIn vs e
                      | otherwise  = v

getIndex :: [Vertex] -> Vertex -> Int
getIndex vs v = fromJust $ elemIndex v vs
{-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])