Baraa - 4 months ago 90
Python Question

# Adjacency List and Adjacency Matrix in Python

Hello I understand the concepts of adjacency list and matrix but I am confused as to how to implement them in Python:

An algorithm to achieve the following two examples achieve but without knowing the input from the start as they hard code it in their examples:

For adjacency list:

``````    a, b, c, d, e, f, g, h = range(8)
N = [
{b:2, c:1, d:3, e:9, f:4},    # a
{c:4, e:3},                   # b
{d:8},                        # c
{e:7},                        # d
{f:5},                        # e
{c:2, g:2, h:2},              # f
{f:1, h:6},                   # g
{f:9, g:8}                    # h
]
``````

For adjacency matrix:

``````    a, b, c, d, e, f, g, h = range(8)
_ = float('inf')
#     a b c d e f g h
W = [[0,2,1,3,9,4,_,_], # a
[_,0,4,_,3,_,_,_], # b
[_,_,0,8,_,_,_,_], # c
[_,_,_,0,7,_,_,_], # d
[_,_,_,_,0,5,_,_], # e
[_,_,2,_,_,0,2,2], # f
[_,_,_,_,_,1,0,6], # g
[_,_,_,_,_,9,8,0]] # h
``````

Again any help will be much appreciated, Thank you!

Answer

Assuming:

``````edges = [('a', 'b'), ('a', 'b'), ('a', 'c')]
``````

Here's some code for the matrix:

``````from collections import defaultdict

matrix = defaultdict(int)
for edge in edges:
matrix[edge] += 1

print matrix['a', 'b']
``````
``````2
``````

And for the "list":

``````from collections import defaultdict

adj_list = defaultdict(lambda: defaultdict(lambda: 0))
for start, end in edges:
adj_list[start][end] += 1

print adj_list['a']
``````
``````{'c': 1, 'b': 2}
``````
Comments