# Converting a List of arcs into Adjacency list representation for graph using dictionary

I was reading up on implementing Graphs in Python and I came across this Essay at python.org about graphs, so I decided to implement it, but with weighted edges.

I start with arcs and their cost using list of lists and then iterate through it building a dictionary (Adjacency list format) that represents the Undirected Weighted Graph. I am looking for suggestions on how to improve the following code. Here I need to check every time if a vertex already exists in the dictionary using an if x in dict.keys() statement, which takes linear time for each node.

data=[['A','B',5],
['A','C',4],
['B','C',2],
['B','D',3],
['C','D',10],
['E','F',1],['F','C',6]]

graph={}

for row in data:
if row in graph.keys():
graph[row][row]=row
if row not in graph.keys():
graph[row]={}
graph[row][row]=row
else:
graph[row][row]=row

else:
graph[row]={}
graph[row][row]=row
if row not in graph.keys():
graph[row]={}
graph[row][row]=row
else:
graph[row][row]=row

print graph


The output of the above code is:

>>{'A': {'C': 4, 'B': 5},
'C': {'A': 4, 'B': 2, 'D': 10, 'F': 6},
'B': {'A': 5, 'C': 2, 'D': 3},
'E': {'F': 1},
'D': {'C': 10, 'B': 3},
'F': {'C': 6, 'E': 1}}

• Welcome to Code Review! Good job on your first post. Oct 24, 2015 at 22:49
• Your indentation was wrong, which is a severe problem in Python. I have attempted to fix it for you in Rev 4. Please verify whether your code has been accurately represented here. Oct 25, 2015 at 7:45
• @200_success sorry about that I tabbed my code in the IDE and the pasted it here so that there it would form the code block. Thank you ! Oct 25, 2015 at 9:18

Overall this is pretty good. Here are a few suggestions for making it even better:

• You have a lot of repeated code in your if branches. Since this code will run on either iteration, it’s better to pull it out of the branches. This reduces code repetition, and makes it clearer that this code will always run. Here’s what it reduces to:

for row in data:
if row not in graph.keys():
graph[row]={}
if row not in graph.keys():
graph[row]={}
graph[row][row]=row
graph[row][row]=row


• Next you have the problem that you need to initialise every vertex with one empty dictionary. Rather than doing this by hand, you can use collections.defaultdict from the standard library. You specify a “default factory” method, and whenever you try to access a key which hasn’t already been set, it fills in the default for you.

Now the code becomes:

import collections

graph = collections.defaultdict(dict)

for row in data:
graph[row][row]=row
graph[row][row]=row


• It can be a bit unwieldy to follow these numeric indices around. You can use tuple unpacking at the top of the for loop to name the individual parts of the row:

for vertex0, vertex1, weight in data:
graph[vertex0][vertex1] = weight
graph[vertex1][vertex0] = weight


• It would be better to wrap your graph-making code in a function, graph_from_data(), so that you can reuse it in other modules.

You should also move the bits of this code that can’t be reused into an if __name__ == '__main__' block – this means the same file can be both a module and a script. If I do an import from this file, I won’t get an example graph printed as a side effect.