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

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

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

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

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

Мне нравятся tuple-ключи для таких двумерных структур в 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

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

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)

(Формат вашего 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.]])

Как упоминалось ранее, стандартным способом работы с матрицами в 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().