1
$\begingroup$

Please excuse or improve the poor title of this question.

My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem.

So there is plenty of work on sorting algorithms.

Sorting is usually understood as creating a / the one correct total order given a set of elements X and their pairwise relationship x >= x' for all x in X. Or actually >= is the total order and the task is to create a sequence or directed graph s.t. x comes after x' iff x>=x'.

Now you want to do the exact same thing, only >= does not define a total order over X, but only a partial order.

This seems like a very straightforward generalization that I can only imagine is required quite often. Still, under the term partial order production, I find only very little literature on the topic / task.

Am I missing something?

EDIT: Alternative Formulation

Given a set of elements X and a function f that returns the relationship between any two elements x,x' in X. Create a DAG with an edge x->x' if the relationship is >= and x'->x if the relationship f((x,x')) is <. Then create the transitive reduction of the DAG.

  1. f(x,x') is either >= or <. This is normal sorting.

  2. f(x,x') is either >=, < or ? (not comparable). This is partial order production.

I would say both are clearly ordering problems, given the relationship function f (the order) and the elements X to order.

Still you find so much on case (1) and hardly anything on case (2).

$\endgroup$
1
$\begingroup$

This is a very well-known problem, known as topological sorting.

Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the pointer, but I had just looked at topological sorting, and I actually think it is something different. Topological sorting still creates a number of possible total orders over the elements of a partial order. I will think some more about my problem and try to specify. $\endgroup$ – Radio Controlled Jul 2 at 16:44
  • $\begingroup$ Maybe it could be this, if you start from scratch, only insert and order: en.wikipedia.org/wiki/Order-maintenance_problem $\endgroup$ – Radio Controlled Jul 2 at 17:10
1
$\begingroup$

This is a comment

There is a confusion when you say that sorting is creating the correct total order. When sorting, the total order is input as the relation $\geq$. What sorting does is output the order-preserving map from the natural numbers $0,1,2,...$ to the totally ordered set (or multiset) that was input. Typically, when this is implemented the map is given in the form of an array in which the assignation $\operatorname{index}\mapsto\operatorname{value}$ is the map from the natural numbers.

With this in mind, you should try to rephrase ... (Well, you already rephrased what you intended to ask)

With your rephrasing, you essentially answered your own question.

Producing the graph, is a step that depends on your implementation. In principle the graph is already given in the input in the form of the relation $\geq$, which is the adjacency matrix and the set, or multiset, of values, which are the vertices (which you could consider weighted if you allow repetitions of the values). So, the only problem left in your interpretation of ordering in partial orders is the computation of transitive reduction.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.