从邻接表快速创建 Scipy 稀疏矩阵

Question

我正在尝试从邻接表创建一个 networkx 图。我目前正在执行以下操作，速度很慢。我查看了 scipy.sparse 矩阵选项，据我所知 none 与我正在使用的格式相同。 adj 中的每个项目都可以有不同的长度，这使情况变得复杂。

o3dmesh.adjacency list returns 一组列表。集合 adjacency_list[i] 包含顶点 i 的相邻顶点的索引。没有行、列索引，只有绝对索引。

import open3d as o3d
import networkx as nx
import scipy

def adj_matrix(adj):
    n = len(adj)
    g= scipy.sparse.dok_matrix((n,n), int)
    for num, i in enumerate(adj):
        g[num, list(i)] = 1
    return g

o3dmesh = mesh = o3d.io.read_triangle_mesh(path)
adj = o3dmesh.adjacency_list
adj = adj_matrix(adj)
graph = nx.from_scipy_sparse_matrix(adj)

Answer 1

我不熟悉 networkx 或您的 adj 列表。但是从代码中我猜它是 (0,n) 范围内的整数列表或数组。

下面是从此类数组构造矩阵的最常用方法：

In [28]: from scipy import sparse                                                              
In [29]: adj = np.random.randint(0,10,size=10)                                                 
In [30]: adj                                                                                   
Out[30]: array([4, 7, 9, 7, 2, 1, 3, 3, 4, 8])
In [31]: data = np.ones_like(adj)                                                              
In [32]: rows = np.arange(10)                                                                  
In [33]: col = adj                                                                             
In [34]: M = sparse.coo_matrix((data,(rows, col)), shape=(10,10))                              
In [35]: M                                                                                     
Out[35]: 
<10x10 sparse matrix of type '<class 'numpy.int64'>'
    with 10 stored elements in COOrdinate format>
In [36]: M.A                                                                                   
Out[36]: 
array([[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
       [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]])

为了使用你的函数，我已经把它变成了一个二维数组：

In [39]: M1 = adj_matrix(adj[:,None])                                                          
In [40]: M1                                                                                    
Out[40]: 
<10x10 sparse matrix of type '<class 'numpy.float64'>'
    with 10 stored elements in Dictionary Of Keys format>
In [41]: M1.A                                                                                  
Out[41]: 
array([[0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 1., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1.],
       [0., 0., 0., 0., 0., 0., 0., 1., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0.],
       [0., 1., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 1., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 1., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 1., 0.]])

如果 adj 是列表的列表（或对象数组），coo 构造会稍微复杂一些。详细信息将取决于您最初 adj 的样子。目标是在矩阵的每个非零元素的 3 个 coo 输入数组中的每一个中都有一个条目。

集合列表

好的，让我们创建一个集合列表：

def foo():
    n = np.random.randint(0,10)
    return np.random.randint(0,10,(n,))

In [34]: alist = [set(foo()) for _ in range(10)]                                             
In [35]: alist                                                                               
Out[35]: 
[{0, 1, 3, 6, 9},
 {1, 9},
 {0, 2, 5},
 {0, 1, 2, 5, 8},
 {1, 4, 5, 8},
 {1, 4, 5, 6, 7, 8, 9},
 {0, 3, 4, 7, 8, 9},
 {0, 1, 4, 7},
 {0, 4, 7, 8},
 {1, 5, 7, 8, 9}]

你应该已经提供了这样的测试用例或功能。我确实要求 [mcve].

你的函数：

def adj_matrix(adj):
    n = len(adj)
    g= sparse.dok_matrix((n,n), int)
    for num, i in enumerate(adj):
        g[num, list(i)] = 1
    return g

对我以前的代码进行改编以处理新的 adj 输入：

def my_adj(adj):
    n = len(adj)
    row, col, data = [],[],[]
    for num, i in enumerate(adj):
        c = list(i)
        m = len(c)
        col.append(c)
        data.append([1]*m)
        row.append([num]*m)
    data = np.hstack(data)
    row = np.hstack(row)
    col = np.hstack(col)    
    return sparse.coo_matrix((data, (row, col)), shape=(n,n))

比较结果：

In [36]: adj_matrix(alist)                                                                   
Out[36]: 
<10x10 sparse matrix of type '<class 'numpy.float64'>'
    with 45 stored elements in Dictionary Of Keys format>
In [37]: _.A                                                                                 
Out[37]: 
array([[1., 1., 0., 1., 0., 0., 1., 0., 0., 1.],
       [0., 1., 0., 0., 0., 0., 0., 0., 0., 1.],
       [1., 0., 1., 0., 0., 1., 0., 0., 0., 0.],
       [1., 1., 1., 0., 0., 1., 0., 0., 1., 0.],
       [0., 1., 0., 0., 1., 1., 0., 0., 1., 0.],
       [0., 1., 0., 0., 1., 1., 1., 1., 1., 1.],
       [1., 0., 0., 1., 1., 0., 0., 1., 1., 1.],
       [1., 1., 0., 0., 1., 0., 0., 1., 0., 0.],
       [1., 0., 0., 0., 1., 0., 0., 1., 1., 0.],
       [0., 1., 0., 0., 0., 1., 0., 1., 1., 1.]])
In [38]: my_adj(alist)                                                                       
Out[38]: 
<10x10 sparse matrix of type '<class 'numpy.int64'>'
    with 45 stored elements in COOrdinate format>
In [39]: _.A                                                                                 
Out[39]: 
array([[1, 1, 0, 1, 0, 0, 1, 0, 0, 1],
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
       [1, 0, 1, 0, 0, 1, 0, 0, 0, 0],
       [1, 1, 1, 0, 0, 1, 0, 0, 1, 0],
       [0, 1, 0, 0, 1, 1, 0, 0, 1, 0],
       [0, 1, 0, 0, 1, 1, 1, 1, 1, 1],
       [1, 0, 0, 1, 1, 0, 0, 1, 1, 1],
       [1, 1, 0, 0, 1, 0, 0, 1, 0, 0],
       [1, 0, 0, 0, 1, 0, 0, 1, 1, 0],
       [0, 1, 0, 0, 0, 1, 0, 1, 1, 1]])

时间：

In [44]: timeit adj_matrix(alist).tocoo()                                                    
2.09 ms ± 76.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [45]: timeit my_adj(alist)                                                                
259 µs ± 203 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)

从邻接表快速创建 Scipy 稀疏矩阵

Quickly creating Scipy sparse matrix from adjacency list

graph

scipy

sparse-matrix

networkx

open3d

集合列表