Forgive me if this is too imprecise a question. My math-fu is weak, I'm just a humble programmer.
I'm looking for an algorithm to sort a list of items based on a partial order: each item has a list of other items that it must be before, and a list of items it must be after. I can produce from this a list of directed edges, $A > B$. However, many pairs will have no given order, while others will only have an implied order (ie $A > B$ and $B > C$ implies $A > C$, but neither $A$ nor $C$ specify this).
What I want to get from this is a single ordered list containing all the inputs once, that satisfies all conditions. There will often be many possible solutions for a given set of inputs, but I don't need to find them all or a definitive "best" order (if that even has a meaning).
Preferably the algorithm will be:
- Stable under small changes, so the resulting sorted list doesn't change wildly when an input changes. This will make the code easier to debug should one of the orders need changing.
- Linear time or near
- Functional more than procedural (but not tied to a single programming language)
- Clear enough to get my head round
No item may appear more than once in the inputs. It is of course possible for the inputs to be invalid, ie for the graph of directed edges to be cyclical. In this case it would be best to spot the error and report it accurately to aid debugging.