Pythonで再帰関数のリストを返す方法

Question

私はPythonでいくつかのおもちゃのコードで遊んでいます。しかし、どうにかして傾けることはできません。ツリー構造のデータ構造で再帰を使用して、特定のノードから各子ノードへのパスを生成しています。

再帰関数の背後にある考え方は、個々のリーフノードへの各パスを収集し、別のリストの各パスを収集するリストを持つことです。

class Tree: 
    def __init__(self): 
     self._ancestors = [] 
     self._store_nodes = {} 

    def add_node(self, node): 
     assert isinstance(node, Node) 
     self._store_nodes[node.name] = node 

    def get_c_path(self, node): 
     subpath = [] 
     path = [] 
     path = self.ret_path(node, subpath, path) 
     return path 

    ## recursive function to fetch paths 
    def ret_path(self, node, subpath=[], pathstore=[]): 
     if len(node.children) == 0: 
      pathstore.append(subpath) 
      return 
     else: 
      for c in node.children: 
       subpath.append(c) 
       self.ret_path(c, subpath, pathstore) 

class Node(object): 
    def __init__(self, name=''): 
     self._name = name 
     self._children = set([]) 
     self._parents = set([]) 

    @property 
    def name(self): 
     return self._name 

    @property 
    def children(self): 
     return self._children 

    @property 
    def parents(self): 
     return self._parents 

    def add_child(self, node): 
     assert isinstance(node, Node) 
     self._children.add(node) 

    def add_parent(self, node): 
     assert isinstance(node, Node) 
     self._parents.add(node) 

if __name__ == '__main__': 
    node_store = {1 : [2,3,4,5,6], 6 : [7,2,8,9,5], 2 : [10,11,5], 12 : [13,14,15,16], 5 : [21,22,23]} 
    tree = Tree() 
    ## build the tree and set parents and children of each node 
    for k, v in node_store.items(): 
     parent_node = None 
     if k in tree._store_nodes: 
      parent_node = tree._store_nodes[k] 
     else: 
      parent_node = Node(k) 
      tree.add_node(parent_node) 
     for c in v: 
      child_node = None 
      if c in tree._store_nodes: 
       child_node = tree._store_nodes[c] 
      else: 
       child_node = Node(c) 
       tree.add_node(child_node) 
      parent_node.add_child(child_node) 
      child_node.add_parent(parent_node) 

    print '-------------' 
    path = tree.get_c_path(tree._store_nodes[2]) 
    for p in path: 
     for t in p: 
      print t.name 
     print "-----" 

次のように私は期待していた結果は、Node-2のためのリストのリストである：

path = [[10], [11], [5, 21], [5, 22], [5, 23]] 

は、どのように私は私の再帰関数を修正することができますか？

Answer 1

ここでは、この目標を達成する2つの方法を示します。私はあなたの構造をいかに修正するかについてはあまりよく分かりません。最初から始めるほうが簡単だったようです。

def get_c_path(self, node): 
    branches = [[c] for c in node.children] 
    expanded = self.expand_branches(branches) 

    while branches != expanded: 
     branches = expanded 
     expanded = self.expand_branches(expanded) 

    return expanded 

def expand_branches(self, branches): 
    new_branches = [] 
    for branch in branches: 
     last_node = branch[-1] 
     if last_node.children: 
      for child in last_node.children: 
       new_branches.append(branch + [child]) 
     else: 
      new_branches.append(branch) 
    return new_branches