В основном я долго ломал себе голову над тем, почему мой код не работает, я тестировал отдельные части и смотрел по всему Интернету, чтобы узнать, может ли он помочь, но безрезультатно. Я получаю сообщение об ошибке:
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. Вы пытаетесь добавить в список, который еще не существует.
Попробуйте вместо этого использовать defaultdict, заменив эту строку (в __init__):
self.adj = {}
с этим:
self.adj = defaultdict(list)
Вам нужно будет импортировать вверху:
from collections import defaultdict
Теперь вместо того, чтобы вызывать KeyError, self.adj[0].append(edge) автоматически создаст список для добавления.
Решение defaultdict лучше. Но для полноты вы также можете проверить и создать пустой список перед добавлением. Добавьте строки +:
+ if not u in self.adj.keys():
+ self.adj[u] = []
self.adj[u].append(edge)
.
.
Попробуйте это:
class Flonetwork(Object):
def __init__(self,adj = {},flow={}):
self.adj = adj
self.flow = flow
Это происходит только тогда, когда ваш список или словарь недоступен в локальной функции.