Python 递归找上游

#背景
cur_table source_table
A C
A B
B D
D E
… …
现在有一张表，里面存着两个字段，cur_table代表现有的表，source_table代表现在的表对应的上游表；如图，表A对应的上游表有C和B，B对应的上游表为D，D对应的上游表为E；

#问题
通过Ptyhon 或者 SQL，实现找到现有表的所有上游相关表；
如
A：C,B,D,E
B：D,E
D：E

背景列的只是举例，实际表中，现有表相关的血缘关系可能有上百层；本人目前会使用SQL，重复left join的笨办法，不能解决血缘关系数量多的情景；

  • 下列程序从标准输入读取字符串，直到遇到空行为止。每行的格式为 "当前表 上游表"，用一个空格隔开。例如，"table1 table2" 表示 "table1" 表依赖于 "table2" 表。

  • 接下来，程序遍历字典的每个键，并计算出那些表是这个表的下游表（即依赖于这个表的表）。为了计算下游表，程序从当前表开始，递归地搜索上游表，直到所有的上游表都被搜索完为止。最后，将计算出的下游表集合更新到字典中。

  • 最后，程序打印出构建的字典。结果应该是每个表及其所有下游表的列表。

# 建立空字典，用于存储每个表格的来源
upstream_tables = {}

# 逐行读入字符串
for index, row in df.iterrows():
    # 拆分为两个单词
    cur_table, source_table = row[0], row[1]
    # 为当前表格建立来源集合，或将来源表格加入来源集合
    upstream_tables.setdefault(cur_table, set()).add(source_table)

# 遍历所有表格
for key in upstream_tables.keys():
    # 取出当前表格的来源表格集合
    downstream_table = upstream_tables[key]
    # 建立临时集合，用于存储间接来源表格
    temp = set()
    # 当来源表格集合不为空时
    while downstream_table:
        # 取出来源表格集合中的一个表格
        a = downstream_table.pop()
        # 将其加入临时集合
        temp.add(a)
        # 如果这个表格还有来源表格
        if a in upstream_tables:
            # 将这些来源表格加入来源表格集合
            downstream_table.update(upstream_tables[a])
    # 将临时集合存回字典
    upstream_tables[key] = temp

# 输出上游表
print(upstream_tables)
# 输出结果df
res_df = pd.DataFrame({'cur_table': upstream_tables.keys(), 'source_table': upstream_tables.values()})

def find_upstream_tables(cur_table, source_table):
    # 定义结果列表
    result = []
    # 查询 source_table 表中，是否有 cur_table 这个表
    query = "SELECT * FROM source_table WHERE cur_table = '%s'" % cur_table
    rows = execute_query(query)
    # 如果有，则递归调用 find_upstream_tables 函数
    for row in rows:
        upstream_table = row['source_table']
        result.extend(find_upstream_tables(upstream_table, source_table))
    # 将当前表加入到结果列表中
    result.append(cur_table)
    return result

# 调用 find_upstream_tables 函数
result = find_upstream_tables('A', 'source_table')
print(result)

这不就是DAG吗。首先，要确保数据是否有错误的情况，比如A的上游是B，B的上游是A；还有数据是否有独立的情况，比如A的上游是B，C的上游是D，但是A与C之间、B与D之间没有关系。也就是说是否会成环或成多棵树。
如果不存在上述问题，直接遍历关系，先找出父-子树，然后遍历该树，建立祖先树

tree = {}
while True:
    s = input()
    if s == "": break
    cur_table, source_table = s.split()
    tree.setdefault(cur_table, set()).add(source_table)
for key in tree.keys():
    son = tree[key]
    temp = set()
    while son:
        a = son.pop()
        temp.add(a)
        if a in tree:
            son.update(tree[a])
    tree[key] = temp
print(tree)