Матрица меток к матрице смежности

Просто интересно, есть ли готовая функция для выполнения следующей операции; учитывая матрицу X, содержащую метки (которые можно считать целыми числами от 0 до N) в каждой записи, например:

X = [[0 1 1 2 2 3 3 3],
     [0 1 1 2 2 3 3 4],
     [0 1 5 5 5 5 3 4]]

Мне нужна его матрица смежности G, т.е. G[i,j] = 1, если i,j смежны в X, и 0 в противном случае.

Например, G[1,2] = 1, потому что 1,2 являются смежными в (X[0,2],X[0,3]), (X[1,2],X[1,3]) и т. д. ..

Наивное решение состоит в том, чтобы перебирать все записи и проверять их соседей, но я бы предпочел избегать циклов из соображений производительности.


python numpy arrays matrix adjacency-matrix
person memecs    schedule 21.10.2014    source источник
comment
Я не получил представления вашей матрицы смежности в X, не могли бы вы объяснить больше?   -  person Saullo G. P. Castro    schedule 21.10.2014
comment
не может преобразовывать данные без их чтения, любая готовая функция будет зацикливаться на этих записях за сценой, поэтому с точки зрения производительности вы ничего не сохраните.   -  person yurib    schedule 21.10.2014
comment
@SaulloCastro: я добавил пример. Это помогает?   -  person memecs    schedule 21.10.2014
comment
@yurib: Конечно, но, возможно, цикл написан на C++   -  person memecs    schedule 21.10.2014

Ответы (1)


arrow_upward
4
arrow_downward

Вы можете использовать причудливую индексацию, чтобы присвоить значения G непосредственно из вашего массива X:

import numpy as np

X = np.array([[0,1,1,2,2,3,3,3],
              [0,1,1,2,2,3,3,4],
              [0,1,5,5,5,5,3,4]])
G = np.zeros([X.max() + 1]*2)

# left-right pairs
G[X[:, :-1], X[:, 1:]] = 1
# right-left pairs
G[X[:, 1:], X[:, :-1]] = 1
# top-bottom pairs
G[X[:-1, :], X[1:, :]] = 1
# bottom-top pairs
G[X[1:, :], X[:-1, :]] = 1

print(G)
#array([[ 1.,  1.,  0.,  0.,  0.,  0.],
#       [ 1.,  1.,  1.,  0.,  0.,  1.],
#       [ 0.,  1.,  1.,  1.,  0.,  1.],
#       [ 0.,  0.,  1.,  1.,  1.,  1.],
#       [ 0.,  0.,  0.,  1.,  1.,  0.],
#       [ 0.,  1.,  1.,  1.,  0.,  1.]])
person Saullo G. P. Castro    schedule 21.10.2014
comment
Отличное решение, спасибо! Только одно быстрое решение: для связи с 4 соседями, которую я искал, добавьте G[X[:, 1:], X[:, :-1]] = 1; G[X[1:, :], X[:-1, :]] = 1; G[X[:-1, :], X[1:, :]] = 1. - person memecs; 21.10.2014
comment
@memecs, ты имеешь в виду... сделать G симметричным? - person Saullo G. P. Castro; 21.10.2014
comment
Это не только делает матрицу симметричной. Прямо сейчас вы рассматриваете только правильных соседей. Из-за этого G[2,5] равен 0 в вашем решении, но должен быть равен 1. - person memecs; 21.10.2014