Grading partial orders (starting from topological sort)

Question

This blog post discusses an interesting variation on topological sort: http://jdh.hamkins.org/linear-gradings-of-partial-orders/

A linear grading of a partial order is just like a topological sort, except that, where permissible, vertices can share a "level" in the output.

How would one implement a program (in Haskell, say) to find all of the linear gradings of a partial order (i.e. a DAG)?

In the case of the illustration in the blog post, a topological sort can easily find the ordering [[1], [2, 3, 4], [5]]. Then the Haskell program

map concat $ sequence $ map concat $ map (map permutations) $ map partitions [[1],[2,3,4],[5]] 

seems to produce the right result. I think this code doesn't correctly solve the general case, though.

Answer 1

Based on the comments received so far, here is a sketch of what an answer might look like.

This code computes ordered partitions of a list. With a suitable poset data structure, avail and update could be replaced with appropriate functions, and I think the logic would hold.

import Control.Monad
import Data.List

delems xs zs = foldr delete zs xs
powerset xs = filterM (\x -> [True, False]) xs

-- returns the currently available subsets
avail s = filter (not . null) $ powerset s

-- updates the data structure
update e s = delems e s

ordered_partitions [] = [[]]
ordered_partitions set = do
  elems <- avail set
  remainder <- ordered_partitions (update elems set)
  [elems:remainder]

It seems that heaps (priority queues) for posets aren't a widely implemented thing. There is some discussion here Priorities in Priority Queue and here https://cs.stackexchange.com/questions/7890/priority-queue-for-partially-ordered-priorities-with-infima. Particularly relevant is the distinction between weak orderings and partial orders. Weak orders are much easier to handle.

Kahn's algorithm seems promising as a way of implementing this priority queue...