Сортировать коллекцию в цепочку по границам объекта

Question

Допустим, у нас есть эстафета. Каждый член команды идет своим путем, передавая палку следующему члену команды. У меня есть класс, который описывает номер трека (каждая команда имеет свой номер трека) и два имени. Первое имя является владельцем флешки для части трека N, а второе имя является владельцем флешки для следующей части трека (N + 1).

class StickTransfer {
    int trackId;
    String stickFrom;
    String stickTo;
}

Моя задача - отсортировать все объекты StickTransfer по 1) отслеживаемому 2) порядку перемещения палки.

например. Допустим, на треке 1 есть команда с Алексом -> Джоном -> Смитом -> Адамом.

list.add(new StickTransfer(1, "John", "Smith");
list.add(new StickTransfer(1, "Alex", "John");
list.add(new StickTransfer(1, "Smith", "Adam");

order(list)
// After that I want to get:
// Alex - John - first entry
// John - Smith - second entry
// Smith - Adam - third entry

Итак, сначала я решил использовать сортировку Java с таким компаратором:

Comparator.comparing(StickTransfer::getTrackId)
            .thenComparing((o1, o2) -> {
                if (o1.getStickFrom().equals(o2.getStickTo())) {
                    return 1;
                }
                if (o1.getStickTo().equals(o2.getStickFrom())) {
                    return -1;
                }
                return 0;
            });

Но у меня возникла проблема, что с этим компаратором некоторые записи все еще не отсортированы. Я думаю, это потому, что это не очень хороший компаратор.

Теперь у меня есть несколько вопросов:

1) Можно ли написать правильный компаратор для стандартного метода сортировки Java?

2) Если нет, есть ли способ решить эту проблему с помощью некоторых стандартных методов Java?

3) Есть ли название для такой алгоритмической задачи?

---

Пример неправильной сортировки: Правильный порядок: X -> Y -> A -> B -> C -> D -> E

    StickTransfer stickTransferArr[] = {
            new StickTransfer(1, "A", "B"),
            new StickTransfer(1, "C", "D"),
            new StickTransfer(1, "B", "C"),
            new StickTransfer(1, "X", "Y"),
            new StickTransfer(1, "Y", "A"),
            new StickTransfer(1, "D", "E")
    };

    Arrays.sort(stickTransferArr, cmp);

Результат:

[{track=1, [A - > B]}, {track=1, [B - > C]}, {track=1, [C - > D]}, {track=1, [X - > Y]}, {track=1, [Y - > A]}, {track=1, [D - > E]}]

Answer 1

3) Есть ли название для такой алгоритмической проблемы?

Ваша проблема называется топологическая сортировка .

1) Можно ли написать правильный компаратор для стандартного метода сортировки Java?

Нет.Если у вас есть более двух элементов, будут элементы, которые нельзя сравнивать напрямую.В вашем примере: StickTransfer(1, "Alex", "John") и StickTransfer(1, "Smith", "Adam") - что из этого приходит раньше?Невозможно узнать, не глядя на другие элементы.

2) Если нет, есть ли способ решить эту проблему с помощью некоторых стандартных методов Java?

Да, существует множество реализаций, например: Образец ориентированного графа и код топологической сортировки

По сути, вы можете использовать поиск по глубине в графе для его топологической сортировки.