Skip to main content
 首页 » 编程设计

python之如何在 scipy 中读取稀疏有向图

2024年11月01日9daizhj

我在文件中表示了一个稀疏加权有向图,每行的格式为

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])}