python - Python で珍しいツリーをたどる

Question

次のような珍しいツリー配列があります。

[[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], 
 [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]

配列の各要素はペアです。これは、2 番目の要素が最初の要素のフォロワーであることを意味します。

[0, 1] - 0 is followed by 1
[1, 2] - 1 is followed by 2

次のように配列を抽出しようとしています：

0 1 2 3 6    
0 1 2 4 6    
0 1 2 5 6
0 7 6
8 9 6

このようなすべての可能なパスを抽出するための堅牢なトラバーサルをコーディングできませんでした。Pythonでどうすればできますか？

Answer 1

再帰ジェネレーター関数を使用してそれを行うことができます。ツリーのルートノードは、常に元のリストのすべての子の前に来ると思います。

tree = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6],
        [0, 7], [7, 6], [8, 9], [9, 6]]

paths = {}
for t in tree:
    if t[0] not in paths: paths[t[0]] = []
    paths[t[0]].append(tuple(t))

used = set()

def get_paths(node):
    if node[1] in paths:
        for next_node in paths[node[1]]:
            used.add(next_node)
            for path in get_paths(next_node):
                yield [node[0]] + path
    else:
        yield [node[0], node[1]]

for node in tree:
    if tuple(node) in used: continue
    for path in get_paths(node):
        print path

出力：

[0, 1, 2, 3, 6]
[0, 1, 2, 4, 6]
[0, 1, 2, 5, 6]
[0, 7, 6]
[8, 9, 6]

説明：最初に、各ノードからのすべての可能なパスのリストを作成します。次に、まだ使用していないノードごとに、それがルートノードであると想定し、そこからどのパスがつながるかを再帰的に見つけます。どのノードからもパスが見つからない場合、それはリーフノードであり、再帰を停止して、見つかったパスを返します。

If the assumption about the order of the nodes does not hold then you would first have to find the set of all root nodes. This can be done by finding all nodes that do not appear as the second node in any connection.

Answer 2

私があなたの質問について理解していることから、あなたはツリーを説明するペアのリストとして親子関係のセットを持っているように見えます。リンクリストのような構造になっていると思って困っているようです。リンクリストとは異なり、ツリーはより一般的な形式であり、子と呼ばれる特定のノードを「追跡」する複数のノードを持つことができます。

最も簡単な方法は、最初にツリーを構築してから、ルートからツリーをトラバースすることです。2つのフィールドを持つNodeクラスを定義します。1つはノードの値用で、もう1つは子のリスト用です。次に、リストの項目を繰り返し処理して、各ペアの2番目の要素を、ペアの最初の要素に対応するノードの子リストに追加します。ツリーが構築された後、現在のノードを印刷し、その子（存在する場合）でそれ自体を呼び出す再帰的な印刷関数を使用します。ルートノードで関数を呼び出すと、ツリー全体が出力されます。

コードを投稿しますが、これは宿題によく似ています。上記の説明は、開始には十分なはずです。

Answer 3

私が考えることができる最も簡単な方法は、次のように、特定の親に対して可能なすべての子を含む辞書を作成することです。

d = {}

for parent, child in tree:
    try:
        d[parent].append(child)
    except KeyError:
        d[parent] = [child]

ツリー = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6] ]、[0, 7]、[7, 6]、[8, 9]、[9, 6]]、これは次のようになります。

{0: [1, 7],
 1: [2],
 2: [3, 4, 5],
 3: [6],
 4: [6],
 5: [6],
 7: [6],
 8: [9],
 9: [6]}

これで、次のようにツリーを再帰的にトラバースできるようになりました。

def printPaths(d, currentPath):
    if currentPath[-1] not in d:
        print currentPath # last node can't possibly be a parent, so stop
    else:
        for child in d[currentPath[-1]]:
            printPaths(d, currentPath + [child])


for root in d:
    printPaths(d, [root])

私は再帰をテストしていませんが、アイデアが得られるはずです:)

Answer 4

どうぞ。地球上で最も優れたコードではありませんが、機能します。

inputValues = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]

tree = {}
numberOfChildren = {}
for (f, t) in inputValues:
  if not tree.has_key(f):
    tree[f] = []
  tree[f].append(t)
  if not numberOfChildren.has_key(t):
    numberOfChildren[t] = 0
  numberOfChildren[t] += 1

roots = [c for c in tree if c not in numberOfChildren]
permutations = []

def findPermutations(node, currentList):
  global tree
  global permutations
  if not tree.has_key(node):
    permutations.append(currentList)
    return
  for child in tree[node]:
    l = list()
    l.extend(currentList)
    l.append(child)
    findPermutations(child, l)

for r in roots:
  findPermutations(r, [r])

print permutations

Answer 5

問題を見ると、最良のアプローチは、数回の反復にわたってアレイを逆方向に構築することであるように思われます。私の考えはこれですが、これは木であると想定する必要があるため、葉は1回しか使用できないことに注意してください。

1. 配列=ペアのリスト
2. 配列内のすべての配列がリーフになるまで：
   1. 配列がリーフの場合（最後の要素は配列内のどの配列の最初の要素でもありません）：
      1. 配列内の各配列について、リーフをその最後にアタッチできるかどうかを確認します
      2. 可能なすべてのアレイにアタッチした後、リーフを削除します

明らかに、それをコードに変換するためにいくつかの作業を行う必要がありますが、それは大まかな考えです。

Answer 6

次のページからfind_all_paths関数を使用できます： http ：//www.python.org/doc/essays/graphs/

これを使用するには、グラフに2週間のマイナーを作成する必要があります。まず、エッジのリストをループして、次のようなグラフの新しい表現を作成します。

    graph = {0: [1, 7],
             1: [2],
             2: [3, 4, 5],
             ...}

次に、スーパーシンクを作成し（この例では、10と呼ぶことができます）、エッジのないすべての頂点をこの新しいノードに接続します。

次に、関数find_all_paths(graph, 0, 10)を呼び出して、そのようなすべてのパスを見つけることができます。

Answer 7

考えられるすべての開始ノードからすべての最長パスを生成します。

tree = [[0, 1], [1, 2], [2, 3], ...]

dtree = {}
for (k, v) in tree:
   dtree.setdefault(k, []).append(v)

parts = [[root] for root in range(10)]

while parts:
   path = parts.pop(0)
   if path[-1] in dtree:
      for n in dtree[path[-1]]:
         parts.append(path + [n])
   else:
      print path

他のノードから始まる別の長いパスの一部ではないパスのみを生成する必要がある場合は、partsに含まれていないすべてのノードに初期化する必要があります[p[1] for p in tree]。代わりに、最長パスだけでなくすべてのパスが必要な場合は、while ループのすべての反復で出力が必要です。

Answer 8

次の作品 - ルートから始まるツリーを生成します。ルートは、親を持たないノードと見なされます。

import operator
def genpaths(data):
    # Initialize dictionary
    ddata = {}
    for item in data:
        ddata.setdefault(item[0], []).append(item[1])
    def genpath(root):
        "Generate paths starting with root"
        if root not in ddata:
            yield (root, )
        else:
            for child in ddata[root]:
                for path in genpath(child):
                    yield (root, ) + path

    for root in set(ddata.keys()) - set(reduce(operator.add, ddata.values())):
        for path in genpath(root):
            print path