I am looking for a data structure for storing a poset, that supports the following operations with good big-Oh complexity (these are done frequently):
- determining if a given element can be consistently ordered before another one (top priority above others)
- adding new ordering constraints
- returning all elements that can be ordered before a given element
The data structure must also support generating a totally ordered set from the poset, but that only needs to be done once for the output after the algorithm has already run.
So far I have been relying on a naive poset implementation, but I am reaching a point where that is no longer sustainable.
I have looked at https://cstheory.stackexchange.com/questions/8503/what-persistent-data-structure-for-a-set-of-partially-ordered-elements, and there are some interesting papers in the answers, but most of these data structures (like ChainMerge) seem to be optimized with sorting in mind, where for me it is the least important step.