How to write a transitive comparator when "equality" implies "order doesn't matter"?

Question

I have a set of items that are serialized to a file. Some items can rely on other items, but circular references are not allowed. Thus, they need to be serialized in a way such that if A relies on B, B is serialized first in the file.

I wrote my Comparator that uses a reliesOn() function to determine if two items are linked:

Collections.sort(itemsToSort, new Comparator<Item>() {
    @Override
    public int compare(Item first, Item second) {
        boolean firstReliesOnSecond = reliesOn(first, second);
        if (firstReliesOnSecond) {
            return 1;
        }
        boolean secondReliesOnFirst = reliesOn(second, first);
        if (secondReliesOnFirst) {
            return -1;
        }
        return 0;
    }
});

This works for some cases, but not all. In debugging, it's obvious that the sort relies on the transitive nature of the Comparator, and understandably does not compare every possible pairing of items.

For example, with five items A through E, if:

A -> B
B -> E
C
D
E

Then one possible ordering would be:

E, B, A, C, D

At the very least, E comes before B, and B comes before A.

However, during the comparison phase (paraphrasing as an example), what happens is that C is compared to E, returning 0 because they have no relation. And then C is compared to B, and also returns 0.

And as a result, the sorting algorithm assumes B = E, which is not the case. (Even though I broke the Comparator contract.) How can I write my compare() method in a way that ensures transitivity?

Edit: It was pointed out that I'm performing a topological sort on a directed acyclic graph. I'm having flashbacks to my Data Structures course. Fortunately Wikipedia seems to have a good linear-time algorithm for performing this sort - I'll give it a shot.

BTW, it's not `Comparator` that assumes B = E, it's the sorting algorithm. (`Comparator` contains very little code itself) — user253751, Jan 22 '15 at 21:50
You're right - I suppose it's a combination of the sorting algorithm, and the contract that the `Comparator` is supposed to fulfill. I'll update my wording, thanks! — Craig Otis, Jan 22 '15 at 21:51
Can you access the related objects of an `Item`? Is there like a `getParents()` or something like that? — aioobe, Jan 22 '15 at 21:57
you can't use a sort. you have to go through the forest to get all the leaves first — njzk2, Jan 22 '15 at 21:57
Unless it's crystal clear I tend to be conservative with the close votes. In this case I'll leave it up to OP to decide if the answer in the other thread answers his question here. — aioobe, Jan 22 '15 at 22:49

aioobe · Accepted Answer · 2015-01-22T22:03:05.727

2

How can I write my compare() method in a way that ensures transitivity?

As you've discovered the contract of a Comparator forces you to make a decision based on two given objects, while their relation in the overall sort may involve other objects.

What you have here is a DAG and what you're trying to do is a topological sort. The only way I see that it would be possible to do using a Comparator would be to first do a topological sort, and then using the indexes of the objects in this sorting as keys when implementing the comparator. But then of course there's no need for the comparator since you have already sorted the elements.

edited Jan 22 '15 at 22:03

answered Jan 22 '15 at 21:53

aioobe

413,195
112
811
826

Thank you for this - you led me to the right place. (Will mark as answered when the time limit is up.) – Craig Otis Jan 22 '15 at 22:00
Can you access the "parents" of each `Item`? – aioobe Jan 22 '15 at 22:00
Yes, we have a visitor/utility method that will find them. – Craig Otis Jan 22 '15 at 22:01
Then there may be a chance of solving it by checking if object 1 is found on the path from object 2 up to the root (or vice versa). But 1) it would just be a convoluted and suboptimal implementation of a topological sort and 2) you would need a way to resolve order of siblings – aioobe Jan 22 '15 at 22:04

score 0 · Answer 2 · answered Jan 22 '15 at 22:21

Breaking the contract of Comparator does little to help you, since the standard sorting algorithms assume that you honor it.

Besides implementing a topological sort algorithm from Wikipedia you can also take a look at this lib (which gets mentioned often when someone speaks of directed graphs and topological sorting) or that implementation.

How to write a transitive comparator when "equality" implies "order doesn't matter"?

2 Answers2