Как разрешить DAG модульных зависимостей?

Question

Я использую networkx для создания DAG, представляющей зависимости между несколькими моими модулями.

Рассмотрим зависимости между «модулями» одежды:

import networkx as nx
dependencies = {
    'underpants': [],
    'socks': [],
    'pants': ['underpants'],
    'shirt': [],
    'sweater': ['shirt'],
    'coat': ['shirt', 'sweater'],
    'shoes': ['socks', 'pants']
}
modules = dependencies.keys()

G = nx.DiGraph()

for mod in modules:
    G.add_node(mod)

for mod, deps in dependencies.items():
    for dep in deps:
        G.add_edge(mod, dep)

nx.draw_networkx(G)

Это значит, что если я хочу надеть туфли, мне нужно уже надеть носки и брюки тоже. И, соответственно, трусы (зависимость от штанов).

Теперь мне нужна функция, которая принимает «модуль» и возвращает все остальные модули в правильной последовательности, которую я должен был выполнить раньше.

Примеры:

prerequisites("pants") == ["underpants"]
prerequisites("underpants") == []
prerequisites("shoes") == ["underpants", "pants", "socks"]  # or: ["socks", "underpants", "pants"] would also work.

Я уверен, что эта проблема существует, и я просто не знаю название алгоритма / функции для нее, верно?

Я думаю, что топологический порядок , полученный с помощью list(nx.topological_sort(G)), - почти то, что я хочу. Однако в этом случае он вернет

['shirt', 'sweater', 'coat', 'socks', 'underpants', 'pants', 'shoes']

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

Answer 1

Я думаю, что подход DFS сделает задачу. Алгоритм приведен ниже:

FindDependencies( module ) {
    ans = []
    for d in dependencies[module] {
        ans = append(ans, FindDependencies(d))
    }
    ans = append(ans, module)
    return ans
}

Answer 2

Проверьте алгоритм поиска в глубину