module Exercise_5 where
import Test.QuickCheck
import Data.List
import qualified Data.Graph as Gra
import qualified Data.IntMap as IntMap
import Data.IntMap (IntMap)
import qualified Data.Array as Array

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

updateDistances::[Vertex] -> Int -> IntMap Int-> IntMap Int
updateDistances [] _ distances = distances
updateDistances (v:vs) newDistance distances = updateDistances vs newDistance (IntMap.adjust upd v distances) where
  upd x = if  x > newDistance then x else newDistance

computeDistances::[Vertex] -> Gra.Graph -> IntMap Int -> IntMap Int
computeDistances [] graph distances = distances
computeDistances (currentNode:ts) graph distances =
    computeDistances ts graph (updateDistances (graph Array.! currentNode) ((distances IntMap.! currentNode) + 1) distances)

--https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
longestPath :: Graph -> Vertex -> Int
longestPath g t =
  let
    graph =  Gra.buildG (minimum (fst g), maximum (fst g)) (snd g)
    --do topological sort
    topOrder = Gra.topSort graph
    --update distances in topological order
    distances = computeDistances topOrder graph (IntMap.fromList [(k,0) | k <- topOrder])
  in
    distances IntMap.! t
{-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])