在 python 中分割 dag 依赖关系

Question

在 Python 中拆分 dag 依赖项

我尝试实现一个用于拆分 dag 依赖项的脚本，我的目标是拆分节点依赖项，以便对于具有多个依赖项的每个节点，我将复制该节点，直到它具有一个依赖项 （复制节点的子依赖也需要复制）， 我尝试使用面包优先搜索算法，但我不确定这是否是正确的方法。

例如对于这个 dag： [示例 dag]：(https://i.sstatic.net/WqgJoDwX.png)

我期望得到以下结果：(https://i.sstatic.net/829jW9yT.png)

假设我在字典共振峰中提供了以下 dag 依赖项：

    dag_dependencies = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E', 'F'],
    'E': [],
    'F': [],
}

我期望得到：

    expected_dag_dependencies = {
    'A': ['B', 'C'],
    'B': ['D1'],
    'C': ['D2'],
    'D1': ['E1', 'F1'],
    'D2': ['E2', 'F2'],
    'E1': [],
    'F1': [],
    'E2': [],
    'F2': [],
}

如何在Python上实现这个？

Answer 1

按原样运行脚本以查看打印的原始和分割的 DAG 结构。您也可以根据您的用例进行修改（如果有）。

from collections import deque

class Node:
    def __init__(self, name):
        self.name = name
        self.children = []
        self.parents = []

def split_dag(root):
    queue = deque([root])
    visited = set()
    new_nodes = {}

    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)

        for child in node.children:
            if len(child.parents) > 1:
                # Create a new node
                new_name = f"{child.name}_{node.name}"
                if new_name not in new_nodes:
                    new_nodes[new_name] = Node(new_name)
                new_node = new_nodes[new_name]

                # Update relationships
                new_node.children = child.children.copy()
                node.children[node.children.index(child)] = new_node
                new_node.parents = [node]

                # Update child's relationships
                child.parents.remove(node)
                for grandchild in child.children:
                    grandchild.parents.append(new_node)

                queue.append(new_node)
            else:
                queue.append(child)

    return root

# Helper function to create the initial DAG
def create_dag():
    nodes = {name: Node(name) for name in 'ABCD1D2E1F1E2F2'}
    
    edges = [
        ('A', 'C'), ('A', 'B'),
        ('C', 'D1'), ('B', 'D2'),
        ('D1', 'E1'), ('D1', 'F1'),
        ('D2', 'E2'), ('D2', 'F2')
    ]

    for parent, child in edges:
        nodes[parent].children.append(nodes[child])
        nodes[child].parents.append(nodes[parent])

    return nodes['A']

# Function to print the DAG structure
def print_dag(root, prefix=""):
    print(f"{prefix}{root.name}")
    for child in root.children:
        print_dag(child, prefix + "  ")

# Main execution
root = create_dag()
print("Original DAG:")
print_dag(root)

split_root = split_dag(root)
print("\nSplit DAG:")
print_dag(split_root)