# Adjacency List Graph representation on python

I began to have my Graph Theory classes on university, and when it comes to representation, the adjacency matrix and adjacency list are the ones that we need to use for our homework and such. At the beginning I was using a dictionary as my adjacency list, storing things like this, for a directed graph as example:

graph = {
0: [1, 2, 4],
1: [2, 3],
2: [],
3: ,
4: ,
}


There was no problem, since the graphs I was dealing with had no weight in their edges, and if I wanted to represent an undirected graph, just had to "mirror" the edges. Now I'm facing a problem with the representation in adjacency list for weighted graphs, being directed or undirected.

So far, this is what I'm using:

class Graph:

def __init__(self, vertices, is_undirected=True):
self.__v = vertices  # number of vertices
self.__edge_list = []  # store the edges and their weight
self.__is_undirected = is_undirected # True for undirected graphs

# method for adding an edge to the graph
self.__edge_list.append([u, v, w if w else 1])
# in case it is an undirected graph,
# replicate edge in opposite way
if self.__is_undirected:
self.__edge_list.append([v, u, w if w else 1])


And this is the method for making my adjacency list using the __edge_list:

def make_adjacency_list(self):
adj_list = {key: [] for key in range(self.__v)}
for edge in self.__edge_list:
# where edge is the destiny and edge the weight
edge_val = {edge: edge}


Also, the graph will be generated from a file, formatted as such:

0 # 0 for directed graph
5 # number of vertices
0 2 4 # edge from u to v, with w weight
0 4 60
0 3 23
2 3 4
3 1 10
4 2 15


This results in the following:

0 = [{2: 4}, {4: 60}, {3: 23}]
1 = []
2 = [{3: 4}]
3 = [{1: 10}]
4 = [{2: 15}]


The problem with this is that is becomes very hard, at least for me, to recover the data for each edge from my adjacency list, so I was wondering if this the right way to do it, or if I can be more efficient in what I'm trying to do. My current algorithms for BFS(breadth first search), DFS( depth first search), Kruskal, Prim and Djikstra are having problems in this structure I made, but I can't see another way of doing it unless I move the adjacency list in a separate class.

Lastly, and code-improvement/advice in more pythonic ways of doing things would be welcome. I tried as best as I could to make this code clean, but now it is a mess(not proud of that). If there's need of any other bit of code or clarification I'll answer as best as I can. I tried going to the professor, but he's more of a Java person, so he couldn't help much.

• I would just use Sage. It is well known to have an extensive graph theory library. Unless you need to reimplement stuff.
– Dair
May 15, 2017 at 22:31
• That's my problem. We can't use something that is already done. That's why I went in the dictionary direction May 16, 2017 at 13:29
• It might be better to have each neighbor for the node stored as a set, to make lookups constant. For reference, here is a good article on how to implement an adjacency list in Python. Mar 14, 2020 at 19:32

Here are two ways you could represent a graph with weighted edges in Python:

1. Represent a graph as a mapping from a node $n$ to a mapping from neighbouring node $m$ to the weight $w$ of the edge from $n$ to $m$:

graph = {
0: {2: 4, 4: 60, 3: 23},
1: {},
2: {3: 4},
3: {1: 10},
4: {2: 15},
}

2. Represent a graph as a pair of mappings: one from a node $n$ to a list of its neighbouring nodes, and the other from pairs of nodes $n, m$ to the weight $w$ of the edge from $n$ to $m$:

graph = {
0: [2, 4, 3],
1: [],
2: ,
3: ,
4: ,
}
weights = {
(0, 2): 4,
(0, 4): 60,
(0, 3): 23,
(2, 3): 4,
(3, 1): 10,
(4, 2): 15,
}


Either of these representations should work fine. Representation (2) would be good if you need to iterate over all the edges at some point in your algorithm. Representation (1) is the simplest and probably best if you have no special requirements.

1. You don't even need .keys() — in Python, iterating over a dictionary yields its keys, so you can write:

for m in graph[n]:
# m is a neighbour of n

2. Yes, defaultdict is a useful technique for building graphs. In representation (1) you'd start with:

graph = defaultdict(dict)


and then add an edge from $n$ to $m$ with weight $w$ by writing:

graph[n][m] = w


graph = defaultdict(list)
edges = {}


and then add an edge from $n$ to $m$ with weight $w$ by writing:

graph[n].append(m)
edges[n, m] = w

• My thnkas for your answer, I was thinking in something along this lines. In the first case, is there any way I could iterate in the neighbours? like in a for i in graph: for instance? In this case, I don't care about the weights, just the keys. May 16, 2017 at 19:25
• Also, is this a case where using the defaultdict from collections would be better than declaring an empty dictionary for initialization? I am not a beginner, but still don't have exactly sure what is better for each case. May 16, 2017 at 19:35
• I just realized that I can use .keys() in that case. I fell kind of stupid. I'll wait for your return about the defaultdict question above and mark this as solved. May 16, 2017 at 20:17
• @inblank: See revised answer. May 16, 2017 at 21:06
• Thanks @gareth-rees. You helped a lot, I will only have to do some tweaking in my previous algorithms to work in the new representation. I choose representation 1, since I can concentrate all representation in one single class variable. Marking as solved. May 16, 2017 at 21:34