依赖树实现

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。

Answer 4

这是我的工具，可以满足您的要求：

https://github.com/bedbad/pyimports

您可以使用文件和基本数据结构的 .ast 来创建任何您喜欢的树：

def get_imports(path):
imports = dict()
with open(path) as fh:
    root = ast.parse(fh.read(), path)
    for node in ast.iter_child_nodes(root):
        if isinstance(node, ast.Import):
            temp = imports
            for n in node.names:
                namelist = n.name.split('.')
                if len(namelist) > 1:
                    for st in namelist:
                        temp[st] = dict()
                        temp = temp[st]
                else:
                    temp[n.name] = dict()
        elif isinstance(node, ast.ImportFrom):
            temp = imports
            namelist = node.module.split('.')
            for n in namelist:
                temp[n] = dict()
                temp = temp[n]
            for n in node.names:
                temp[n.name] = dict()
        else:
            continue
return imports

请注意，Python 中的基本只是一个字典。尽管如此，据我所知，没有树 DS 实际上实现了对自循环的检查。那东西叫做Floyd-Warshall

Answer 5

1. 遍历旧的依赖树。构建其中所有元素的集合。
2. 遍历新的依赖树。和以前一样做。
3. 从前者中减去后者set。结果就是你的答案。

或者：

1. 遍历旧的依赖树。在每个节点上，存储依赖（指向）该节点的事物的数量。
2. 删除您要删除的项目。遵循其所有依赖项并将其使用计数减 1。如果以这种方式递减会将节点的计数降低到 0，则不再需要。

前者实现起来比较简单，但效率较低。后者虽然高效，但实施起来比较困难。

Answer 6

我认为您正在寻找的步骤是区分已明确安装的软件包和依赖项。完成此操作后，您可以构建所有请求软件包的依赖关系树，并将这些软件包集与已安装软件包集进行比较。假设所有请求的包都已安装，对这些进行异或，应该会给出不再依赖的所有包的集合。