我在文件中表示了一个稀疏加权有向图,每行的格式为
from to weight
我想将它读入 scipy 的压缩稀疏格式,这样我就可以对其执行简单的遍历和图形算法(或者实际上是任何内存高效表示)。但是,给定一个节点,我希望能够快速按权重顺序列出其所有传出边,而不必每次都对它们进行排序。当然,每个排序一次就可以了。
是否可以在 scipy 或使用任何其他 python 包中执行此操作?
请您参考如下方法:
你可以像这样加载你的数据:
import numpy as np
import scipy.sparse as sps
data = np.genfromtxt('data.txt', dtype=[('from', np.intp),
('to', np.intp),
('weight', np.float)])
如果您想将权重存储在稀疏矩阵 graph 中,其中 graph[i, j] 是来自节点 i 的权重到节点 j,你可以这样做:
graph = sps.csr_matrix((data['weight'], (data['from'], data['to'])))
要获得一个已排序的传出节点列表,我会使用字典,其中 sorted_to 是按权重排序的传出节点数组。这有点老套,并且依赖于 CSR 稀疏矩阵格式,但您可以这样做:
graph = sps.rand(10, 10, density=0.1, format='csr')
data, indptr, indices = graph.data, graph.indptr, graph.indices
non_empty_rows, = np.nonzero(np.diff(graph.indptr))
sorted_out = {}
for j in non_empty_rows:
weight_slice = data[indptr[j]:indptr[j+1]]
out_slice = indices[indptr[j]:indptr[j+1]]
sorted_out[j] = out_slice[np.argsort(weight_slice)]
举个简单的例子:
>>> graph = sps.rand(5, 5, density=0.2, format='csr')
>>> graph.toarray()
array([[ 0.88968871, 0. , 0. , 0.80773932, 0. ],
[ 0. , 0. , 0.8921645 , 0. , 0. ],
[ 0. , 0. , 0. , 0. , 0. ],
[ 0.18552664, 0. , 0. , 0. , 0. ],
[ 0. , 0. , 0. , 0. , 0.22945956]])
>>> non_empty_rows
array([0, 1, 3, 4], dtype=int64)
>>> sorted_out
{0: array([3, 0]), 1: array([2]), 3: array([0]), 4: array([4])}
