Adjacency List and Adjacency Matrix in Python

Solution 1:

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}

Solution 2:

Setting up your data structures can be pretty simple. For instance, the adjacency list example can be implemented using a defaultdict like this:

from collections import defaultdict

N = defaultdict(dict)

Then when you start getting input, just do N[start][end] = weight for each inputted edge. The set of nodes will be a little more tricky to come by, if you have some nodes with no outbound edges (you'll need to union the keys of the inner dictionaries with the outer one to be sure you have them all). But a lot of algorithms will work correctly even without a complete node list.

The adjacency matrix is a little more complicated, since you need to know the number of nodes there are in order to set its dimensions correctly. If you know it ahead of time, then its easy:

number_of_nodes = 8
_ = float("inf")

N = [[_]*number_of_nodes for i in number_of_nodes]

If you don't, you'll probably want to scan over the edges you get as input to find the highest numbered node, then use the same code above to make the matrix. For instance, if your edges are provided as a list of (start, end, weight) 3-tuples, you can use this:

number_of_nodes = max(max(start, end) for start, end, weight in edges)