Python从未排序的层次结构fi中查找后代和祖先

Question

我有一个未排序的父子层次结构文件（制表符分隔），格式如下：

City1   Area1
City1   Area2
Continent1  Country1
Continent2  Country2
Continent3  Country3
Continent4  Country4
Continents  Continent1
Continents  Continent2
Continents  Continent3
Continents  Continent4
Country1    State1
Country2    State2
Country3    State3
Earth   Continents
State1  City1
State1  City1.1
State2  City2

我的目标是找到给定成员的所有“后代”和“祖先”。在

以下是我编写的代码：

^{pr2}$

函数find_dependents未按预期工作。至于find_祖先函数，虽然我知道伪代码，但我不能用Python表达它。在

请帮忙。在

Answer 1

正如我在评论中所说的，你在找之前忘了附加你的后代 在你的藏品里。这是有效的：

def find_descendants(parent, collections):
    descendants = []
    for descendant in collections[parent]:
        descendants.append(descendant)
        if descendant in collections:
            descendants = descendants + find_descendants(descendant, collections)
    return descendants

对于祖先，只需构建另一个collections，比如ancestors_collection，它存储了反向的后代/祖先关系。然后查找祖先的函数应该与find\u descents完全相同，您可以相应地对其进行重命名。在

编辑：

Here a complete working code, I use relative to refer to ancestor or descendant:

^{pr2}$

Answer 2

下面是一个使用networkx的简单解决方案：

import networkx as nx

coll = nx.DiGraph()
with open("input.txt") as f:
    for line in map(str.strip, f):
        ancestor, descendant = line.split("\t")
        coll.add_edge(ancestor, descendant)

print(nx.descendants(coll, "Continent1"))
# {'Area2', 'City1.1', 'Area1', 'City1', 'State1', 'Country1'}

print(nx.ancestors(coll, "City1.1"))
# {'Earth', 'Continent1', 'State1', 'Continents', 'Country1'}

这两个函数都返回一个集合，因此祖先和后代没有顺序。在