回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我正在使用networkx构建一个DAG,它表示我的几个模块之间的依赖关系。你知道吗</p>
<p>考虑服装“模块”之间的依赖关系:</p>
<pre><code>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)
</code></pre>
<p><a href="https://i.stack.imgur.com/Z3nns.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Z3nns.png" alt="enter image description here"/></a></p>
<p>这意味着如果我想穿上鞋子,我需要已经穿上袜子,还有裤子。延伸到内裤(裤子的附属品)。你知道吗</p>
<p>我现在想要一个函数,它接受一个“module”,并以正确的顺序返回我之前必须运行的所有其他模块。你知道吗</p>
<p>示例:</p>
<pre><code>prerequisites("pants") == ["underpants"]
prerequisites("underpants") == []
prerequisites("shoes") == ["underpants", "pants", "socks"] # or: ["socks", "underpants", "pants"] would also work.
</code></pre>
<p>我肯定这个问题存在,我只是不知道它的算法/函数名,对吗?你知道吗</p>
<p>我认为通过<code>list(nx.topological_sort(G))</code>获得的拓扑序几乎就是我想要的。但在这种情况下,它会返回</p>
<pre><code>['shirt', 'sweater', 'coat', 'socks', 'underpants', 'pants', 'shoes']
</code></pre>
<p>所以如果我想穿袜子,这个结果会告诉我先穿衬衫、毛衣和外套(尽管它们是可选的,但没有依赖性)。你知道吗</p>