Python 3.5 - «Инфекция открытых ветвей дерева»

Question

Я знаю, что название звучит немного странно, но, конечно, это просто аналогия с тем, что мне действительно нужно.

Итак, предположим, у меня есть дерево, как это:

A 
┃ 
┣━━ B 
┃ ┣━━ D 
┃ ┣━━ E 
┃ ┃ ┗━━ H 
┃ ┗━━ F 
┃  ┗━━ I 
┗━━ C 
    ┗━━ G 

с одним из листьев (или ветви), инфицированных какого-либо заболевания.

Обход дерева будет заражать все «открытые» ветви/листья во время обхода, , но не вновь открытые. Предположим, что ветвь E заражена - заражение зараженного дерева F и C ветвей, так как они уже «открыты» на этой итерации, но не I и G.

код питона У меня до сих пор (infection_test.py):

#!/usr/bin/env python 
from itertools import chain 

class Node(): 
    def __init__(self, name, infected=False): 
     self.name = name 
     self.children = [] 

     self.infected = infected 

    def __str__(self): 
     return 'Node ' + self.name + (' *** INFECTED ***' if self.infected else '') 

A = Node('A');B = Node('B');C = Node('C') 
D = Node('D');E = Node('E', True);F = Node('F'); 
G = Node('G');H = Node('H');I = Node('I'); 

A.children = [B, C] 
B.children = [D, E, F] 
E.children = [H] 
F.children = [I] 
C.children = [G] 

def traverse_tree(node, level=0): 
    print (' '*level, node) 
    level += 1 
    infected_found = False 
    for child in node.children: 
     if child.infected: 
      infected_found = True 
     traverse_tree(child, level) 
     child.infected = infected_found 

print('First traversal:') 
traverse_tree(A) 
print('\nAfter Infection:') 
traverse_tree(A) 

Какие выходы:

First traversal: 
Node A 
    Node B 
     Node D 
     Node E *** INFECTED *** 
      Node H 
     Node F 
      Node I 
    Node C 
     Node G 

After Infection: 
Node A 
    Node B 
     Node D 
     Node E *** INFECTED *** 
      Node H 
     Node F *** INFECTED *** 
      Node I 
    Node C 
     Node G 

Как я могу сделать ветви 'более высокого уровня' (как C) быть зараженным, без влияния на следующие итерации traverse_tree?

(я надеюсь, что «открытые ветви» достаточно ясно, но только, чтобы удостовериться, что это - те ветви, которые выходы из цикла for child уже, когда зараженный филиал обнаружен)

Answer 1

ОК, так что я нашел решение, но я думаю, что все равно буду ждать лучшего.

Я только что отредактировал оригинал Node и добавил атрибут p_infected. Это поможет мне отметить все ветви, которые мне нужно заразить позже. Как только я обнаружил какую-то зараженную ветку, она заражает всех своих родителей до корня. Затем я пересекаю дерево, заражаю детей этих ветвей и удаляю «родительскую инфекцию».

текущий код выглядеть следующим образом:

from itertools import chain 

class Node(): 
    def __init__(self, name, infected=False, p_infected=False): 
     ... 
     self.parent = None 
     self.p_infected = p_infected 

    def add_children(self, childs = []): 
     self.children.extend(childs) 
     for node in childs: 
      node.parent = self 

    def __str__(self): 
     return 'Node ' + self.name + \ 
     (' ***INFECTED***' if self.infected else '') + \ 
     (' ***P_INFECTED***' if self.p_infected else '') 

A = Node('A');B = Node('B');C = Node('C') 
D = Node('D',True);E = Node('E');F = Node('F'); 
G = Node('G');H = Node('H');I = Node('I'); 

A.add_children([B,H]) 
B.add_children([C, D, F]) 
D.add_children([E]) 
F.add_children([G]) 
H.add_children([I]) 

def infect_parent(node): 
    if node.parent: 
     node.parent.p_infected = True 
     infect_parent(node.parent) 

def traverse_tree(node, level=0): 
    print (' '*level + str(node)) 
    if node.infected: 
     node.p_infected = True 
     infect_parent(node) 
    level += 1 
    for child in node.children: 
     traverse_tree(child, level) 


def infect_children(node): 
    infect_flag = False 
    for child in node.children: 
     if infect_flag: 
      child.infected = True 
     infect_flag = child.p_infected 
     infect_children(child) 

def remove_parent_infection(node): 
    node.p_infected = False 
    for child in node.children: 
     remove_parent_infection(child) 

print('First travesal:') 
traverse_tree(A) 
infect_children(A) 
remove_parent_infection(A) 
print('\nAfter infection:') 
traverse_tree(A) 

И выход, по желанию:

First travesal: 
Node A 
    Node B 
     Node C 
     Node D ***INFECTED*** 
      Node E 
     Node F 
      Node G 
    Node H 
     Node I 

After infection: 
Node A 
    Node B 
     Node C 
     Node D ***INFECTED*** 
      Node E 
     Node F ***INFECTED*** 
      Node G 
    Node H ***INFECTED*** 
     Node I 

Но, как я уже писал раньше, я по-прежнему открыт для лучшего решения. У меня есть догадка, что вышеупомянутое может быть сделано только с помощью оригинальной функции «обхода», и если кто-то найдет, как я буду счастлив.

Спасибо.