Pythonの行列から隣接リストのグラフを作成する

Question

私は文字のマトリックスから文字のグラフを作成しようとしています（boggleボードを表す）。だから私のようなもの持っていると言う：

[ [ A, B, C, D], 
    [E, F, G, H], 
    [I, J, K, L], 
    [M, N, O, P] ]. 

を、私は、各ノードは、文字にしたいが、私は、各ノードの隣人を取得する方法を考え出すのトラブルを抱えています。たとえば、ノードAには隣接ノードB、E、Fがありますが、ノードKには隣接ノードF、G、H、J、L、M、O、Pがあります。

g = { "A" : ["D", "F"], 
     "B" : ["C"], 
     "C" : ["B", "C", "D", "E"], 
     "D" : ["A", "C"], 
     "E" : ["C"], 
     "F" : ["D"] 
    } 

あなたのグラフの構造に応じて：

Answer 1

あなたは可能性があり、あなたのマトリックス内のすべてのノードをループし、その結果に右&以下のすべての隣接ノードを追加します。

matrix = [ 
    ['A', 'B', 'C', 'D'], 
    ['E', 'F', 'G', 'H'], 
    ['I', 'J', 'K', 'L'], 
    ['M', 'N', 'O', 'P'] 
] 

def add(adj_list, a, b): 
    adj_list.setdefault(a, []).append(b) 
    adj_list.setdefault(b, []).append(a) 

adj_list = {} 
for i in range(len(matrix)): 
    for j in range(len(matrix[i])): 
     if j < len(matrix[i]) - 1: 
      add(adj_list, matrix[i][j], matrix[i][j+1]) 
     if i < len(matrix[i]) - 1: 
      for x in range(max(0, j - 1), min(len(matrix[i+1]), j+2)): 
       add(adj_list, matrix[i][j], matrix[i+1][x]) 

import pprint 
pprint.pprint(adj_list) 

が出力：

{'A': ['B', 'E', 'F'], 
'B': ['A', 'C', 'E', 'F', 'G'], 
'C': ['B', 'D', 'F', 'G', 'H'], 
'D': ['C', 'G', 'H'], 
'E': ['A', 'B', 'F', 'I', 'J'], 
'F': ['A', 'B', 'C', 'E', 'G', 'I', 'J', 'K'], 
'G': ['B', 'C', 'D', 'F', 'H', 'J', 'K', 'L'], 
'H': ['C', 'D', 'G', 'K', 'L'], 
'I': ['E', 'F', 'J', 'M', 'N'], 
'J': ['E', 'F', 'G', 'I', 'K', 'M', 'N', 'O'], 
'K': ['F', 'G', 'H', 'J', 'L', 'N', 'O', 'P'], 
'L': ['G', 'H', 'K', 'O', 'P'], 
'M': ['I', 'J', 'N'], 
'N': ['I', 'J', 'K', 'M', 'O'], 
'O': ['J', 'K', 'L', 'N', 'P'], 
'P': ['K', 'L', 'O']} 

Answer 2

あなたはノード に接続されたノードを格納するために辞書を使用する必要があります。グラフ内のノードの隣人を取得するには

単にあなたの行列を想定すると、ノードの値

>>> g["A"] 
>>> ["D","F"] 

Answer 3

は、n×mの行列であり、各要素は、以下のようなユニーク文字列でアクセスすることができます。

    # The matrix
 

matrix = [ 
    ['A', 'B', 'C', 'D'], 
    ['E', 'F', 'G', 'H'], 
    ['I', 'J', 'K', 'L'], 
    ['M', 'N', 'O', 'P'] 
] 
 

あなたは最初の要素のインデックスを見つけることができます。

    node = 'K' # Input 

    # Get the matrix dimension 
    n = len(matrix) 
    m = len(matrix[0]) 

    # Assume there is exactly one matching node 
    for i in xrange(n): 
     for j in xrange(m): 
      if matrix[i][j] == node: 
       x, y = i, j 

し、リストとして隣人を返す：

 
    # Get the (at most) 8 neighbors 

    neighbors = [row[max(0,y-1):y+2] for row in matrix[max(0,x-1):x+2]] 
    answer = set([v for r in neighbors for v in r]) 
    answer.remove(node) 
    answer = list(answer) 

ノードが複数のオカレンスを持つことができるならば、あなたは、Pythonに新しいしている場合How to find the index of a value in 2d array in Python?また、これらのリンクはあなたのための役に立つかもしれない参照してください。

• Sub matrix of a list of lists (without numpy)
• Convert multi-dimensional list to a 1D list in Python
• How to find the index of a value in 2d array in Python?