Adjacency matrix in Python

Question

I cannot find any clear explanation as to how to create an adjacency matrix in Python, with weights taken into consideration. I assume it should be relatively simple to create.

I have the following matrix...

   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

The numbers 1 through 6 are vertices, and the numbers within are the weights between each neighbouring vertex. For example, edge 1-2 has weight 15.

How would I implement this in python? I just need a simple example, not necessarily using the one I provided.

I know how to create an adjacency list...

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'}]}

but I need an adjacency matrix.

Answer 1

This converts your "adjacency list" (really a dict, not a list) into a genuine matrix:

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)

(The format of your graph is not particularly convenient for use in networkx.) networkx supports all kinds of operations on graphs and their adjacency matrices, so having the graph in this format should be very helpful for you. Note also that I've shifted your graph to use Python indices (i.e., starting at 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 2

I think the most common and simplest concept to store an adjacency matrix is to use a 2D array, which in python corresponds to nested lists

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

If the values are read only, you can use nested tuples, instead :)

Of course you can go as crazy as you want with that and use dictionaries or write a class and redefine __getattr__ to be more efficient on access times and storage as the matrix is symmetrical.