基本上,我已经绞尽脑汁好一阵子了,为什么我的代码不能工作,我已经分别测试了部分,并在整个网络上寻找,看看它是否可以帮助,但没有效果。 我得到一个错误,回溯是:
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
有错误的两部分是
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
以及
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 ####
下面是完整的代码,如果没有它,可能很难看到发生了什么
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')
非常感谢您抽出时间,非常感谢。
您得到的错误是
self.adj
没有键0
。您试图附加到一个尚不存在的列表。考虑改用^{} ,替换这一行(在
__init__
中):有了这个:
您需要在顶部导入:
现在,
self.adj[0].append(edge)
将自动创建一个要附加到的列表,而不是引发一个KeyError
。试试这个:
defaultdict解决方案更好。 但是为了完整起见,您还可以在追加之前检查并创建空列表。 添加+行:
相关问题 更多 >
编程相关推荐