Numpy- получить соседей матрицу из 2D массива

Question

У меня есть неориентированный граф определяется по формуле:

A,B 
A,C 
A,F 
B,D 
C,D 
C,F 
E,D 
E,F 

И мне нужно, чтобы преобразовать это в матрицу N, где

N[x,y] = 1 if x is neighbor of y (like A and B) and 0 if not 

Какой самый быстрый способ сделай это?

NOTA Граф хранится в виде Numpy массив строк:

array([['A', 'B'], 
     ['A', 'C'], 
     ['A', 'F'], 
     ['B', 'D'], 
     ['C', 'D'], 
     ['C', 'F'], 
     ['E', 'D'], 
     ['E', 'F']], 
     dtype='|S4') 

Ожидаемая мощность:

A B C D E F 
A 1 1 1 0 0 1 
B 1 1 0 1 0 0 
C 1 0 1 1 0 1 
D 0 1 1 1 1 0 
E 0 0 0 1 1 1 
F 1 0 1 0 1 1 

Благодаря

Answer 1

Вот один NumPythonic подход -

# Tag each string with a numeric ID based on the uniqueness among other strings 
_,ID = np.unique(graph,return_inverse=True) 
M = ID.reshape(graph.shape) 

# Consider each row of numeric IDs as an indexing tuple of a 2D array. 
# Calculate the linear indices corresponding to each tuple. 
n = M.max()+1 
idx1 = M[:,0]*(n) + M[:,1] 
idx2 = M[:,1]*(n) + M[:,0] 

# Setup output array with 1s on the diagonal. 
out = np.eye(n,dtype=int) 

# Put 1s at places specified by the earlier computed pairs of linear indices 
np.put(out,[idx1,idx2],1) 

вход образца, выход -

In [93]: graph 
Out[93]: 
array([['A', 'B'], 
     ['A', 'C'], 
     ['A', 'F'], 
     ['B', 'D'], 
     ['C', 'D'], 
     ['C', 'F'], 
     ['E', 'D'], 
     ['E', 'F']], 
     dtype='|S4') 

In [94]: out 
Out[94]: 
array([[1, 1, 1, 0, 0, 1], 
     [1, 1, 0, 1, 0, 0], 
     [1, 0, 1, 1, 0, 1], 
     [0, 1, 1, 1, 1, 0], 
     [0, 0, 0, 1, 1, 1], 
     [1, 0, 1, 0, 1, 1]]) 

---

выполнения тестов

В этом разделе в основном сравнивает все подходы (в этой должности и другие должности) перечислены до сих пор на производительность, чтобы решить дело.

Определение функции -

def networkx_based(a): #@atomh33ls's solution code 
    A=nx.Graph() 
    for x in a: 
     A.add_edge(x[0],x[1]) 
    return nx.adjacency_matrix(A) 

def vectorize_based(data): # @plonser's solution code 
    ord_u = np.vectorize(lambda x: ord(x)-65) 
    s = ord_u(data) 
    res = np.zeros((s.max()+1,s.max()+1),dtype=int) 
    res[s[:,0],s[:,1]] = 1 
    res_sym = res + res.T 
    np.fill_diagonal(res_sym,1) 
    return res_sym 

def unique_based(graph): #solution from this post 
    _,ID = np.unique(graph,return_inverse=True) 
    M = ID.reshape(graph.shape) 
    n = M.max()+1 
    idx1 = M[:,0]*(n) + M[:,1] 
    idx2 = M[:,1]*(n) + M[:,0] 
    out = np.eye(n,dtype=int) 
    np.put(out,[idx1,idx2],1) 
    return out 

тайминги -

In [321]: N = 1000 

In [322]: arr = np.random.randint(65,90,(N,2)) 

In [323]: graph = np.array([map(chr,a) for a in arr],dtype='S4') 

In [324]: %timeit networkx_based(graph) 
100 loops, best of 3: 3.79 ms per loop 

In [325]: %timeit vectorize_based(graph) 
1000 loops, best of 3: 760 µs per loop 

In [326]: %timeit unique_based(graph) 
1000 loops, best of 3: 405 µs per loop 

Answer 2

Использование networkx:

A=nx.Graph() 
for x in a: 
    A.add_edge(x[0],x[1]) 
ad =nx.adjacency_matrix(A) 

дает

matrix([[ 0., 1., 1., 0., 0., 1.], 
     [ 1., 0., 0., 0., 1., 1.], 
     [ 1., 0., 0., 0., 1., 0.], 
     [ 0., 0., 0., 0., 1., 1.], 
     [ 0., 1., 1., 1., 0., 0.], 
     [ 1., 1., 0., 1., 0., 0.]]) 

Предлагайте fill_diagonal получить самое-ссылку, как в вашем ожидаемом результате:

np.fill_diagonal(ad,1) 

matrix([[ 1., 1., 1., 0., 0., 1.], 
     [ 1., 1., 0., 1., 0., 0.], 
     [ 1., 0., 1., 1., 0., 1.], 
     [ 0., 1., 1., 1., 1., 0.], 
     [ 0., 0., 0., 1., 1., 1.], 
     [ 1., 0., 1., 0., 1., 1.]]) 

Answer 3

В чистом numpy я бы сделать что-то вроде

import numpy as np 

data = np.array([['A', 'B'], 
     ['A', 'C'], 
     ['A', 'F'], 
     ['B', 'D'], 
     ['C', 'D'], 
     ['C', 'F'], 
     ['E', 'D'], 
     ['E', 'F']], dtype='|S4') 

# define vectorized mapping from letters to integers 
ord_u = np.vectorize(lambda x: ord(x)-65) 

# map entities of data to integer 
s = ord_u(data) 

# initialize the matrix 
res = np.zeros((s.max()+1,s.max()+1)) 

# use advanced indexing for calculating the matrix 
res[s[:,0],s[:,1]] = 1 

# symmetrize the matrix 
res_sym = res + res.T 
np.fill_diagonal(res_sym,1) 

res_sym 
#array([[ 1., 1., 1., 0., 0., 1.], 
#  [ 1., 1., 0., 1., 0., 0.], 
#  [ 1., 0., 1., 1., 0., 1.], 
#  [ 0., 1., 1., 1., 1., 0.], 
#  [ 0., 0., 0., 1., 1., 1.], 
#  [ 1., 0., 1., 0., 1., 1.]])