module Exercise_5 where
import Test.QuickCheck
import Data.List

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


longestPath :: Graph -> Vertex -> Int
longestPath (node, edge) t = go [t] 0
 where go [] n = n-1
       go xs n = go(nub(concat[[w|(w, u)<- edge,u == x ]|x<-xs])) n+1
{-TTEW-}

{-   
--old version
longestPath2 :: Graph -> Vertex -> Int
longestPath2 (node, edge) t= go [root (node, edge)] [(n,0)|n<-node]
 where desc = descendants (node, edge) t
       go [] xs = head [b|(a,b)<- xs,a==t]
       go (y:ys) xs = go (nub(ys++kinder)) [if v `elem` kinder then (v, max ((head[b|(a,b)<-xs,a==y])+1) i) else (v,i)|(v,i)<-xs] 
         where kinder = [u|(w, u)<- edge,w == y, not (u `elem` desc) ]
 
-- alternative version 
longestPath1 :: Graph -> Vertex -> Int
longestPath1 (node, edge) t= go [t] [(n,0)|n<-node]-- [(n,0)|n<- (vorgaenger (node, edge) t)]
 where go [] xs = maximum [b|(a,b)<- xs]
       go (y:ys) xs = go (nub(ys++father)) [if v `elem` father then (v, max ((head[b|(a,b)<-xs,a==y])+1) i) else (v,i)|(v,i)<-xs] 
         where father = [w|(w, u)<- edge,u== y ]



vorgaenger :: Graph -> Vertex -> [Vertex]
vorgaenger (node, edge) v = go [v] (father (node, edge) v)
 where go xs [] = xs
       go xs ys= go (nub(xs++ys)) (nub (concat[father (node, edge) y|y<-ys]))

 
index :: [Vertex]-> Vertex -> Int
index xs y= head[i|i<-[0..length xs -1], xs!!i == y]

father :: Graph -> Vertex -> [Vertex]
father (node, edge) v= [w|(w, u)<- edge,u == v ]

children :: Graph -> Vertex -> [Vertex]
children (node, edge) v= [u|(w, u)<- edge,w == v ]

descendants :: Graph -> Vertex -> [Vertex]
descendants (node, edge) v = go [] (children (node, edge) v)
 where go xs [] = xs
       go xs ys= go (nub(xs++ys)) (nub (concat[children (node, edge) y|y<-ys]))

root :: Graph -> Vertex
root (node, edge)= head [n |n<-node, and[u/=n|(v,u)<-edge]] 

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