给定根，如何在Python中基于条件查找树/有向无环图的端点

8fq7wneg 于 2023-02-18 发布在 Python

关注(0)|答案(2)|浏览(133)

问题的详细信息：

我有一个数据集，如下所示：

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

注意，数据结构是树/DAG结构，其中A-〉B-〉E、A-〉B-〉F等。A是由多个父项拥有的最终子项。
我想要做的是只输出满足以下条件的父对象：1.直接和/或间接拥有A的30%或以上2.是外国公司。3.该外国母公司必须是符合所有权标准的第一级外国母公司，拥有该外国母公司但仍符合所有权标准的任何外国母公司都不计算在内
预期输出：

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

注意，在这种情况下，满足该标准的父母是G和H，因为H是外国人，拥有D的80%，而D拥有A的60（0.8 * 0.6 = 0.48），G是外国人，拥有90%的C，C拥有30%的A，加上G直接拥有5%的A（0.9 * 0.3 + 0.05 = 0.33）还应注意，即使J拥有H的100%，所以也应该拥有A的48%，但是因为H更接近A，所以J不满足标准。

我尝试过的：

基于我问过的一个类似的问题，我了解到我的 Dataframe 表示一个加权有向无环图，其中最终子节点A是根节点。我首先创建了一个dict，将所有的父节点、所有权和国家附加到每个子节点上，但后来我有点卡住了。我尝试使用dfs来计算A中每个父节点的所有最终所有权百分比。并输出A的所有符合条件的父节点。但是，我遇到了以下问题：
1.我不能只将根目录A作为输出字典中的键，并将包含父目录和所有权对的多个行附加到A。我尝试在for循环外初始化键，但遇到错误
1.我希望循环在遇到满足该路径条件的第一个父路径时中断，但其他路径继续运行。
1.也许我只是需要用一种完全不同的方法来达到最终的结果。请heelpp
见下面的代码我用：

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

python

来源：https://stackoverflow.com/questions/75478705/given-the-root-how-to-find-the-ends-of-a-tree-directed-acyclic-graph-based-on-c

2条答案

按热度按时间

enxuqcxy1#

我将使用networkx：

import networkx as nx
import numpy as np

G = nx.from_pandas_edgelist(df.rename(columns={'Ownership': 'weight'}),
                            source='Parent', target='Child',
                            create_using=nx.DiGraph, edge_attr='weight')

foreign = set(df.loc[df['Parent_Country'].eq('Foreign'), 'Parent'])
# {'B', 'F', 'G', 'H', 'J'}

paths = {f: np.product([G.get_edge_data(*e)['weight'] for e in p])
         for f in foreign
         for p in nx.all_simple_edge_paths(G, f, 'A')}

输出：

{'H': 0.48, 'B': 0.1, 'J': 0.48, 'G': 0.05, 'F': 0.06}

图表：

输入：

df = pd.DataFrame({'Child': ['A', 'A', 'A', 'B', 'B', 'H', 'C', 'A', 'D', 'D'],
                   'Parent': ['B', 'C', 'D', 'E', 'F', 'J', 'G', 'G', 'H', 'I'],
                   'Ownership': [0.1, 0.3, 0.6, 0.4, 0.6, 1.0, 0.9, 0.05, 0.8, 0.2],
                   'Parent_Country': ['Foreign', 'Domestic', 'Domestic', 'Domestic', 'Foreign', 'Foreign', 'Foreign', 'Foreign', 'Foreign', 'Domestic']})

赞(0）回复(0）举报 2023-02-18

gpnt7bae2#

下面是另一种方法（networkx非常好）：
首先构建一个字典（子-父关系）和一个集合（包含外国人）：

parents = {
    child: dict(zip(gdf["Parent"], gdf["Ownership"]))
    for child, gdf in df.groupby("Child")
}
foreign = set(df.loc[df["Parent_Country"].eq("Foreign"), "Parent"])

{'B': 'Foreign', 'C': 'Domestic', 'D': 'Domestic', 'E': 'Domestic', 'F': 'Foreign',
 'J': 'Foreign', 'G': 'Foreign', 'H': 'Foreign', 'I': 'Domestic'}

{'F', 'H', 'B', 'G', 'J'}

然后实际搜索：

result = {}
for child, ownership in parents.items():
    stack = [(child, 1.)]
    while stack:
        last_parent, last_own = stack.pop()
        if last_parent not in parents:
            continue
        for parent, own in parents[last_parent].items():
            new_own = last_own * own
            if last_parent != child:
                new_own += ownership.get(parent, 0)
            if parent in foreign and new_own >= 0.3:
                result.setdefault(child, []).append((parent, new_own))
                continue
            stack.append((parent, new_own))

样品结果：

{'A': [('H', 0.48), ('G', 0.32)],
 'B': [('F', 0.6)],
 'C': [('G', 0.9)],
 'D': [('H', 0.8)],
 'H': [('J', 1.0)]}

方法与递归函数相同：

def get_parents(child, last_own=1., ownership=None, level=0):
    if child not in parents:
        return []
    if ownership is None:
        ownership = parents[child]
    result = []
    for parent, own in parents[child].items():
        new_own = last_own * own
        if level > 0:
            new_own += ownership.get(parent, 0)
        if parent in foreign and new_own >= 0.3:
            result.append((parent, new_own))
            continue
        result.extend(get_parents(parent, new_own, ownership, level + 1))
    return result

get_parents("A")的结果为[('G', 0.32), ('H', 0.48)]。

赞(0）回复(0）举报 2023-02-18

我来回答

给定根，如何在Python中基于条件查找树/有向无环图的端点

问题的详细信息：

我尝试过的：

2条答案

相关问题

热门标签

最新问答