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