创建未知大小的稀疏矩阵 [英] creating sparse matrix of unknown size

问题描述

例如，我有一个文本文件，每行表示一个图的边

I have a text file with each line indicating an edge on a graph, for example

2 5 1

表示节点2和5之间的权重1的边缘.我想使用这些元组创建一个稀疏的邻接矩阵.通常，我将稀疏矩阵初始化为

indicates an edge of weight 1 between nodes 2 and 5. I want to create a sparse adjacency matrix using these tuples. Typically, I'd initialize a sparse matrix as

G = scipy.sparse.lil_matrix((n,n))

其中n是图中的节点数.但是在这种情况下，我不知道"n"是什么.有没有比在文件的各行上循环以找到最大节点索引，创建lil_matrix然后再次在文件上循环更有效的方式来创建矩阵?我当前的实现是这样:

where n is the number of nodes in the graph. But in this case, I do not know what 'n' is. Is there a more efficient way to create the matrix than looping over the lines of the file to find the max node index, creating the lil_matrix and then again looping over the file ? My current implementation is this:

n = 0
with open(gfile) as f:
    for line in f:
        temp = map(int,line.split())
        n = np.max([n,temp[0],temp[1]])
G = sp.lil_matrix((n,n))
with open(gfile) as f:
    for line in f:
        temp = map(int,line.split())
        G[temp[0],temp[1]] = temp[2]

推荐答案

创建稀疏矩阵的原始方法(也是原型)是将所有输入收集在row, col, data数组(或列表)中，并使用coo_matrix构造矩阵.可以从这些输入(最大索引值)推导形状，也可以将其作为参数给出.

The original, and still prototypical, way of creating a sparse matrix is to collect all inputs in row, col, data arrays (or lists), and use coo_matrix to construct the matrix. Shape can be deduced from those inputs (maximum index values), or given as a parameter.

修改代码

row, col, data = [],[],[]
with open(gfile) as f:
    for line in f:
        temp = map(int,line.split())
        # G[temp[0],temp[1]] = temp[2]
        data.append(temp[2])
        row.append(temp[0])
        col.append(temp[1])
G = sparse.coo_matrix((data, (row,col))

列表追加至少与行读取一样快，并且比稀疏矩阵插入要好，甚至lil(lil分配也涉及列表追加).

List appends are at least as fast as line reads, and better than sparse matrix inserts, even lil (lil assignment involves list appends as well).

我怀疑您也可以这样做:

I suspect you could also do:

A = np.genfromtxt(gfile, dtype=int) # default white space delimiter
# A should now be a 2d 3 column array
G = sparse.coo_matrix((A[:,2], (A[:,0], A[:,1]))

用genfromtxt或loadtxt读取整个文件，然后从结果列中创建稀疏矩阵.

That is read the whole file with genfromtxt or loadtxt and create the sparse matrix from the resulting columns.

(几年前当我在MATLAB中创建稀疏矩阵时，我使用了这种数据，列，行初始化，尽管巧妙地使用了索引来从没有循环的有限元模块中组装这些数组.)

(When I made sparse matrices in MATLAB years ago, I used this sort of data, col, row initialization, though with a clever use of indexing to assemble those arrays from finite element blocks without loops.)

这篇关于创建未知大小的稀疏矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！