What is an efficient way to convert an adjacency matrix to a dictionary?

user_8812682 0
Viewed 2157

I'm wondering what is an efficient way to covert an adjacency matrix to a dictionary representing connections between one node and another?

Example matrix:

matrix = [
[0,1,0,0,0,0],
[0,0,0,0,0,0],
[0,1,0,1,0,0],
[0,0,0,0,0,0],
[0,0,0,1,0,1],
[1,0,0,0,0,0]
]

Example output:

{0: [1], 1: [], 2: [1, 3], 3: [], 4: [3, 5], 5: [0]}

My code below actually generates the correct output; however, I believe it's very inefficient because I'm using two for loops. Is there any way I can optimize my code without using any libraries? Please let me know, and thank you!

def convertAdjMatrixtoDict(m):

    graph = {}
    for idx, row in enumerate(m):
        res = []
        for r in range(len(row)):
            if row[r] != 0:
                res.append(r)
            graph[idx] = res
    return graph
adjacency-list adjacency-matrix for-loop dictionary python
2 Answers

You can get a much better performance by usung NumPy to locate nonzero elements in each row:

import numpy as np
{i: np.nonzero(row)[0].tolist() for i,row in enumerate(matrix)}

Timings for a random 1000x1000 matrix:

  1. original code: 310ms
  2. @Denxiloe's code: 91ms
  3. This code: 20ms
user_44929320

Here's a more Pythonic solution which may be a little faster.

{i: [j for j, adjacent in enumerate(row) if adjacent] for i, row in enumerate(matrix)}

I doubt you'll get much faster in raw Python. I'll think about whether there are any solutions which leverage fast libraries such as numpy.

Update: I timed the two solutions using the following.

import numpy as np

# Make a big example
num_nodes = 1000
matrix = np.random.randint(0, 2, [num_nodes, num_nodes])

# Convert to raw Python
matrix = [[element for element in row] for row in matrix]

Your solution took 0.62 seconds, mine took 0.12 seconds. So in fact there is a good speed up of a factor of about 5.

user_55068940
Related