Чистый алгоритм сортировки объектов по определенным зависимостям?

Question

Дан список классов, унаследованных от этой базы:

class Plugin(object):
    run_after_plugins = ()
    run_before_plugins = ()

... и следующие правила:

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

Может кто-нибудь предоставить хороший чистый алгоритм для заказа списка плагинов? Также необходимо будет определить круговые зависимости ....

 def order_plugins(plugins):
      pass

Я придумал несколько версий, но ничего особенного: я уверен, что некоторые из вас Искусство компьютерного программирования типов получат удовольствие:)

[примечание: вопрос задан в Python, но это явно не только вопрос Python: подойдет псевдокод на любом языке]

Answer 1

Это называется топологическая сортировка .

Каноническое применение топологическая сортировка (топологическая порядок) в планировании последовательности рабочие места или задачи; топологическая сортировка Алгоритмы были впервые изучены в начале 1960-х годов в контексте PERT Техника для планирования в проекте менеджмент (Ярнагин, 1960). Работы представлены вершинами, и там это ребро от х до у, если задание х должно быть завершено до того, как работа у может быть началось (например, при стирке одежда, стиральная машина должна закончить, прежде чем положить одежду сухой). Затем топологическая сортировка дает порядок выполнения заданий.

Answer 2

Здесь - это код Python, который выполняет топологическую сортировку.

Answer 3

Это называется топологическая сортировка .

Для этого необходимо выполнить несколько шагов:

Сначала создайте график всех выбранных плагинов в виде вершин и их зависимостей в виде ребер. Запустите до / после того, как капли упадут к краям того же типа.

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

Последний шаг: выберите вершину без входящих ребер и выполните поиск DFS (или BFS). Эти алгоритмы могут быть обогащены циклом обнаружения.

Answer 4

Если вы хотите дать хорошую диагностику для случая, когда есть циклы, взгляните на http://en.wikipedia.org/wiki/Strongly_connected_component. Я думаю, что если вы используете версию Сильно подключенного компонента, такую ​​как описанная в http://www.cs.sunysb.edu/~skiena/373/notes/lecture16/lecture16.html вы можете распечатать сильно связанные компоненты в топологическом порядке сортировки.

Answer 5

Если вы определите __lt__ и связанные с ним методы в плагине на основе того, должны ли они выполняться до или после этого, можно было бы найти разумный порядок с sorted().Циклы все еще были бы проблемой, хотя.