Матрица смещения в Python

Question

Я не могу найти ясного объяснения относительно того, как создать матрицу смежности в Python с учетом веса. Я предполагаю, что это должно быть относительно просто создать.

У меня есть следующие матрицы ...

1 2 3 4 5 6 
1 0 15 0 7 10 0 
2 15 0 9 11 0 9 
3 0 9 0 0 12 7 
4 7 11 0 0 8 14 
5 10 0 12 8 0 8 
6 0 9 7 14 8 0 

Число 1 по 6 являются вершинами, а числа в сути вес между каждой соседней вершиной. Например, край 1-2 имеет вес 15.

Как реализовать это в python? Мне просто нужен простой пример, не обязательно используемый тот, который я предоставил.

Я знаю, как создать список смежности ...

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}], 
    '2': [{'3':'9'}, {'4':'11'}, {'6':'9'}], 
    '3': [{'5':'12'}, {'6':'7'}], 
    '4': [{'5':'8'}, {'6':'14'}], 
    '5': [{'6':'8'}]} 

, но мне нужна матрица смежности.

Answer 1

Я думаю, что самое распространенная и самая простая концепция для хранения матрицы смежности является использование 2D-массива, который в питоне соответствует вложенным спискам

mat = [[0, 15, 0, 7, 10, 0], [15, 0, ...], [...], [...]] 
m[0][1] # = 15 (weight of 1-2) 

Если значения только для чтения, вы можете использовать вложенные кортежи , вместо этого:

Конечно, вы можете сходить с ума, как хотите, и использовать словари или написать класс и переопределить __getattr__, чтобы быть более эффективными при доступе и хранении, поскольку матрица симметрична.

Answer 2

Мне нравятся закодированные ключи для 2d структур, подобных этому в python.

{(1, 1): 0, (3, 2): 9... } 

Я думаю, что это концептуально понятно, так как он снижает структуру промежуточных данных в вышеупомянутом решении. Тем не менее, эта промежуточная структура данных - внутренний список или строка/столбец - может быть полезна, если вы намерены получить доступ к своей структуре как в строке, так и в столбце.

for x, row in enumerated(matrix, 1): 
     # process whole row 
     for y in enumerate(row, 1): 
      # process cell... 

Если клетка-накрест доступ к данным вашей игры, хотя, это трудно превзойти следующий за выразительную простоту:

for (x, y), value in matrix.iteritems(): 
     # act on cell 

Сортировка, если вы хотите.

# (1, 1), (1, 2)... 
for (x, y), value in sorted(matrix.iteritems()): 
     # act on cell 

Answer 3

Это превращает ваш «список смежности» (на самом деле Dict, а не список) в настоящую матрицу:

import networkx as nx 

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}], 
    '2': [{'3':'9'}, {'4':'11'}, {'6':'9'}], 
    '3': [{'5':'12'}, {'6':'7'}], 
    '4': [{'5':'8'}, {'6':'14'}], 
    '5': [{'6':'8'}]} 
new_graph = nx.Graph() 
for source, targets in graph.iteritems(): 
    for inner_dict in targets: 
     assert len(inner_dict) == 1 
     new_graph.add_edge(int(source) - 1, int(inner_dict.keys()[0]) - 1, 
          weight=inner_dict.values()[0]) 
adjacency_matrix = nx.adjacency_matrix(new_graph) 

(Формат вашей не особенно удобно для использования в networkx.) networkx поддерживает все виды операций на графиках и их матрицах смежности, поэтому наличие графика в этом формате должно быть очень полезным для вас. Также обратите внимание, что я изменил график, чтобы использовать индексы Python (т. Е. Начиная с 0).

In [21]: adjacency_matrix 
Out[21]: 
matrix([[ 0., 15., 0., 7., 10., 0.], 
     [ 15., 0., 9., 11., 0., 9.], 
     [ 0., 9., 0., 0., 12., 7.], 
     [ 7., 11., 0., 0., 8., 14.], 
     [ 10., 0., 12., 8., 0., 8.], 
     [ 0., 9., 7., 14., 8., 0.]]) 

Answer 4

Как уже упоминалось ранее, стандартный способ иметь дело с матрицами в Python является использование NumPy. Вот функция, которая просто считывает матрицу смежности из списка смежности. (Неявный порядок узлов определяется явным значением параметра nodes.)

import numpy 

def weighted_adjmatrix(adjlist, nodes): 
    '''Returns a (weighted) adjacency matrix as a NumPy array.''' 
    matrix = [] 
    for node in nodes: 
     weights = {endnode:int(weight) 
        for w in adjlist.get(node, {}) 
        for endnode, weight in w.items()} 
     matrix.append([weights.get(endnode, 0) for endnode in nodes]) 
    matrix = numpy.array(matrix) 
    return matrix + matrix.transpose() 

В этом случае weighted_adjmatrix(graph, nodes=list('123456')) дает массиву Numpy

array([[ 0, 15, 0, 7, 10, 0], 
     [15, 0, 9, 11, 0, 9], 
     [ 0, 9, 0, 0, 12, 7], 
     [ 7, 11, 0, 0, 8, 14], 
     [10, 0, 12, 8, 0, 8], 
     [ 0, 9, 7, 14, 8, 0]]) 

Если обычный список желателен, метод tolist() можно назвать.