Ich kann nicht durch die Logik gehen! Kann mir jemand in die richtige Richtung zeigen?

Question

Kann mir jemand helfen, die Logik des unten gezeigten Programms durchzugehen? Ich habe versucht, die Python debugger zu verwenden. Das hat mir aber nicht viel geholfen.

Ich verstehe nicht, wie folgt vor:

• preorder_traversal()

  • Zum Beispiel an der yield (parent, root) Codezeile; Gibt die Funktion diese Werte als Generator an diesem Punkt an den Aufrufer zurück oder gibt sie den Generator zurück und geht dann weiter in die Funktion preorder_traversal()?

  • Auch schmilzt völlig, wenn Sie versuchen, meinen Kopf um den rekursiven Anruf zu preorder_traversal() zu wickeln. Kennt jemand einen Weg, dies zu verstehen? Wie eine Wahrheitstabelle oder etwas Ähnliches, mit dem ich das Programm manuell mit Stift und Papier oder Notizblock oder was auch immer durchgehen kann. Ich denke, der komplizierteste Teil davon ist die Verschachtelung und die Rekursion.

• Ich verstehe nicht, den Knoten in einem Knoten in einem Knoten, etc. Oder die gesamte Zugabe und Randteil, der einen Knoten zu einer Liste hinzufügt.

-Code

class Node(object): 
    """A simple digraph where each node knows about the other nodes 
    it leads to. 
    """ 
    def __init__(self, name): 
     self.name = name 
     self.connections = [] 
     return 

    def add_edge(self, node): 
     "Create an edge between this node and the other." 
     self.connections.append(node) 
     return 

    def __iter__(self): 
     return iter(self.connections) 

def preorder_traversal(root, seen=None, parent=None): 
    """Generator function to yield the edges via a preorder traversal.""" 
    if seen is None: 
     seen = set() 
    yield (parent, root) 
    if root in seen: 
     return 
    seen.add(root) 
    for node in root: 
     for (parent, subnode) in preorder_traversal(node, seen, root): 
      yield (parent, subnode) 
    return 

def show_edges(root): 
    "Print all of the edges in the graph." 
    for parent, child in preorder_traversal(root): 
     if not parent: 
      continue 
     print '%5s -> %2s (%s)' % (parent.name, child.name, id(child)) 

# Set up the nodes. 
root = Node('root') 
a = Node('a') 
b = Node('b') 
c = Node('c') 

# Add edges between them. 
root.add_edge(a) 
root.add_edge(b) 
a.add_edge(b) 
b.add_edge(a) 
b.add_edge(c) 
a.add_edge(a) 

print 'ORIGINAL GRAPH:' 
show_edges(root) 

Dankes- dies zu lesen.

Answer 1

Wie für den yield Operator, yield ermöglicht die Funktion, ein Generator zu sein, also lazy. Für dieses spezielle Beispiel wird die Notwendigkeit eines Generators nicht benötigt und sein einziger Vorteil ist eine viel bessere Lesbarkeit (d. H. for _ in _). Zusammenfassend wird yield (parent, root) zurückgegeben, indem der next()-Vorgang am Generator verwendet wird. Dann, wenn next() erneut aufgerufen wird, führt der Generator weiterhin dynamisch den verbleibenden Code in der Funktion aus.

Wie für den rekursiven Aufruf ist dies ziemlich üblich, wenn Sie einen beliebigen Typ von graph traversal. Außerdem ist ein Graph ein recursive data structure.

Here ist eine gute Ressource für das Verständnis von Graph-Traversalen.

Unten finden Sie eine leicht modifizierte Version des preorder_traversal() (leichter zu lesen), die einige Kommentare hat:

def preorder_traversal(root, seen=set(), parent=None): 
    """Generator function to yield the edges via a preorder traversal.""" 
    yield (parent, root) 

    # avoid cycle 
    if root not in seen: 
     seen.add(root) 

     # for each neighbor of the root 
     for node in root: 

      # for each (parent, neighbor) pair in the subgraph 
      # not containing the nodes already seen 
      for (parent, subnode) in preorder_traversal(node, seen, root): 
       yield (parent, subnode) 

die faule Art eines Python-Generator Um zu demonstrieren, betrachten die benutzerdefinierte irange() Generator wo irange(n) == xrange(n+1):

def irange(limit): 
    current_number = 0 
    while current_number <= limit: 
     yield current_number 
     current_number += 1 

Wenn Sie a = irange(9999999999999999999999) tun, wird kein Code in irange() durchgeführt, bis next() wird sie aufgefordert hatte.

Um Rekursion mit Generatoren, sollten Sie die benutzerdefinierte rrange() Generator wo rrange(n) == reversed(irange(n)) zu verstehen: [? Was bedeutet die "Ausbeute" Schlüsselwort do]

def rrange(limit): 
    if limit >= 0: 
     yield limit 
     for num in rrange(limit - 1): 
      yield num