Быстрое создание разреженной матрицы Scipy из списка смежности - PullRequest
Новая
       46

Быстрое создание разреженной матрицы Scipy из списка смежности

0 голосов
/ 28 марта 2020

Я пытаюсь создать граф networkx из списка смежности. В настоящее время я делаю следующее, что медленно. Я изучил параметры матрицы scipy.sparse и, насколько я мог судить, ни один из них не был в том же формате, что и то, с чем я работаю. Это усложняется тем, что каждый элемент в adj может иметь разную длину.

o3dme sh .adjacency list возвращает список наборов. Множество 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)

1 Ответ

1 голос
/ 28 марта 2020

Я не знаком с networkx или вашим списком прилагательных. Но из кода я предполагаю, что это список или массив целых чисел в диапазоне (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]])

Хотя, чтобы использовать вашу функцию, я должен превратить это в 2d массив: 

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

Адаптация моего предыдущего кода для обработки нового ввода приставки: 

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)
...