Сортировка по зависимостям

Question

Есть список объектов, у них есть поле, в котором указаны зависимости


class A:
    dependencies = []

class B:
    dependencies = []

class C:
    dependencies = [A]

class D:
    dependencies = [B]

class E:
    dependencies = [A, B, C]

class F:
    dependencies = [E]

class G:
    dependencies = [F]

Изначально весь набор объектов валиден, все объекты в зависимостях имеются, нет цикличности.

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

Порядок должен быть такой:

Объект встает в список если все зависимости уже добавлены
Если нет какой либо зависимости, ждем пока она появится
Если не осталось объектов с полными зависимостями, то добавляем объекты независимые от уже добавленных
см п 1 (по кругу) пока изначальный список не будет полностью в новом

Подскажите алгоритм?

Примеры входных/выходных данных

> [A, C, E, B, D]
< [A, B, C, D, E] или [A, B, D, C, E]

> [B, E, A, D, G, F]
< [B, A, D, E, F, G]

Предполагаю, сначала надо пройтись по объектам и записать, какие объекты зависят от них, и смотреть исходя из этих данных

Answer 1

На основе полученных комментарием, нашел библиотеку для топологической сортировки.

>>> import graphlib
>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = graphlib.TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

Это решило проблему без костылизации и велосепедолизации

Спасибо

БЛОГ НА HUSL

Сортировка по зависимостям

Ответы (1 шт):