Pythonの - 私は、次の形式でソートされていない親子階層のファイル（タブ区切り）はソートされていない階層のファイル

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 

を私の目標は、すべての「子孫」を見つけることですし、与えられたメンバーの "祖先"。ここで

は、私がこれまで行うコード化されたものである：予想通り

import sys, re 

with open("input.txt", "r") as my_in: 
    collections={} 
    for line in my_in: 
     parent, child=line.rstrip('\r\n').split('\t') 
     collections.setdefault(parent, []).append(child) 

print (collections) 
''' 
{'Continent4': ['Country4'], 'Continent2': ['Country2'], 
'Continents': ['Continent1', 'Continent2', 'Continent3', 'Continent4'], 
'Continent1': ['Country1'], 'Country2': ['State2'], 
'Country3': ['State3'], 'State1': ['City1', 'City1.1'], 
'Country1': ['State1'], 'State2': ['City2'], 
'Earth': ['Continents'], 'City1': ['Area1', 'Area2'], 'Continent3': ['Country3']} 
''' 

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

# Get descendants of "Continent1": 
lis=find_descendants("Continent1", collections) 
print (lis) # It shows ['Area1', 'Area2', 'City1.1'] 
# Actually it should show ['Country1', 'State1', 'City1', 'Area1', 'Area2', 'City1.1'] 

def find_ancestors(child, collections): 
    # pseudo code 
    # link child to its parent and parent to its parent until no more parents are found 
    pass 

# lis=find_ancestors("City1.1", collections) 
# should show ['Earth', 'Continents', 'Continent1', 'Country1', 'State1'] 

機能find_descendantsが機能していません。 find_ancestors関数に関しては、私は擬似コードを知っていますが、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 

、ちょうど逆の関係の子孫/祖先を格納する、ancestors_collectionを言って、他のcollectionsを構築します。祖先を見つける関数はfind_descendantsとまったく同じである必要があります。find_descendantsはそれに応じて名前を変更することができます。

EDIT：

ここでは完全な作業コード、私は祖先や子孫を参照するためにrelativeを使用します。

import sys, re 

with open("input.txt", "r") as my_in: 
    descendants={} 
    ancestors={} 
    for line in my_in: 
     parent, child=line.rstrip('\r\n').split('\t') 
     descendants.setdefault(parent, []).append(child) 
     ancestors.setdefault(child, []).append(parent) 

def get_relatives(element, collection): 
    relatives = [] 
    for relative in collection[element]: 
     relatives.append(relative) 
     if relative in collection: 
      relatives = relatives + get_relatives(relative, collection) 
    return relatives 

# Get descendants of "Continent1": 
lis=get_relatives("Continent1", descendants) 
print (lis) 
# shows ['Country1', 'State1', 'City1', 'Area1', 'Area2', 'City1.1'] 

lis=get_relatives("City1.1", ancestors) 
print (lis) 
# shows ['Earth', 'Continents', 'Continent1', 'Country1', 'State1'] 

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'} 

両方の関数がそれで祖先と子孫は命令されません。