依赖树实现

Question

如果你用过apt-get，你就知道每次安装或卸载软件时，系统会通知你需要或不再需要某些依赖项。

我想了解这个背后的原理，并可能自己实现一个类似的功能。我查了一些资料，发现大多数内容都是关于耦合的。从我理解的来看，耦合是指两个类或模块相互依赖。这并不是我想要的。我想要的是生成一个依赖树，这样我可以找到依赖最少的模块（我已经做了一个递归的方法来实现这一点），而且（这部分我还没做）在移除一个节点后找到哪些东西不再需要。

另外，学习图论会有帮助吗？有没有关于这方面的教程，最好是用Python作为编程语言的？

Answer 1

我写了一个工具，可以帮助找到并绘制Python包在PyPi上的依赖关系。这个工具叫做gluttony。

我用它来分析我正在使用的一些库的依赖关系。下面是一些图示：

我不确定这是否是你想要的。如果是的话，你可以在这里查看源代码，它是一个开源项目。想看更多的依赖关系图，可以去图库。

说到我是怎么实现这个的，找包的依赖关系时，我使用了pip作为后端。绘制图示时，我用的是Networkx。

Answer 2

这可能会引起你的兴趣：

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的关系。

正式来说，图就是一组顶点和它们之间的有序对，称为边。你需要用到一个叫“拓扑排序”的图算法，现在你可以去了解一下这个内容。