Как написать транзитивный компаратор, когда «равенство» подразумевает «порядок не имеет значения»?

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, а также возвращается 0.

И в результате алгоритм сортировки предполагает B = E, что составляет не. (Несмотря на то, что я разорвал договор Comparator.) Как я могу написать свой метод compare() таким образом, чтобы обеспечить транзитивность?

Редактировать: Было указано, что я выполняю топологическую сортировку на направленном ациклическом графе. У меня есть воспоминания о моем курсе Data Structures. К счастью, у Википедии есть хороший алгоритм линейного времени для выполнения этого вида - я дам ему шанс.

Answer 1

Как написать метод compare() таким образом, чтобы обеспечить транзитивность?

Как вы обнаружили контракт через Comparator заставляет вас принять решение на основе двух указанных объектов, в то время как их соотношение в общем-то, может включать в себя другие объекты.

Что у вас здесь есть, так это то, что вы пытаетесь сделать, это топологический вид. Единственный способ, с помощью которого можно было бы использовать Comparator, - это сначала сделать топологическую сортировку, а затем использовать индексы объектов в этой сортировке как ключи при реализации компаратора. Но тогда, конечно, нет необходимости в компараторе, так как вы уже отсортировали элементы.

Answer 2

Нарушение договора Comparator мало что может вам помочь, поскольку стандартные алгоритмы сортировки предполагают, что вы его почитаете.

Помимо реализации топологического алгоритма сортировки из Википедии вы также можете посмотреть this lib (который часто упоминается, когда кто-то говорит о направленных графах и топологической сортировке) или that.