什么是 python 用于在非二叉树中列出祖先的后代的递归方法？

Question

我是使用 Python 的初学者。我有一个包含家谱的 MS Access 数据库。我希望使用 Python 来查询家谱以列出已识别祖先的所有后代。家谱保存在 table 我已经导出到 excel。它包含三列：关系 ID、Node1_ID、Node2_ID。每行中列出的关系是从 Node1_ID 到 Node2_ID 的单向关系。树是非二进制的，因此树可以有几个 Node2_ID 从 Node1_ID.

下降

婚姻中处于 Node1_ID 位置的每个伴侣都与 Node2_ID 中的同一个伙伴关系节点相关（在下面的示例中，父节点 1 和 2 与伙伴关系节点 3 相关）。伙伴关系节点然后与子节点相关（例如，伙伴关系节点 3 连接到子节点 4、5 和 6）。

RID	Node1_ID	Node2_ID
1	1	3
2	2	3
3	3	4
4	3	5
5	3	6

我希望使用代码调用 excel 电子表格，并允许我通过递归查询特定节点的所有后代的列表。然后我希望将该列表写入一个新的 excel 文件，我可以将该文件导入回我的 MS Access 数据库或在其他软件（如 GraphViz）中进行可视化。

在网上搜索时，我遇到了以下代码，似乎可以解决问题：

import pandas as pd
import sys
sys.setrecursionlimit(100000000)

df = pd.read_excel(r'excelfilepath')
columns = df.columns.ravel()

def get_ancestry_dataframe_flat(df):

    def get_child_list(parent_id):

        list_of_children = list()
        list_of_children.append(df[df['P1ID'] == parent_id]['P2ID'].values)

        for i, r in df[df['P1ID'] == parent_id].iterrows():
            if r['P2ID'] != parent_id:
                list_of_children.append(get_child_list(r['P2ID']))

        # flatten list
        list_of_children = [item for sublist in list_of_children for item in sublist]
        return list_of_children

    new_df = pd.DataFrame(columns=['descendant', 'ancestor']).astype(int)
    for index, row in df.iterrows():
        temp_df = pd.DataFrame(columns=['descendant', 'ancestor'])
        temp_df['descendant'] = pd.Series(get_child_list(row['P1ID']))
        temp_df['ancestor'] = row['P1ID']
        new_df = new_df.append(temp_df)

    new_df = new_df\
        .drop_duplicates()\
        .sort_values(['ancestor', 'descendant'])\
        .reset_index(drop=True)

    return new_df

writer = pd.ExcelWriter('20210408_descendant_relationships.xlsx',engine='xlsxwriter')
get_ancestry_dataframe_flat(df).to_excel(writer,sheet_name='Sheet1')
writer.save()

这段代码的问题是，我在创建所有祖先的后代列表时似乎达到了递归限制（家谱相当大）。因此，我希望只查询特定祖先的后代。我可以做哪些编辑来做到这一点？除了递归限制问题，我仍然想识别特定祖先的后代。

我是 Python 的初学者，所以如果可能的话，我将不胜感激。谢谢你的时间。

编辑：来自 @Ajax1234

建议的代码


import pandas as pd
from collections import deque

df = pd.read_excel('input.xlsx')
tree = df.values.tolist()

def get_ancestors(node):
   d, seen = deque([node]), set()
   while d:
      yield (n:=d.popleft())
      seen.add(n)
      d.extend([int(c) for _, b, c in tree if int(b) == int(n)])

r = dict([(next(n:=get_ancestors(i)), list(n)) for i in set([t[1] for t in tree])])
vals = [[[a, i] for i in b] for a, b in r.items()]
df1 = pd.DataFrame([dict(zip(['node', 'descendent'], i)) for i in vals])

print(r)

df1.to_excel('output.xlsx')

预期输出 excel table 应该是这样的：

Node	Descendant
1	3
1	4
1	5
1	6
2	3
2	4
2	5
2	6
3	4
3	5
3	6

Answer 1

可以使用广度优先搜索的非递归解决方案：

from collections import deque
tree = [[1, 1, 3], [2, 2, 3], [3, 3, 4], [4, 3, 5], [5, 3, 6]]
def get_ancestors(node):
   d, seen = deque([node]), set()
   while d:
      yield (n:=d.popleft())
      seen.add(n)
      d.extend([int(c) for _, b, c in tree if int(b) == int(n)])

get_ancestors 接收一个节点并通过广度优先搜索生成该节点的所有后代。例如，要获取 node1_id 的所有后代：

r = dict([(next(n:=get_ancestors(i)), list(n)) for i in set([t[1] for t in tree])])

输出：

{1: [3, 4, 5, 6], 2: [3, 4, 5, 6], 3: [4, 5, 6]}

编辑：写入 Excel:

writer = pd.ExcelWriter('20210408_descendant_relationships.xlsx',engine='xlsxwriter')
df = pd.read_excel(writer, 'sheet1')
tree = df.values.tolist()
r = dict([(next(n:=get_ancestors(i)), list(n)) for i in set([t[1] for t in tree])])
vals = [[a, i] for a, b in r.items() for i in b]
df1 = pd.DataFrame([dict(zip(['node', 'descendent'], i) for i in vals])
df1.to_excel(writer)

什么是 python 用于在非二叉树中列出祖先的后代的递归方法？

What is a python recursion method for listing descendants from an ancestor in a non-binary tree?

python

recursion

hierarchy

family-tree