從字典創建一個稀疏矩陣

Question

我正在做一個學校項目，我給了一個無向圖G，並且我認爲在G內找到了最小生成樹。我想我會使用Scipy (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html)中的minimum_spanning_tree。但要做到這一點，我必須爲它提供一個數組類或稀疏矩陣，2維。 像這樣：

x_right= 
    ([[0, 2, 0], 
    [2, 0, 5], 
    [0, 5, 0]]) 

在該項目中，我應該採取結構化這樣的鄰接表：

x_input= 
    {'A': [('B', 2)], 
    'B': [('A', 2), ('C', 5)], 
    'C': [('B', 5)]} 

要試試看...有，看是否minimum_spanning_tree是給我想要的結果，我跑了手動更改的x_input到x_right和我得到的輸出：

(0, 1) 2.0 
(1, 2) 5.0 

這是我想要什麼，但我應該返回ŧ他以與x_input相同的格式輸出。

我一直在嘗試各種各樣的方法（其中一個DictVectorizer - ValueError：無法將字符串轉換爲浮點數：'B'...就像在其他情況下一樣），我認爲是時候尋求幫助。

因此，你有沒有關於如何從x_input創建適合於minimum_spanning_tree的矩陣（以及如何將結果再次轉換爲x_input格式）的建議。

謝謝

Answer 1

不知道我是否完全理解了這個問題。從我得到的是要x_input轉換爲稀疏矩陣x_right

import scipy.sparse as sp 

x_input= {'A': [('B', 2)], 
      'B': [('A', 2), ('C', 5)], 
      'C': [('B', 5)]} 

keys = x_input.keys() 
map_dict = dict(zip(list(keys), range(len(keys)))) 

創建字典鍵值映射到上述例如指數從A到1和B到2。然後，您可以遍歷給定的字典以獲取行/列位置。之後，您可以將矩陣的行/列對與相應的值轉換爲稀疏矩陣。

rows, cols, vals = [], [], [] 
for key, values in x_input.items(): 
    for value in values: 
     rows.append(map_dict[key]) 
     cols.append(map_dict[value[0]]) 
     vals.append(value[1]) 
X = sp.csr_matrix((vals, (rows, cols))) 

輸出如下：

print(X.toarray()) 
array([[0, 2, 0], 
     [2, 0, 5], 
     [0, 5, 0]], dtype=int64) 

要轉換稀疏矩陣回，簡單的方法是稀疏矩陣CSR轉換爲COO矩陣。 COO矩陣可以讓您輕鬆獲取行，列和數據。獲得行/列位置後，我有字典map_dict_reverse將它們轉換回給定的鍵。

from collections import defaultdict 
map_dict_reverse = dict(zip(range(len(keys)), list(keys))) 

Xcoo = X.tocoo() # convert csr matrix to coo sparse matrix 
x_convert = defaultdict(list) 
for (r, c, d) in zip(Xcoo.row, Xcoo.col, Xcoo.data): 
    x_convert[map_dict_reverse[r]].append((map_dict_reverse[c] , d)) 
x_convert = dict(x_convert) 

您將在末尾得到x_input。

{'A': [('B', 2)], 'B': [('A', 2), ('C', 5)], 'C': [('B', 5)]}