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.

  • 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 '17 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 – inblank May 16 '17 at 13:29
up vote 6 down vote accepted

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
    
  • 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 May 16 '17 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. – inblank May 16 '17 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. – inblank May 16 '17 at 20:17
  • @inblank: See revised answer. – Gareth Rees May 16 '17 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. – inblank May 16 '17 at 21:34

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.