依赖树实现

Question

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

我正在努力理解这背后的理论,并可能实现我自己的版本.我做了一些谷歌搜索,提出了大多数耦合的东西.根据我的理解,耦合是两个相互依赖的类/模块.这不是我正在寻找的.我正在寻找的更像是依赖树生成,在那里我可以找到最少依赖的模块(我已经做了这样的递归方式),并且(这是我没有做过的部分)找到什么是删除节点后不再需要.

还有,学习图论有用吗？是否有任何教程,最好使用Python作为语言？

Answer 1

这可能有一些兴趣:

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 2

图论是要走的路。

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

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

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

形式上，图只是顶点和（有序）顶点对的集合，称为边。您需要一种称为“拓扑排序”的图算法，现在您需要阅读一些内容。

Answer 3

我确实编写了一个工具，用于查找和绘制 PyPi 上的 Python 包之间的依赖关系。就是贪吃

我确实用来分析我正在使用的一些库的依赖关系。以下是一些图表：

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

谈谈我是如何实现的，为了查找包依赖关系，我使用pip作为后端。为了绘制图表，我使用Networkx。