Adjacency List Representation to Adjacency Matrix in Python

Question

Given the two Adjacency List Representation below

g = {
'I': ['J', 'K', 'M'],
'J': ['I', 'K', 'L'],
'K': ['I', 'J', 'M'],
'L': ['J'],
'M': ['I', 'K']
}

#Weighted 
g = {
'I': [('J', 1), ('K', 2), ('M', 3)],
'J': [('I', 1), ('K', 7), ('L', 5)],
'K': [('I', 2), ('J', 7), ('M', 6)],
'L': [('J', 5)],
'M': [(I, 3), (K, 6)]
}

How can I output an equivalent adjacency matrix in the form of a list of lists especially for the Weighted Adjacency List. I have applied the algorithm of karakfa from How do I generate an adjacency matrix of a graph from a dictionary in python?. However, I can't seem to implement it to weighted graphs.

keys = sorted(g.keys())
M = [ [0]*len(keys) for i in range(len(keys)) ]
for a,b in [(keys.index(a), keys.index(b)) for a, row in g.items() for b in row]:
   M[a][b] = 1

It returns ValueError: ('J', 1) is not in list

Your I and J in the second list are missing string quotes. — Ngoc N. Tran
– Ngoc N. Tran, Commented Jan 8, 2021 at 6:22

Ngoc N. Tran · Accepted Answer · 2021-01-08 06:28:55Z

2

The reason is that your dictionary keys are your vertex names, but you are passing a tuple of (vertex_name, weight). Also, the variable names are confusing and might cause a bug (b is used twice).

keys = sorted(g.keys())
M = [ [0]*len(keys) for i in range(len(keys)) ]
for vertex_1, row in g.items():
    for vertex_2, weight in row:
        M[keys.index(vertex_1)][keys.index(vertex_2)] = weight

This gives:

[[0, 1, 2, 0, 3],
 [1, 0, 7, 5, 0],
 [2, 7, 0, 0, 6],
 [0, 5, 0, 0, 0],
 [3, 0, 6, 0, 0]]

answered Jan 8, 2021 at 6:28

Ngoc N. Tran

1,0683 gold badges10 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Adjacency List Representation to Adjacency Matrix in Python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related