如何解决模块依赖关系的 DAG？

Question

我正在使用 networkx 构建一个 DAG，表示我的几个模块之间的依赖关系。

考虑服装之间的依赖关系"modules":

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)

这意味着如果我想穿鞋，我需要已经穿上袜子和裤子。并且通过扩展，内裤（裤子的依赖）。

我现在想要一个函数，它需要 "module" 和 return 之前我必须运行的正确顺序的所有其他模块。

示例：

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

我确定存在这个问题，我只是不知道它的 algorithm/function 名称，对吗？

我认为通过 list(nx.topological_sort(G)) 获得的 拓扑顺序 几乎是我想要的。但是在这种情况下它会 return

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

所以如果我想穿袜子，这个结果会告诉我先穿衬衫、毛衣和外套（即使它们是可选的，但没有依赖性）。

Answer 1

查看深度优先搜索算法

Answer 2

我认为 DFS 方法可以完成任务。算法如下：

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

如何解决模块依赖关系的 DAG？

How to resolve a DAG of module dependencies?

python

algorithm

networkx

directed-acyclic-graphs