私は論理を踏みにじることができません！誰かが私を正しい方向に向けることができますか？

Question

誰でも私の下のプログラムのロジックを踏んで助けてくれますか？私はPython debuggerを使ってみました。これはあまり助けにはなりませんでした。

私は次のことを理解していない：コードのyield (parent, root)ラインで例えば

• preorder_traversal()

  • を。関数はこれらの値をこの時点でジェネレータとして呼び出し元に返しますか、それともジェネレータを返してから、preorder_traversal()関数の中に入り続けますか？

  • また、〜preorder_traversal()の回帰コールで頭を包み込むときに心が完全に溶けます。誰もがこれを理解する方法を知っていますか？真理のテーブルのようなもの、私は手でペンや紙、メモ帳などでプログラムを踏み外すのに使うことができます。私はこれの最も複雑な部分が入れ子と再帰であると思います。

• 私はリストにノードを追加するノードなど、または追加全体とエッジ部の内部ノード内のノードを理解していません。

コード

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) 

お礼にこれを読むため。

Answer 1

yield演算子については、yieldは、関数がジェネレータであることを許可します。したがって、lazyです。この特定の例では、発電機の必要はなく、その唯一の利点ははるかに優れた可読性（すなわち、for _ in _）です。抽象的には、next()ジェネレータの操作を使用してyield (parent, root)が返されます。次に、next()が再び呼び出されると、ジェネレータは関数内の残りのコードを動的に実行し続けます。

再帰呼び出しに関しては、graph traversalのいずれかのタイプを実行する場合、これはかなり一般的です。さらに、グラフはrecursive data structureです。

Hereは、グラフのトラバーサルを理解するための優れたリソースです。

以下

いくつかのコメントがありpreorder_traversal()を少し変更したバージョン（読みやすい）です：

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) 

がirange(n) == xrange(n+1)カスタムirange()発電を検討し、Pythonのジェネレータの怠惰な性質を証明するために：

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

a = irange(9999999999999999999999)を実行すると、が呼び出されるまでirange()のコードは実行されません。発電機と再帰を理解することが

、rrange(n) == reversed(irange(n))カスタムrrange()発電考える：[？「利回り」のキーワードは何をするん]の

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