Сохраните путь от листьев до корня с помощью ete2

Question

У меня есть большое дерево, где я хочу получить для каждого листового узла путь (все узлы) до корня.

Я пытаюсь сделать это с помощью ete2, но дерево настолько велико и кажется слишком медленным.

Может ли кто-нибудь предложить более быстрый способ сделать это?

вот что я делаю:

tr = Tree("anytree.nw", format=8) 
    path_leaf_root = {} ## all paths from leafs to root 
    root = tr.get_tree_root() 
    for le in tr: 
     if not path_leaf_root.has_key(le.name): 
      path_leaf_root[le.name]=[] 
     le_up = le 
     while not le_up.name == root.name: 
      le_up=le.up 
      path_leaf_root[le.name].append(le_up.name) 

Answer 1

Вы можете попробовать следующий подход, который пересекает дерево только один раз. На моем компьютере он обработал дерево подсказок размером 50 тыс. В 0,24 сек (немного больше, если вы распечатываете или записываете результаты):

from ete2 import Tree 
t = Tree() 
t.populate(50000) 

import time 
t1 = time.time() 
current_path = [t] 
for postorder, node in t.iter_prepostorder(): 
    if postorder: 
     current_path.pop(-1) 
    else: 
     if not node.children: 
      # print node.name, "path :", current_path 
      pass 
     else: 
      current_path.append(node) 
print time.time() - t1 

# 0.242053985596