外部系统交易表排序问题：确保父元素先于子元素创建

这本质是一个依赖拓扑排序的问题，我们需要梳理未创建元素之间的依赖关系，确保每个子元素的所有未创建父元素都先被处理。已持久化的F、X、E可以视为“已就绪”的节点，不需要参与排序逻辑，只需要关注那些还没创建的元素之间的依赖链。

具体解决方案步骤： #

• 第一步：拆分并过滤依赖
  遍历交易表的每一行，把分号分隔的父元素拆成单个元素，然后过滤掉已经持久化的（F/X/E）——因为这些元素已经存在，不需要考虑创建顺序。只保留未创建的父元素，建立子元素到这些父元素的依赖关系。

• 第二步：构建依赖图与入度表
  用一个图来记录每个未创建元素的子元素（即谁依赖它），同时用入度表记录每个未创建元素有多少个未创建的父元素需要先处理。比如子元素A依赖未创建的B，那么B的邻接列表要加上A，A的入度加1。

• 第三步：执行拓扑排序（Kahn算法）

  1. 先把所有入度为0的元素（没有未创建父元素，只依赖已持久化元素）加入队列。
  2. 依次取出队列中的元素，加入排序结果，然后把它的所有子元素的入度减1——因为这个父元素已经处理完成了。
  3. 如果某个子元素的入度减到0，说明它的所有未创建父元素都处理完了，把它加入队列。
  4. 最后检查排序结果的长度是否等于未创建元素的总数，如果不等，说明存在循环依赖（比如A依赖B，B又依赖A），这种情况无法满足排序要求，需要修正数据。

示例代码实现（伪代码） #

from collections import deque

# 模拟交易表数据
transaction_data = [
    {"child": "A", "parents": "B;F"},
    {"child": "B", "parents": "E;C"},
    {"child": "C", "parents": "X"}
]
persisted_elements = {"F", "X", "E"}

# 初始化依赖图和入度表
dependency_graph = {}
in_degree_count = {}

for entry in transaction_data:
    child = entry["child"]
    # 初始化子元素的图和入度
    if child not in dependency_graph:
        dependency_graph[child] = []
        in_degree_count[child] = 0
    # 处理每个父元素
    for parent in entry["parents"].split(";"):
        if parent not in persisted_elements:
            # 初始化父元素（如果还没在图里）
            if parent not in dependency_graph:
                dependency_graph[parent] = []
                in_degree_count[parent] = 0
            # 父元素指向子元素，子元素入度+1
            dependency_graph[parent].append(child)
            in_degree_count[child] += 1

# 拓扑排序流程
processing_queue = deque()
# 先加入所有入度为0的节点
for element in in_degree_count:
    if in_degree_count[element] == 0:
        processing_queue.append(element)

creation_order = []
while processing_queue:
    current_element = processing_queue.popleft()
    creation_order.append(current_element)
    # 更新子元素的入度
    for dependent_child in dependency_graph[current_element]:
        in_degree_count[dependent_child] -= 1
        if in_degree_count[dependent_child] == 0:
            processing_queue.append(dependent_child)

# 检查循环依赖
if len(creation_order) != len(in_degree_count):
    raise ValueError("检测到循环依赖，无法生成合法的创建顺序，请检查交易表数据")

print("推荐的创建顺序:", creation_order)  # 输出: ['C', 'B', 'A']

关键注意点： #

• 已持久化元素不需要加入依赖图，因为它们已经存在，不影响创建顺序。
• 必须处理循环依赖的情况，这种场景下没有合法的排序，需要人工修正交易表中的依赖关系。
• 如果交易表中有孤立的元素（没有任何父元素，或者父元素都已持久化），它们会被优先加入队列，可以随时创建。

内容的提问来源于stack exchange，提问作者Iqbal