Is the topsort from “Structuring Depth-First Search Algorithms” guaranteed to be (reverse) stable?

Question

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?

Answer 1

Stripping the Haskell encryption from your question (and ignoring why you are using dff instead of dfs to get a search that respects a given order), you appear to be asking about the stability of the topological sorting algorithm that performs a depth first search and reverses a postorder traversal of the depth-first spanning forest. However, there is a more general answer to your question: it is not generally possible, given a sequence of vertices in a DAG, to find a topological ordering that respects the input sequence for all incomparable pairs of vertices in the DAG. That is, stable topological ordering is not possible.

To see this, consider a DAG with three vertices $a$, $b$, and $c$, and one edge $a\rightarrow b$, with the vertex ordering $bca$. The DAG has three topological orderings $abc$, $acb$, $cab$, but none of these are stable: $abc$ and $acb$ both reverse the pair $ca$, and $acb$ and $cab$ both reverse the pair $bc$.

For the same reason, reverse-stable topological ordering is also not possible. In particular the reverse-postorder-dfs algorithm is not reverse-stable.