graph - 图：节点依赖

Question

我有一个这样的图表：

例如，我想知道节点 8 的依赖关系是： 1,2,3,5 。有人可以给我一些代码或者可能是伪代码来解决这个问题吗？

谢谢

Answer 1

依赖结构是一个偏序集。我有类似的案例，我用 2 种方法（在 python 中）介绍了它：

• nodes_to_update( to_proc )参数是一组开始的节点（例如 set([8])）。返回两组节点：给定节点所依赖的所有节点集和叶节点集。想法是递归访问依赖访问节点的所有节点。
• sequence_to_update( to_proc )参数如上。返回（有序）节点列表，以便列表中的节点仅依赖于列表中之前的节点。它是通过将叶节点添加到有序列表中并更新要处理的节点集（所有和叶节点）来完成的。

依赖节点是 get with 方法down_nodes(o_id)，依赖的节点是 get with up_nodes(o_id)。

def nodes_to_update(self, to_proc):
    all_to_update, first_to_update = set(), set()
    while to_proc:
        n = to_proc.pop()
        all_to_update.add(n)
        ds = self.down_nodes(n)  # nodes on which n depends
        if not ds:
            first_to_update.add(n)
        else:
            to_proc.update(ds)
    return all_to_update, first_to_update

def sequence_to_update(self, to_proc):
    all_to_update, first_to_update = self.nodes_to_update(to_proc)
    update_in_order = []
    while first_to_update:
        n_id = first_to_update.pop()
        all_to_update.discard(n_id)
        update_in_order.append(n_id)
        # nodes which depend on n_id (intersection of upper nodes and all nodes to update)
        for up_id in (self.up_nodes(n_id) & all_to_update):
            if all(d not in all_to_update for d in self.down_nodes(up_id)):
                first_to_update.add(up_id)
    return update_in_order