As a mathematician (not as an engineer), the instinct is to complete your relation into a

**partial order**: Compute the transitive closure by repeatedly adding the forced pairs (if A < C and C < B, then add A < B to your relation) until you can't add any more. Then websearch for an algorithm about partial orders; the task is to find a linear order a.k.a. total order that contains your partial order.

But problem: I don't know if we're wasting too much algorithmic time by first computing the transitive closure. Maybe there is a better way to work directly with the nontransitive relation that you have, a way that will still come up with a suitable total order. It's probably enough to assume that the transitive closure (that always exists) would, if we were to compute it, be cycle-free (and thus be a partial order).

When websearching for algorithms, include "partial order" as a search term nonetheless, or "extend partial order into total order", maybe you find useful things that still work.

Ad hoc, I found:

Partial-Order PlanningLinear Extension of a partial order. This looks like pure math, but refers to algorithms in reference #5.

The next keyword to websearch from there is:

**Topological sort**, or directly

on wikipedia. (Starts to sounds like geoo or another computer scientist could have pointed us there much quicker.

)

-- Simon