Comparison Based Ranking Algorithm (Variation)

Question

This question is a variation on a previous question: Comparison-based ranking algorithm

The variation I would like to pose is: what if loops are solved by discarding the earliest contradicting choices so that a transitive algorithm could actually be used.

Here I have pasted the original question:

"I would like to rank or sort a collection of items (with size potentially greater than 100,000) where each item in the collection does not have an intrinsic (comparable) value, instead all I have is the comparisons between any two items which have been provided by users in a 'subjective' manner.

Example:

Consider a collection with elements [a, b, c, d]. And comparisons by users:

b > a, a > d, d > c

The correct order of this collection would be [b, a, d, c].

This example is simple however there could be more complicated cases:

Since the comparisons are subjective, a user could also say that c > b. In which case that would cause a conflict with the ordering above. Also you may not have comparisons that 'connects' all the items, ie:

b > a, d > c. In which case the ordering is ambiguous. It could be : [b, a, d, c] or [d, c, b, a]. In this case either ordering is acceptable.

...

The Question is:

Is there an algorithm which already exists that can solve the problem above, I would not like to spend effort trying to come up with one if that is the case. If there is no specific algorithm, is there perhaps certain types of algorithms or techniques which you can point me to?"

Answer 1

The simpler version where no "cycle" exists can be dealt with using topological sorting.

Now, for the more complex scenario, if for every "cycle" the order on which the elements appear in the final ranking does not matter, then you could try the following:

• model the problem as a directed graph (i.e. the fact that a > b implies that there is an edge in the resulting graph starting in node "a" and ending in node "b").

• calculate the strongly connected components (SCC) of the graph. In short, an SCC is a set of nodes with the property that you can get to any node in the set from any node in the set by following a list of edges (this corresponds to your "cycles" in the original problem).

• transform the graph by "collapsing" each node into the SCC it belongs to, but preserve the edges that that go between different SCC's.

• it turns out the new graph obtained in the way mentioned above is a directly acyclic graph so we can perform a topological sort on it.

Finally, we're ready. The topological sort should tell you the right order in which to print nodes in different SCC's. For the nodes in the same SCC's, no matter what the order you choose is, there will always be "cycles", so a possibility might be printing them in a random order.