Python 3.5 - 'Infect geöffnete Äste'

Question

Ich weiß, dass der Titel etwas komisch klingt, aber das ist natürlich nur eine Analogie zu dem, was ich wirklich brauche.

So lässt vermuten, ich habe einen Baum wie folgt aus:

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

mit einem der Blätter (oder Zweige) mit einer Krankheit infiziert.

Beim Durchfahren des Baumes werden alle 'geöffneten' Zweige/Blätter zur Durchlaufzeit infiziert, , aber nicht neu geöffnete. Nehmen wir an, dass die Verzweigung E infiziert ist - durchqueren der Baum Ausbeute infiziert F und C Zweige, da sie bereits in dieser Iteration "geöffnet", aber nicht I und G.

Der Code Python ich bisher habe, ist (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) 

Welche Ausgänge:

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 

Wie kann ich 'höhere Ebene' Zweige (wie C) machen infiziert werden, ohne Einfluss auf die nächsten Iterationen von traverse_tree?

(ich hoffe, dass ‚geöffnet Zweige‘ ist klar genug, aber nur, um sicherzustellen, es ist - das sind die Zweige, die bereits von der for child Schleife ergibt, wenn die infizierte Zweig entdeckt)

Answer 1

OK, so dass ich Ich habe eine Lösung gefunden, aber ich denke, ich werde immer noch auf eine bessere warten.

Ich habe gerade das Original Node bearbeitet und das Attribut p_infected hinzugefügt. Dies wird mir helfen, alle Zweige zu markieren, die ich später infizieren muss. Sobald ich einen infizierten Zweig gefunden habe - infiziert es alle seine Eltern bis an die Wurzel. Dann durchquere ich den Baum, infiziere die Kinder dieser Zweige und entferne die "Elterninfektion".

Der aktuelle Code sieht wie folgt aus:

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) 

Und die Ausgabe wie gewünscht:

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 

Aber, wie ich schon geschrieben habe, bin ich zu einer besseren Lösung noch offen. Ich habe eine Ahnung, dass die oben genannten nur mit der ursprünglichen "Traversal" -Funktion getan werden könnte, und wenn jemand finden könnte, wie - ich werde glücklich sein ..

Vielen Dank.