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

longestPath :: Graph -> Vertex -> Int
longestPath (v, e) end = case longestPathFrom (getStart e v) end e of
  Nothing -> 0
  Just n  -> n

longestPathFrom :: Vertex -> Vertex -> [Edge] -> Maybe Int
longestPathFrom start end edges 
  | start == end  = Just 0
  | otherwise     = case nextVertexes start end edges of 
      Nothing   -> Nothing
      Just []   -> Just 0
      Just next -> case mapMaybe (\x -> longestPathFrom x end edges) next of
        []          -> Nothing
        longestPath -> Just (1 + maximum longestPath)

nextVertexes :: Vertex -> Vertex -> [Edge] -> Maybe [Vertex]
nextVertexes start end [] = if start == end then Just [] else Nothing
nextVertexes start _ es = case f es of
    []   -> Nothing
    next -> Just next 
  where
    f []            = []
    f ((v1, v2):es) = if start == v1 then v2:f es else f es

getStart :: [Edge] -> [Vertex] -> Vertex
getStart _ (v:[]) = v
getStart ((v1, v2):es) vs = (getStart es . filter (v2/=)) 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])

dotGraph :: Graph -> String
dotGraph (v, e) = "digraph{" ++ ((listToString . map (toString)) v) ++ ";" ++ ((listToString . map (\(a, b) -> (toString a) ++ "->" ++ (toString b))) e) ++ "}" where
  toString s = show s :: String
  listToString = intercalate ";"