In "Structuring Depth-First Search Algorithms in Haskell", implemented in Data.Graph in the Haskell standard library, an algorithm for topologically sorting graphs is given:
postorder :: Tree a -> [a] -> [a]
postorder (Node a ts) = postorderF ts . (a :)
postorderF :: Forest a -> [a] -> [a]
postorderF ts = foldr (.) id $ map postorder ts
postOrd :: Graph -> [Vertex]
postOrd g = postorderF (dff g) []
topSort :: Graph -> [Vertex]
topSort = reverse . postOrd
Experimentally, this topological sort seems to be stable with respect to the reverse of the input graph, e.g.:
Prelude> import Data.Graph
Prelude Data.Graph> let d = buildG (0,3) []
Prelude Data.Graph> topSort d
[3,2,1,0]
Is this actually true? That is, given an ordered list of nodes $N$ with edges $E$, is the result of topSort
on this graph an ordering of nodes such that if there is no path from $n_1$ to $n_2$, the ordering of $n_1$ and $n_2$ from the original list is swapped from in the topologically sorted list?
As an extra thought, is there an elegant way to rewrite this algorithm so that it doesn't reverse the original order?