Sorting w. r. t. a partial ordering

2022-09-03, post № 263

programming, #haskell, #order-theory

Task. Given a type $T$ , a finite array $v=(n,\varphi)$ with $n\in\mathbb{N}_0$ and $\varphi:\{1..n\}\to T$ together with a finite set of pairs $K\subset T^2$ , compute a permutation $\pi\in\mathbb{S}_n$ such that $v':=(n,\varphi\circ\pi)$ respects the strict partial ordering induced by $K$ , provided $K$ is loop-free.
Furthermore choose $\pi$ to respect relative ordering of equal elements, that is

$\forall\,i<j\in\{1..n\}:\Big(v_i=v_j\implies\pi(i)<\pi(j)\Big).$

An application of late is computing the execution order of inter-dependent transformers.

Possibly due to the seeming banality of the application, my many first presumptuous attempts were both of questionable algorithmic complexity as well as failing in subtle ways, fostering bugs which only seldom showed their ugly faces. Fed up with hotfixed bypasses and manual pre-ordering, I badly longed after an implementation which indeed took some time to get right:

Heart of my approach I will herein present is computing a total ordering on all order-participating values $L:=\bigcup\{\{x,y\};(x,y)\in K\}$ that is compatible with $K$ and thus an apt choice for a sorting key to attain $\pi$ by arbitrary extension to $v$ .
For this consider the digraph $D:=(L,K)$ and inductively deconstruct it to form a $K$ -conforming array $(\#L,\varphi_L:\{1..\#L\}\to L)$ . Care must be taken, however, to correctly position elements left of a node of minimal degree three as e. g. greedily seeking chains may disregard local element relations. As such, iteratively pluck an arbitrarily chosen minimal element, laying these out from left to right via $\varphi_L$ . Their minimality ensures that no element can contradict $K$ going down.
When using a stable sorting algorithm which sorts under $\varphi_L$ , relative ordering is naturally respected as desired.

I wrote quadratic implementation in Haskell that only stipulates Eq a: sort-via.hs. To achieve the complexity typically sought after for sorting tasks, I suspect an underlying total order on the elements is required for data management. Avoiding Haskell’s non-ADT containers and disappointing standard library support for random number generation, I wrote a C++ implementation and test suite testing both: sort-via.cpp, Makefile.