代码之家  ›  专栏  ›  技术社区  ›  Alexander Engelhardt

如何解决模块依赖的DAG?

  •  0
  • Alexander Engelhardt  · 技术社区  · 6 年前

    我正在使用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)
    

    enter image description here

    我现在想要一个函数,它接受一个“module”,并以正确的顺序返回我之前必须运行的所有其他模块。

    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']
    

    所以如果我想穿袜子,这个结果会告诉我先穿衬衫、毛衣和外套(尽管它们是可选的,但没有依赖性)。

    2 回复  |  直到 6 年前
        1
  •  1
  •   peterhzsti    6 年前

    查看深度优先搜索算法

        2
  •  1
  •   nightfury1204    6 年前

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

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