Python 中的广度优先搜索（BFS）用于分割 dag 节点

Question

我尝试在 python 中实现面包优先搜索算法来分割 dag，我的目标是分割节点依赖项，以便对于具有多个依赖项的每个节点，我将复制该节点直到它具有一个依赖项，例如对于这个 dag：

示例 dag

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

)

如何在Python上实现这个？

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

Answer 1

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)