tsort

tsort.hs

tsort :: (Eq a) => Graph a -> [a]
tsort graph  = tsort' [] (noInbound graph) graph
  where noInbound (Graph v e) = filter (flip notElem $ map snd e) v
        tsort' l []    (Graph _ []) = reverse l
        tsort' l []    _            = error "There is at least one cycle in this graph."
        tsort' l (n:s) g            = tsort' (n:l) s' g'
          where outEdges = outbound n g
                outNodes = map snd outEdges
                g'       = foldr removeEdge g outEdges
                s'       = s ++ filter (null . flip inbound g') outNodes