ツリーを行列Python 3に変換する

Question

私はTree：（list Nat（listof tree））をグラフ行列に変換しようとしていますが、どこから開始するのか分かりません。私はコードを探しているのではなく、この問題に近づく方法のアイデアをもっと探しています。

例えば、ツリーは

ようになり

aTree = [3 , [ 
      [1 , []] , 
      [0 , [ 
        [2 , []] , 
        [5 , []] 
        ] 
      ] , 
      [4 , []] 
      ] 
     ] 

です：

 3 
    /| \ 
    1 0 4 
    /\ 
    2 5 

とマトリックスが関数Nがあるtreetomatrix(Tree, N)だろう

aM = 

    [[0 , 0 , 1 , 1 , 0 , 1] , 
    [0 , 0 , 0 , 1 , 0 , 0] , 
    [1 , 0 , 0 , 0 , 0 , 0] , 
    [1 , 1 , 0 , 0 , 1 , 0] , 
    [0 , 0 , 0 , 1 , 0 , 0] , 
    [1 , 0 , 0 , 0 , 0 , 0]] 

だろう木の頂点の数。だからtreetomatrix(aTree, 6) => aM。

ご提案いただければ幸いです。

Answer 1

この質問の本当に難しい部分は、使用している奇妙なリスト構造を辞書に変更する方法です。 （もしあなたが辞書について知りたくないのであれば、それらを読んでください。彼らはあなたのリストをするためにあなたがしようとしていることをやっていますが、はるかに自然に）私はそれを今スキップしました。私たちの所望の出力である

aTree = {3 : { 
       1: {}, 
       0:{ 2: {}, 
        5: {} 
       } 
       4:{} 
      } 
     } 

def tree_to_matrix(tree, n): 
    return tree_to_mat(tree, [[0 for i in range(n)] for j in range(n)]) 

def tree_to_mat(tree, mat): 
    for k, v in tree.items(): 
     for i in v.keys(): 
      mat[i][k] = mat[k][i] = 1 
     mat = tree_to_mat(v, mat) 
    return mat 

print(tree_to_matrix(aTree, 6)) 

プリント

[[0, 0, 1, 1, 0, 1], [0, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0], [1, 1, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0]] 

。入力をカスタムTreeクラスに読み込み、そのクラスのメソッドを作成して行列を生成する方が簡単です。トリックは再帰を使用して、mat[i][k]とmat[k][i]の両方を同時に設定する必要があることを認識しています。

EDIT：あなたのリストを辞書に変換する私のハックな方法です。

def dictify(l): 
    return {l[0]: d_helper(l[1])} 

def d_helper(l): 
    d={} 
    for i in l: 
     d.update(dictify(i)) 
    return d 

dictify(aTree) 

これは良い方法ですが、これは機能します。