当 "equality" 意味着 "order doesn't matter" 时如何编写传递比较器？

Question

我有一组序列化到文件的项目。有些项目可以依赖其他项目，但不允许循环引用。因此，它们需要以某种方式序列化，如果 A 依赖于 B，则 B 首先在文件中序列化。

我写了我的 Comparator，它使用 reliesOn() 函数来确定两个项目是否链接：

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;
    }
});

这适用于一些个案例，但不是全部。在调试过程中，很明显排序依赖于 Comparator 的传递性质，并且可以理解的是不会比较每一个可能的项目对。

例如，有五个项目 A 到 E，如果：

A -> B
B -> E
C
D
E

那么一种可能的顺序是：

E, B, A, C, D

最起码，E在B之前，B在A之前。

然而，在比较阶段（解释为示例），发生的情况是 C 与 E 进行比较，返回 0，因为它们没有关系。然后 C 与 B 比较，还有 returns 0.

因此，排序算法假设 B = E，不是。（即使 我违反了 Comparator 合同 。）我如何以确保传递性的方式编写我的 compare() 方法？

编辑： 有人指出我正在对有向无环图执行拓扑排序。我正在回忆我的数据结构课程。幸运的是，维基百科似乎有一个很好的线性时间算法来执行这种排序 - 我会试一试。

Answer 1

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

正如你所发现的，Comparator 的契约迫使你根据两个给定的对象做出决定，而它们在整体排序中的关系可能涉及其他对象。

你这里有一个 DAG，你要做的是拓扑排序。我认为可以使用 Comparator 的唯一方法是首先进行拓扑排序，然后在实现比较器时使用此排序中对象的索引作为键。但是当然不需要比较器，因为您已经对元素进行了排序。

Answer 2

违反 Comparator 的约定对您没有多大帮助，因为标准排序算法假定您遵守它。

除了实现维基百科的拓扑排序算法之外，您还可以查看 this lib (which gets mentioned often when someone speaks of directed graphs and topological sorting) or that 实现。

当 "equality" 意味着 "order doesn't matter" 时如何编写传递比较器？

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

java

sorting

transitivity

comparator