Поиск путей между родительским узлом и определенными дочерними узлами в дереве

Question

Заранее извиняюсь за открытый характер этого вопроса, но в настоящее время я провожу мозговой штурм, как решить проблему автоматизации с использованием Python. Набор данных, которые я анализирую, можно представить как дерево, которое выглядит следующим образом:

На мой вопрос есть две части: сначала сложная часть, а затем еще один вопрос общего характера.

1. Для данного родительского узла верхнего уровня (узла, у которого нет родителя), как найти путь к дочернему узлу нижнего уровня (узлу без потомков) ТОЛЬКО для нижних узлов, которые находятся в наборе значений я определяю? Например, если я определю набор значений только как «B» и «F», я бы хотел только извлечь путь из A в B и только из A в F. Например, я должен получить [A -> Y -> B] и [A -> Z -> C -> F] в качестве ответа.

2. Учитывая вышеприведенные требования, как лучше всего представить эти деревья в Python? Моей оригинальной мыслью были вложенные словари, в которых каждый узел определен как ключ словаря. Имейте в виду, что пример, который я дал, прост. Я буду строить эти деревья для множества разных родителей верхнего уровня, и у каждого родителя верхнего уровня может быть много-много дочерних узлов.

Answer 1

Предполагая, что количество желаемых листьев в том же порядке, что и количество листьев, самое простое решение - просто создать общий итератор для всех путей, а затем просто отфильтровать его по совпадениям. Например:

def find_paths(self, targets):
    targets = set(targets)
    for path in self.iter_all_paths_dfs():
        if path[-1].name in targets:
            yield path

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

---

И если вы можете сделать это таким образом, вам не нужны обратные указатели или следующие указатели, так что узел может быть точным отображением дочерних имен дочерним узлам, как вы предложили.

Тем не менее, часто проще представить узел как имя и набор дочерних элементов. Для сравнения:

class Node(collections.namedtuple('Node', ('name', 'children'))):
    def iter_node_names_dfs(self):
        yield self.name
        for child in self.children:
            yield from child.iter_node_names_dfs()

E = Node('E', ())
F = Node('F', ())
C = Node('C', (E, F))
D = Node('D', ())
Z = Node('Z', (C, D))
X = Node('X', ())
A = Node('A', (X, Z))
tree = A

до:

E = {}
F = {}
C = {'E': {}, 'F': {}}
D = {}
Z = {'C': C, 'D': D}
X = {}
A = {'X': X, 'Z': Z}
tree = {'A': A}

def iter_node_names_dfs(tree):
    for name, child in tree.items():
        yield name
        yield from iter_node_names_dfs(child)

Обратите внимание, что для решения dict требуется дополнительный узел, указывающий на A, чтобы вы могли хранить его имя, а это также означает, что вы не можете получить имя узла от узла; Вы должны запомнить это с предыдущего шага.

Что касается пространства, то здесь не так много различий, но, конечно, вы можете проверить его (повторяя и суммируя sys.getsizeof(node), если это вызывает озабоченность).