隣接リストをPythonの隣接行列に変換しようとしています

Question

私が間違っていることを知っていても、これを効果的に実装する方法を考えるのは苦労しています。私は、例えば無向グラフの重み付きグラフなどの隣接リストを読み込むようにコードを作成しようとしています。

[（0,5）、（2,7）]、[（1） 、7）]

そして返す隣接行列にそれを変換する：

[0、5、INF]、[5]、[0,7]、[INF、7、0]

しかし、以下のコードは[0、5、inf]、[5、inf、0、inf、7]、[inf、7、0]を返します。しかし、0は2に隣接しておらず、したがってその重さが 'inf'であるため、[0、5、inf]のような場合にのみ、隣接行列に 'inf'を追加したいだけです。最高のソリューションは何ですか？

def adjacency_matrix(graph_string): 
    adj_list = adjacency_list(graph_string) 
    n = len(adj_list) 
    adj_mat = [[] for _ in range(n)] 
    for i in range(n): 
     for j in range(n): 
      if j == i: 
       adj_mat[i].append(0) 
      else: 
       for neighbour, weight in adj_list[i]: 
        if j == neighbour: 
         adj_mat[i].append(weight) 
         break 
        elif j != neighbour: 
         adj_mat[i].append(float('inf')) 
    return adj_mat 

Answer 1

問題は、あなただけ不足しているエッジについてinfを埋めるためにしたいのでelif一部

elif j != neighbour: 
    adj_mat[i].append(float('inf')) 

であるように思われます。条件elif j < neighbourを使用すると、adj_listがソートされている場合は正しくなります。

ただし、より良い解決策は、ゼロ対角で隣接行列を初期化し、別のところではinfの値にすることです。そして、隣接リストから重みを満たすだけです。こうすることで、非エッジに関する考え方を避けることができます。

これは、numpyを使用して実装する方法の簡単な例です。

import numpy as np 

def adj_list_to_matrix(adj_list): 
    n = len(adj_list) 
    adj_matrix = np.nan * np.ones((n,n)) 
    np.fill_diagonal(adj_matrix,0) 

    for i in range(n): 
     for j, w in adj_list[i]: 
      adj_matrix[i,j] = w 
    return adj_matrix 

使用法：

adj_list = [(1,5)], [(0,5), (2,7)], [(1,7)] 
adj_list_to_matrix(adj_list)