4

私は以下によって与えられる無向グラフを持っています:

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

それを行う最も速い方法は何ですか？

注意: グラフは文字列の 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

ありがとう

4

3 に答える 3

4

これがNumPythonicアプローチの1つです-

# 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
于 2015-11-13T14:49:09.847 に答える
4

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.]])
于 2015-11-13T14:28:03.230 に答える
1

純粋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.]])
于 2015-11-13T14:48:25.500 に答える