Adjacency List Graph representation on python

Question

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],
 4: [0],
}

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
 self.__adj_matrix = None # stores the adjacency matrix
 self.__adj_list = None # stores the adjacency list
 # method for adding an edge to the graph
 def add_edge(self, u, v, w=None):
 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[1] is the destiny and edge[2] the weight
 edge_val = {edge[1]: edge[2]} 
 adj_list[edge[0]].append(edge_val)
 self.__adj_list = adj_list

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.

• Dair: I would just use Sage. It is well known to have an extensive graph theory library. Unless you need to reimplement stuff.
• inblank: That's my problem. We can't use something that is already done. That's why I went in the dictionary direction
• Neethan Badea: 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.

Answer 1

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],
    3: [1],
    4: [2],
   }
   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.

Answers to comments

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
   

   In representation (2) you'd start with:

   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
   

• inblank: 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[0]: for instance? In this case, I don't care about the weights, just the keys.
• inblank: 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.
• inblank: 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.
• Gareth Rees: @inblank: See revised answer.
• inblank: 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.