依赖关系树实现

Question

对于那些使用apt-get的人，你知道每次你安装/卸载某个东西时，你都会收到通知说你需要/不再需要某些依赖项。

我试图理解这个理论的背后，并可能实现我自己的版本。我做了一些谷歌搜索，找到了大部分耦合的东西。据我所知，耦合是两个相互依赖的类/模块。这不是我要找的。我所寻找的更像是一个依赖树生成，在这里我可以找到最不依赖的模块（我已经做了一个递归的方法），并且（这是我没有做的部分）找到删除节点后不再需要的东西。

另外，学习图论有帮助吗？有没有关于使用Python作为语言的教程？

Answer 1

我确实编写了一个工具来查找和绘制PyPi上Python包之间的依赖关系。是gluttony

我也曾经分析过我正在使用的库的依赖关系。以下是一些图表：

我不确定这是你想要的。如果是，可以读取源代码here，这是一个开源项目。对于更多依赖关系图，可以查看gallery

谈到如何实现它，为了查找包依赖项，我使用pip作为后端。对于绘制图表，我使用Networkx。

Answer 2

This可能会引起一些兴趣：

def dep(arg):
    '''
        Dependency resolver

    "arg" is a dependency dictionary in which
    the values are the dependencies of their respective keys.
    '''
    d=dict((k, set(arg[k])) for k in arg)
    r=[]
    while d:
        # values not in keys (items without dep)
        t=set(i for v in d.values() for i in v)-set(d.keys())
        # and keys without value (items without dep)
        t.update(k for k, v in d.items() if not v)
        # can be done right away
        r.append(t)
        # and cleaned up
        d=dict(((k, v-t) for k, v in d.items() if v))
    return r

if __name__=='__main__':
    d=dict(
        a=('b','c'),
        b=('c','d'),
        e=(),
        f=('c','e'),
        g=('h','f'),
        i=('f',)
    )
    print dep(d)

Answer 3

图论是一条路。

图只是一堆中间有路（边）的地方（顶点），特别是我们所说的有向图，意思是单向路。找出依赖关系，基本上意味着，找出所有的地方，可以到达一个特定的城镇沿着单行道。

现在，你得到了一堆模块，它们成为你的顶点。假设我们有A和B，我们知道B依赖于A，所以有一条有方向的边——一条“单行道”——从A到B

如果C依赖于B，那么你有A→B→C

在形式上，图只是顶点和（有序的）顶点对的集合，称为边。你想要一个叫做“拓扑排序”的图算法，现在你有一些东西要读。