Adjacency matrix in Python

buydadip picture buydadip · Apr 6, 2015 · Viewed 61.6k times · Source

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

jwilner picture jwilner · Apr 6, 2015

I like tupled keys for 2d structures like this in python.

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

I think it's conceptually clearest since it drops the intermediary data structure in the above solution. Nonetheless, that intermediary data structure -- the inner list or row / column-- can be useful if you intend to access your structure either row or column wise.

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

If cell-wise data access is your game though, it's hard to beat the following for expressive simplicity:

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

Sort it if you want.

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