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.

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