python - 从字典创建一个稀疏矩阵

Question

我正在做一个学校项目，给我一个无向图 G，我应该找到 G 中的最小生成树。我想我会使用 Scipy 中的 minimum_spanning_tree (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html) .但要做到这一点，我必须给它一个 array_like 或稀疏矩阵，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: could not convert string to float: 'B'... like in other cases)，我认为是时候寻求帮助。

归根结底，关于如何从 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)]}