I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables representing elements of the set. The laws that relate the two orderings are the same as $<$ and $\leq$ for integers. I need to make sure that each constraint that I add does not make the set inconsistent (e.g. adding $x < y$ and then $y < x$ I'd get an error).
Now, if I had only the $<$ constraints I could get away with generating a graph and then doing a topological sort, or with disjoint-sets. The problem is that I'm not sure how to handle the additional $\leq$ constraints.
One idea is to express $x \leq y$ as $\neg (x > y)$, and to keep two graphs: one for the actual $<$ relations and one for the negated ones. Then we'd need to check, at each new constraints, whether there are overlapping paths between the two graphs, in which case we'd have a problem. However this seems rather costly since it seems to me that we'd need to analyze all the pairs each time.
Another idea would be to 'collapse' $\leq$ relations to equalities or $<$ when needed, but again I'm quite uncertain on the details.
Is this problem described somewhere? As a bonus, I'd like the data structures involved to be purely functional.