Сортировка порядка выполнения метода в Java

Question

Я давно застал эту проблему и не смог найти помощь в другом месте в Интернете, поэтому это может оказаться полезным для кого-то еще позже.

У меня есть список слов, и каждое слово в списке имеет свои собственные два массива слов, которые должны идти до и после.

Вот пример:

"forest" - before:{"tree"} 
"frog" - after:{"mushroom"} 
"mushroom" 
"leaf" - after:{"mushroom"}, before: {"frog"} 
"tree" - before:{"mushroom"} 

Эти слова должны быть упорядочены в следующем порядке: лес, дерево, грибы, листья, лягушки. Таким образом, в принципе, «после» не означает, что слово должно идти сразу после другого (и не «до»), оно просто не может идти перед словом (или в случае «до»).

Я попытался решить эту проблему, используя списки массивов и добавление элементов в пользовательские индексы, которые разбиваются, как только вставлен элемент, такой как «лист» (элемент, который находится между двумя другими элементами).

Этот пример упрощен, поэтому он никого не смущает, я на самом деле пишу модный загрузчик, который сортирует методы, аннотация которых указывает, какие моды они должны выполнять после/до.

EDIT: Мне удалось решить проблему, обратившись до конца на элементы, содержащиеся перед массивами.

После этого все, что я сделал, это перебрать все элементы, а затем проверить, был ли этот элемент уже выполнен (вы увидите, почему в секунду), если он не был выполнен, выполните все после того, как элементы сначала в том же и затем выполнить фактический элемент. Я также делаю некоторые проверки для предотвращения циклов и т. Д.

Answer 1

Я не буду писать код для вас, но я опишу некоторые намеки на алгоритм.

Первое, что нужно понимать, что нет никакого смысла в after информации, потому что говорят, что B приходит после того, как A то же самое, как говорят A идет перед B. Начните с замены всей информации after на эквивалентную информацию before.

Далее вы должны понимать, что если элемент находится в одном из массивов before, он не может быть первым. Таким образом, вам нужно просмотреть все массивы before, чтобы найти элемент ни в одном из них. Если в любом из этих массивов нет элемента, этот элемент может идти первым. (Если нет, проблема невозможна).

После того, как вы решили, какой элемент идет первым, отбросьте массив before и заполните список, используя рекурсию.

Answer 2

Это пример проблемы Topological Sort.

Имена методов можно рассматривать как узлы в графе, а ваши отношения «до» и «после» - это направленные ребра в указанном графе.