user3573321 user3573321 - 1 year ago 94
Python Question

Python Key Error=0 - Can't find Dict error in code

basically I have been racking my brains for a good while now as to why my code is not working, I have tested parts separately and have look throughout the web to see if it can help, to no avail.
I am getting an error that the traceback is:

Traceback (most recent call last):
File "yes2.py", line 62, in <module>
g.add_edge(row_index,col_index, b)
File "yes2.py", line 27, in add_edge
self.adj[u].append(edge)
KeyError: 0


The two parts with errors are

def add_edge(self, u, v, w=0):
if u == v:
raise ValueError("u == v")
edge = Edge(u,v,w)
redge = Edge(v,u,0)
edge.redge = redge
redge.redge = edge
self.adj[u].append(edge) #### LINE 27 ####
self.adj[v].append(redge)
self.flow[edge] = 0
self.flow[redge] = 0


and

g = FlowNetwork()
map(g.add_vertex, ['0','1','2','3','4','5','6'])
with open('network.txt', "r") as file:
for row_index, row in enumerate(file):
for col_index, value in enumerate(row.split(",")):
b = int(value)
if b != 0:
g.add_edge(row_index,col_index, b) ### LINE 62 ####


And here is the completed code, as without this it may be difficult to see what is happening

class Edge(object):
def __init__(self, u, v, w):
self.source = u
self.sink = v
self.capacity = w
def __repr__(self):
return "%s->%s:%s" % (self.source, self.sink, self.capacity)

class FlowNetwork(object):
def __init__(self):
self.adj = {}
self.flow = {}

def add_vertex(self, vertex):
self.adj[vertex] = []

def get_edges(self, v):
return self.adj[v]

def add_edge(self, u, v, w=0):
if u == v:
raise ValueError("u == v")
edge = Edge(u,v,w)
redge = Edge(v,u,0)
edge.redge = redge
redge.redge = edge
self.adj[u].append(edge)
self.adj[v].append(redge)
self.flow[edge] = 0
self.flow[redge] = 0

def find_path(self, source, sink, path):
if source == sink:
return path
for edge in self.get_edges(source):
residual = edge.capacity - self.flow[edge]
if residual > 0 and not (edge,residual) in path:
result = self.find_path( edge.sink, sink, path + [(edge,residual)] )
if result != None:
return result

def max_flow(self, source, sink):
path = self.find_path(source, sink, [])
while path != None:
flow = min(res for edge,res in path)
for edge,res in path:
self.flow[edge] += flow
self.flow[edge.redge] -= flow
path = self.find_path(source, sink, [])
return sum(self.flow[edge] for edge in self.get_edges(source))

g = FlowNetwork()
map(g.add_vertex, ['0','1','2','3','4','5','6'])
with open('network.txt', "r") as file:
# enumerate allows you to iterate through the list with an index and an object
for row_index, row in enumerate(file):
# split allows you to break a string apart with a string key
for col_index, value in enumerate(row.split(",")):
#convert value from string to int
b = int(value)
if b != 0:
g.add_edge(row_index,col_index, b)

print g.max_flow('1','6')


Many thanks for your time, much appreciated.

Answer Source

The error you're getting is that self.adj doesn't already have a key 0. You're trying to append to a list that doesn't exist yet.

Consider using a defaultdict instead, replacing this line (in __init__):

self.adj = {}

with this:

self.adj = defaultdict(list)

You'll need to import at the top:

from collections import defaultdict

Now rather than raise a KeyError, self.adj[0].append(edge) will create a list automatically to append to.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download