Для оптимизации цикла для создания матрицы смежности
В настоящее время я работаю с графом с помеченными ребрами. Исходная матрица смежности представляет собой матрицу формы [n_nodes, n_nodes, n_edges], где каждая ячейка [i,j, k] равна 1, если узлы i и j соединены ребром k.
Мне нужно создать реверс исходного графа, где узлы становятся ребрами, а ребра становятся узлами, поэтому мне нужна новая матрица с формой [n_edges, n_edges, n_nodes], где каждая ячейка [i,j,k] равна 1, если ребра i и j имеют k как общую вершину.
Следующий код корректно выполняет задачу, но использование 5 вложенных циклов for слишком медленное, чтобы обработать количество графов, с которыми мне приходится работать, кажется, около 700 часов.
Есть ли лучший способ реализовать это?
n_nodes = extended_adj.shape[0]
n_edges = extended_adj.shape[2]
reversed_graph = torch.zeros(n_edges, n_edges, n_nodes, 1)
for i in range(n_nodes):
for j in range(n_nodes):
for k in range(n_edges):
#If adj_mat[i][j][k] == 1 nodes i and j are connected with edge k
#For this reason the edge k must be connected via node j to every outcoming edge of j
if extended_adj[i][j][k] == 1:
#Given node j, we need to loop through every other possible node (l)
for l in range(n_nodes):
#For every other node, we need to check if they are connected by an edge (m)
for m in range(n_edges):
if extended_adj[j][l][m] == 1:
reversed_graph[k][m][j] = 1
Спасибо заранее.
Пхе, только сейчас понял твой предыдущий (удаленный) вопрос. Там вы могли бы получить лучшую обратную связь, если бы сказали, что рассматриваемый тензор предназначен для представления графов.
@AlexeyBirukov удаленный вопрос был предназначен для объединения графиков, и я его решил, это еще одна проблема.
Да я получил его. Вы зря удалили свой вопрос, лучше бы вы дополнили информацию и предоставили решение.
Что касается нового, [n_edges, n_edges, n_узлов] скорее будет [n_edges, n_edges, new_edges], не так ли?
@AlexeyBirukov каждая пара ребер может иметь общий один из исходных узлов, и мне нужно отслеживать, какой из них их соединяет, поэтому new_edges равен n_nodes
Это представление графа ужасно неэффективно. Почему бы вам не использовать квадратную матрицу, в которой элементы являются номером ребра? (И зарезервированное значение для «не края»)
Ответы 1
Вторя комментариям выше, это представление графа почти наверняка громоздко и неэффективно. Но, несмотря на это, давайте определим векторизованное решение без циклов, которое по возможности использует тензорные представления, что должно быть достаточно эффективным для вычислений для больших графов.
Для ясности давайте использовать [i,j,k] для индексации G (исходный график) и [i',j',k'] для индексации G' (новый график). И давайте сократим n_edges до e и n_nodes до n.
Рассмотрим двумерную матрицу slice = torch.max(G,dim = 1). В каждой координате [a,b] этого среза 1 указывает, что узел a соединен ребром b с каким-то другим узлом (нам все равно с каким).
slice = torch.max(G,dim = 1) # dimension [n,e]
Мы уже на пути к решению, но нам нужно выражение, которое говорит нам, связано ли a с ребром b и другим ребром c для всех ребер c. Мы можем отобразить все комбинации b,c, расширив slice, скопировав и переместив их, а также найдя пересечения между ними.
expanded_dim = [slice.shape[0],slice.shape[1],slice.shape[1]] # value [n,e,e]
# two copies of slice, expanded on different dimensions
expanded_slice = slice.unsqueeze(1).expand(expanded_dim) # dimension [n,e,e]
transpose_slice = slice.unsqueeze(2).expand(expanded_dim) # dimension [n,e,e]
G = torch.bitwise_and(expanded_slice,transpose_slice).int() # dimension [n,e,e]
G[i',j',k'] теперь равно 1 тогда и только тогда, когда узел i' соединен ребром j' с каким-то другим узлом, И узел i' соединен ребром k' с каким-то другим узлом. Если j' = k' значение равно 1, если одна из конечных точек этого ребра равна i'.
Наконец, мы изменяем размеры, чтобы получить желаемую форму.
G = torch.permute(G,(1,2,0)) # dimension [e,e,n]
Может быть, это могло бы помочь: «Матрица смежности ребер графа G идентична матрице смежности вершин линейного графа L (G) графа G»