如何获得在python中复制文件的正确顺序？

Question

我正在使用python来复制一些文件。但我无法获得正确的复制订单。

假设我有一个班级：

class Info:
    def __init__(self, source: str, destination: str):
        self.source = source
        self.destination = destination

我有一份Info列表。

复制令的规则是：

如果A.destination包含B.source，则将B放在A后面。

例如在这里，我们有三个Info

 Id        source         destination
Info1      Root/A    ->    Root/B/A
Info2      Root/B    ->    Root/D/B
Info3      Root/C    ->    Root/A/C

Info1.destination包含Info2.source，因此将Info2放在Info1后面，

Info3.destination包含Info1.source，因此将Info1置于Info3之后。

最后的订单是[Info3, Info1, Info2]

我认为最大的困难是一些Info无法比较。

有没有一些有效的算法来实现这一目标？谢谢！

Answer 1

你可以通过topological sort做到这一点，我在here找到一个版本：

from collections import deque
from collections import defaultdict

GRAY, BLACK = 0, 1

def topological(graph):
    order, enter, state = deque(), set(graph), {}

    def dfs(node):
        state[node] = GRAY
        for k in graph.get(node, ()):
            sk = state.get(k, None)
            if sk == GRAY: raise ValueError("cycle")
            if sk == BLACK: continue
            enter.discard(k)
            dfs(k)
        order.appendleft(node)
        state[node] = BLACK

    while enter: dfs(enter.pop())
    return order

测试代码：

graph = defaultdict(list)
graph['A'].append('B')
graph['B'].append('D')
graph['C'].append('A')

src_info = {'A': 'Info1', 'B': 'Info2', 'C': 'Info3'}
res = [src_info[c] for c in topological(graph) if c in src_info]

print(res)

输出：

['Info3', 'Info1', 'Info2']