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

Question

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[0] in graph.keys():
        graph[row[0]][row[1]]=row[2]
        if row[1] not in graph.keys():
            graph[row[1]]={}
            graph[row[1]][row[0]]=row[2]
        else:
            graph[row[1]][row[0]]=row[2]

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


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}}

Answer 1

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[0] not in graph.keys():
          graph[row[0]]={}
      if row[1] not in graph.keys():
          graph[row[1]]={}
      graph[row[0]][row[1]]=row[2]
      graph[row[1]][row[0]]=row[2]
  

• 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[0]][row[1]]=row[2]
      graph[row[1]][row[0]]=row[2]
  

• 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.