Сохранить путь от листьев к корню, используя 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