Python实现：从树/DAG根节点查找符合条件的父节点

问题描述 #

给定如下数据集，构成带权有向无环图（DAG），其中A是最终子节点：

Child Parent Ownership  Parent_Country
  A     B      0.1      Foreign
  A     C      0.3      Domestic
  A     D      0.6      Domestic
  B     E      0.4      Domestic
  B     F      0.6      Foreign
  H     J       1       Foreign
  C     G      0.9      Foreign
  A     G      0.05     Foreign
  D     H      0.8      Foreign
  D     I      0.2      Domestic

需要找出满足以下条件的父节点：

• 直接或间接持有A的所有权≥30%
• 属于外国（Foreign）节点
• 是路径上第一个满足所有权条件的外国父节点，上层符合条件的节点不计入

期望输出：

{'A':[('G',0.33),('H',0.48)]}

注：G的所有权计算为0.9*0.3 + 0.05 = 0.33，H的所有权为0.8*0.6 = 0.48；J虽然间接持有A的48%，但因H更接近A，故J不符合条件。

已尝试方案 #

将DataFrame转换为DAG字典存储子节点对应的父节点、所有权及国家，尝试用深度优先搜索（DFS）计算所有权，但遇到以下问题：

1. 无法正确构建以A为键、符合条件的节点-所有权对为值的输出字典
2. 无法在路径中遇到第一个符合条件的外国节点时终止该路径遍历，同时不影响其他路径
3. 未正确处理同一节点的多路径所有权累加

已编写的代码：

import pandas as pd
from collections import defaultdict

df=pd.DataFrame({'Child': list('AAABBHCADD'), 'Parent': list('BCDEFJGGHI'), 'Ownership': [.1,.3,.6,.4,.6,1,.9,.05,.8,.2],'Parent_Country':('Foreign','Domestic','Domestic','Domestic','Foreign','Foreign','Foreign','Foreign','Foreign','Domestic')})

#Create a dict appending all the parents to each child
dag_as_dict = defaultdict(list) # {child: list of (parent, weight)}
for idx, row in df.iterrows():
    dag_as_dict[row['Child']].append((row['Parent'], row['Ownership'],row['Parent_Country']))

#Calculate ultimate ownership in A for every parent
def get_weights_of_descendants(dag_as_dict, root, root_weight=1.0, country='Domestic', result=None,real_parent=None):
    if result is None:
        result = defaultdict(float)
    if real_parent is None:
        real_parent=defaultdict(str)
    for parent, weight, country in dag_as_dict[root]:
        new_weight=weight*root_weight
        result[parent] += new_weight
        if result[parent]>0.3 and country!='Domestic':
            real_parent[root]=parent
            break
        get_weights_of_descendants(dag_as_dict, parent, new_weight, country,result,real_parent)            
    return real_parent
#    return result

解决方案 #

核心思路：通过DFS遍历所有从A出发的路径，跟踪每条路径的所有权乘积；遇到外国节点时，累计该节点的总所有权，若达到≥30%则记录并终止当前路径；最后整理输出格式。

完整代码 #

import pandas as pd
from collections import defaultdict

df = pd.DataFrame({
    'Child': list('AAABBHCADD'),
    'Parent': list('BCDEFJGGHI'),
    'Ownership': [.1, .3, .6, .4, .6, 1, .9, .05, .8, .2],
    'Parent_Country': ('Foreign', 'Domestic', 'Domestic', 'Domestic', 'Foreign', 'Foreign', 'Foreign', 'Foreign', 'Foreign', 'Domestic')
})

# 构建DAG字典：子节点 -> [(父节点, 所有权, 国家), ...]
dag = defaultdict(list)
for _, row in df.iterrows():
    dag[row['Child']].append((row['Parent'], row['Ownership'], row['Parent_Country']))

def find_target_nodes(dag, root):
    # 存储符合条件的节点及其总所有权
    target_weights = defaultdict(float)
    # 记录已处理的节点（避免重复遍历路径）
    processed = set()

    def dfs(current_node, current_weight):
        if current_node in processed:
            return
        # 遍历当前节点的所有父节点
        for parent, weight, country in dag.get(current_node, []):
            new_weight = current_weight * weight
            # 如果是外国节点，先累加所有权
            if country == 'Foreign':
                target_weights[parent] += new_weight
                # 检查是否满足所有权条件，满足则终止该路径
                if target_weights[parent] >= 0.3:
                    processed.add(parent)
                    continue
            # 继续遍历父节点的上层，直到遇到符合条件的外国节点或无父节点
            dfs(parent, new_weight)
    
    # 从根节点A开始遍历，初始所有权为1（A对自己的所有权是100%）
    dfs(root, 1.0)
    
    # 筛选出所有权≥0.3的节点，并保留两位小数
    result = [(node, round(weight, 2)) for node, weight in target_weights.items() if weight >= 0.3]
    # 整理成期望的输出格式
    return {root: result}

# 执行并打印结果
output = find_target_nodes(dag, 'A')
print(output)

代码解释 #

1. DAG构建：将DataFrame转换为字典，方便快速查找每个子节点的父节点信息。
2. DFS遍历：
   • 从根节点A出发，初始所有权为1.0（代表A的100%所有权）
   • 每条路径上，所有权按父节点的持有比例累乘
   • 遇到外国节点时，累加其对A的所有权；若累加后≥30%，则标记该节点为已处理，终止当前路径的后续遍历
3. 结果整理：筛选出所有权≥0.3的节点，保留两位小数后整理成期望的字典格式。

运行代码后将输出：

{'A': [('G', 0.33), ('H', 0.48)]}

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