最大流，最小费用最大流问题 python
徐少华 算法设计与分析 P145
代码实现
import itertools
class Node:
def __init__(self, name):
"""
:param name:节点的名字
"""
self.name = name
self.next_nodes = set()
self.prev_nodes = set()
self.tag = None
def add_next_node(self, next_node):
"""
添加后向节点
:param next_node:
:return:
"""
self.next_nodes.add(next_node)
def add_prev_node(self, prev_node):
"""
添加前向节点
:param prev_node:
:return:
"""
self.prev_nodes.add(prev_node)
def update_tag(self, tag):
self.tag = tag
def del_tag(self):
self.tag = None
def __str__(self):
str_node = f"{self.name} " \
f"\t tag:{self.tag} " \
f"\t next_node:{[i.name for i in self.next_nodes]} " \
f"\t prev_node:{[j.name for j in self.prev_nodes]} "
return str_node
class Graph:
def __init__(self, nodes, edges):
self.nodes = dict()
for i in nodes:
self.nodes[i] = Node(i)
self.edges = dict()
for i in edges:
start = i[0]
end = i[1]
weight = i[2]
self.edges[(i[0], i[1])] = Edge(start, end, weight)
self.nodes[start].add_next_node(self.nodes[end])
self.nodes[end].add_prev_node(self.nodes[start])
self.head_node = self.nodes['vs']
self.tail_node = self.nodes['vt']
def get_node_names(self):
return list(self.nodes.keys())
def get_edge_names(self):
return list(self.edges.keys())
def get_nodes(self):
return list(self.nodes.values())
def get_costs(self):
return sum(i.weight[1] * i.weight[2] for i in self.edges.values())
def __str__(self):
nodes_str = "Nodes:" + str([i.name for i in self.nodes.values()])
edges_str = "Edges:\n\t" + "\n\t".join([str(i) for i in self.edges.values()])
return nodes_str + "\n" + edges_str
def clean_node_tag(self):
# 清除所有节点的标号
for i in self.nodes.keys():
self.nodes[i].update_tag(None)
def update_flow(self, path, theta, by):
path = list(path)
if by == "by_flow":
# 在增流圈中，需要对圈进行调整，使路径变成环
path.insert(0, path[-1])
for i in range(1, len(path)):
start = path[i - 1].name
end = path[i].name
key = (start, end)
if key in self.edges:
# 正向弧
weight = list(self.edges[key].weight)
weight[1] += theta
else:
key = tuple(reversed(key))
weight = list(self.edges[key].weight)
weight[1] -= theta
self.edges[key].weight = tuple(weight)
def is_add_loop(self, neg_loop):
# 判断负回路是否是增流圈
for i in range(len(neg_loop)):
start = neg_loop[i - 1].name
end = neg_loop[i].name
key = (start, end)
if key in self.edges:
# 正向弧
weight = list(self.edges[key].weight)
if not weight[0] > weight[1]:
return False
else:
key = tuple(reversed(key))
weight = list(self.edges[key].weight)
if weight[1] == 0:
return False
else:
return True
def find_loop(self):
# 寻找回路
# 构成（负）回路至少两3个点
for i in range(3, len(self.nodes) + 1):
for j in itertools.permutations(self.nodes.values(), i):
if is_path(j, isloop=True):
yield j
def find_neg_loop(self):
"""
寻找负回路
:return: 【迭代器】 一个负回路
"""
mat = []
for i in self.find_loop():
val = 0
min_theta = inf
for j in range(len(i)):
weight = self.edges[(i[j - 1].name, i[j].name)].weight
val += weight[1]
min_theta = min(min_theta, weight[0])
if val < 0:
l = set([j.name for j in i])
if l not in mat:
mat.append(l)
yield i, min_theta
def find_chain(self):
"""
查找所有链（链的起始点为起点，结束点为收点，路径但忽略方向）
:param self:
:return:
"""
head_node = self.head_node
tail_node = self.tail_node
def gen_full_chain(u, u_tag_path):
full_chain = [self.head_node]
full_chain.extend(u)
full_chain.append(self.tail_node)
u_tag_path.append(True)
return full_chain, u_tag_path
nodes_ex = self.get_nodes()
nodes_ex.remove(head_node)
nodes_ex.remove(tail_node)
all_path_u = []
for i in range(1, len(nodes_ex) + 1):
all_path_u.extend(list(itertools.permutations(nodes_ex, i)))
all_chain_u = all_path_u
for i in all_chain_u:
if i[0] not in head_node.next_nodes or i[-1] not in tail_node.prev_nodes:
# 构不成一条链
continue
tag_path = [True]
# 标注在图上的方向，是正向还是反向
if len(i) == 1:
# 只有一个中间节点的情况
yield gen_full_chain(i, tag_path)
continue
for j in range(1, len(i)):
if i[j] in i[j - 1].next_nodes:
# 前项弧
tag_path.append(True)
elif i[j] in i[j - 1].prev_nodes:
tag_path.append(False)
# 后向弧
else:
break
else:
yield gen_full_chain(i, tag_path)
def find_expanded_chain(self):
"""
查找一条增广链
:param self: 图
:return:
"""
chains = self.find_chain() # 返回迭代器
for chain, chain_direction in chains:
for j in range(len(chain_direction)):
k = (chain[j].name, chain[j + 1].name)
if chain_direction[j]:
# 前项弧，容量小于容量
weight = self.edges[k].weight
if not weight[0] > weight[1]:
break
else:
# 后项弧，流量大于0
k = tuple(reversed(k))
weight = self.edges[k].weight
if not weight[1] > 0:
break
else:
return chain, chain_direction
else:
return False, False
def max_flow_by_tag(self, show_detail=False):
"""
标号法寻找最大流
:param show_detail:
:param self:
:return: 无返回值，引用传递g
"""
while True:
# 寻找增广链
chain, chain_direction = self.find_expanded_chain()
if chain:
# 对增广链进行标号
chain[0].update_tag(tag=("0", inf, True))
min_theta = inf
for j in range(len(chain_direction)):
k = (chain[j].name, chain[j + 1].name)
if chain_direction[j]:
# 前项弧标号 v_prev,容量-流量,true
weight = self.edges[k].weight
dig = weight[0] - weight[1]
else:
# 后项弧标号 v_prev,流量,False
k = tuple(reversed(k))
weight = self.edges[k].weight
dig = weight[1]
min_theta = min(dig, min_theta)
tag = (chain[j].name, dig, False)
chain[j + 1].update_tag(tag)
# 调整流量
for j in range(len(chain_direction)):
k = (chain[j].name, chain[j + 1].name)
if chain_direction[j]:
# 前项弧增大流量，加上 Θ
weight = self.edges[k].weight
new_weight = (weight[0], weight[1] + min_theta, weight[2])
else:
# 后项弧减小流量，减去 Θ
k = tuple(reversed(k))
weight = self.edges[k].weight
new_weight = (weight[0], weight[1] - min_theta, weight[2])
self.edges[k].update_weight(new_weight)
self.clean_node_tag()
if show_detail:
print("调整流量后的图：")
print(self)
else:
break
def augment_net(self, by):
"""
构建增流网络
:return:
"""
nodes = self.get_node_names()
# 先把点复制出来
edges = []
# 检查边是否是零流弧、饱和弧、非饱和弧
if by == "by_flow":
for i in self.get_edge_names():
weight = self.edges[i].weight
if weight[1] == 0:
# 零流弧，构建同向弧
new_weight = (weight[0], weight[2])
edges.append((i[0], i[1], new_weight))
elif weight[0] == weight[1]:
# 饱和弧,构建反向弧
new_weight = (weight[1], -weight[2])
edges.append((i[1], i[0], new_weight))
else:
# 不饱和弧，同时构建同向弧和反向弧
# 同向弧
new_weight1 = (weight[0] - weight[1], weight[2])
edges.append((i[0], i[1], new_weight1))
# 反向弧
new_weight2 = (weight[1], -weight[2])
edges.append((i[1], i[0], new_weight2))
if by == 'by_cost':
for i in self.get_edge_names():
weight = self.edges[i].weight
if weight[1] == 0:
# 零流弧，构建同向弧
new_weight = (weight[2],)
edges.append((i[0], i[1], new_weight))
elif weight[0] == weight[1]:
# 饱和弧,构建反向弧
new_weight = (-weight[2],)
edges.append((i[1], i[0], new_weight))
else:
# 不饱和弧，同时构建同向弧和反向弧
# 同向弧
new_weight1 = (weight[2],)
edges.append((i[0], i[1], new_weight1))
# 反向弧
new_weight2 = (-weight[2],)
edges.append((i[1], i[0], new_weight2))
return Graph(nodes=nodes, edges=edges)
def get_theta(self, path):
# 先获取调整量
theta = inf
for i in range(1, len(path)):
key = (path[i - 1].name, path[i].name)
if key in self.edges:
# 同向弧
weight = self.edges[key].weight
vals = weight[0] - weight[1]
else:
key = tuple(reversed(key))
weight = self.edges[key].weight
vals = weight[1]
theta = min(theta, vals)
return theta
def find_all_path(self):
chains = self.find_chain()
for i, _ in chains:
if is_path(i):
yield i
def find_min_cost_path(self):
"""
返回最小费用路径和最小费用
:return:
"""
all_paths = self.find_all_path()
min_path = None
costs = set()
all_paths = [i for i in all_paths]
if len(all_paths) == 0:
return False
else:
for path in all_paths:
now_cost = 0
now_path = path
for j in range(1, len(now_path)):
edge_cost = self.edges[(now_path[j - 1].name, now_path[j].name)].weight[0]
now_cost += edge_cost
if len(costs) > 0:
if now_cost < min(costs):
# 初始状态 最小值为inf ，则第一个路径初始化为最小花费路径
min_path = path
else:
min_path = path
costs.add(now_cost)
return min_path
inf = 999999
class Edge:
def __init__(self, start, end, weight):
"""
:param start: 起始点
:param end: 终点
:param weight: 权重
"""
self.start = start
self.end = end
self.weight = weight
def update_weight(self, weight):
"""
更新权重
"""
self.weight = weight
def __str__(self):
return str(self.start) + " -" + str(list(self.weight)) + "-> " + str(self.end)
def is_path(lis, isloop=False):
if isloop:
if lis[0] not in lis[-1].next_nodes:
return False
for i in range(1, len(lis)):
if lis[i] not in lis[i - 1].next_nodes:
return False
else:
return True
def graph_to_max(g, by):
k = 0
if by == 'by_flow':
# 调整到最大流
g.max_flow_by_tag()
print(f"最大流网络\n{g}")
while True:
k += 1
print(f"第{k}轮调整")
# 构建增流网络
df = g.augment_net(by=by)
print(f"增流网络{df}")
if by == 'by_flow':
neg_loops = [(neg_loop, theta) for neg_loop, theta in df.find_neg_loop()]
if len(neg_loops) > 0:
neg_loop, theta = neg_loops[0]
if g.is_add_loop(neg_loop):
# 是增流圈
g.update_flow(path=neg_loop, theta=theta, by=by)
else:
break
if by == 'by_cost':
ch_path = df.find_min_cost_path()
if ch_path:
theta = g.get_theta(ch_path)
g.update_flow(path=ch_path, theta=theta, by=by)
else:
break
print('调整后的g\n', g)
return g, g.get_costs()
from p62.graph import Graph, graph_to_max
g2 = Graph(nodes=['vs', 'v1', 'v2', 'v3', 'vt'],
edges=[('vs', 'v1', (10, 0, 4)),
('vs', 'v2', (8, 0, 1)),
('v2', 'v1', (5, 0, 2)),
('v1', 'vt', (7, 0, 1)),
('v2', 'v3', (10, 0, 3)),
('v1', 'v3', (2, 0, 6)),
('v3', 'vt', (4, 0, 2))])
g2, g2_cost = graph_to_max(g2,by='by_cost')
print(f"调整到最后的网络：\n{g2}", f"\n最小花费:{g2_cost}")
g1 = Graph(nodes=['vs', 'v1', 'v2', 'v3', 'vt'],
edges=[('vs', 'v1', (10, 0, 4)),
('vs', 'v2', (8, 0, 1)),
('v2', 'v1', (5, 0, 2)),
('v1', 'vt', (7, 0, 1)),
('v2', 'v3', (10, 0, 3)),
('v1', 'v3', (2, 0, 6)),
('v3', 'vt', (4, 0, 2))])
g1, g1_cost = graph_to_max(g1,by='by_flow')
print(f"调整到最后的网络：\n{g1}", f"\n最小花费:{g1_cost}")
输出
第1轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[4]-> v1
vs -[1]-> v2
v2 -[2]-> v1
v1 -[1]-> vt
v2 -[3]-> v3
v1 -[6]-> v3
v3 -[2]-> vt
调整后的g
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 0, 4]-> v1
vs -[8, 5, 1]-> v2
v2 -[5, 5, 2]-> v1
v1 -[7, 5, 1]-> vt
v2 -[10, 0, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 0, 2]-> vt
第2轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[4]-> v1
vs -[1]-> v2
v2 -[-1]-> vs
v1 -[-2]-> v2
v1 -[1]-> vt
vt -[-1]-> v1
v2 -[3]-> v3
v1 -[6]-> v3
v3 -[2]-> vt
调整后的g
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 2, 4]-> v1
vs -[8, 5, 1]-> v2
v2 -[5, 5, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 0, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 0, 2]-> vt
第3轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[4]-> v1
v1 -[-4]-> vs
vs -[1]-> v2
v2 -[-1]-> vs
v1 -[-2]-> v2
vt -[-1]-> v1
v2 -[3]-> v3
v1 -[6]-> v3
v3 -[2]-> vt
调整后的g
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 2, 4]-> v1
vs -[8, 8, 1]-> v2
v2 -[5, 5, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 3, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 3, 2]-> vt
第4轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[4]-> v1
v1 -[-4]-> vs
v2 -[-1]-> vs
v1 -[-2]-> v2
vt -[-1]-> v1
v2 -[3]-> v3
v3 -[-3]-> v2
v1 -[6]-> v3
v3 -[2]-> vt
vt -[-2]-> v3
调整后的g
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 3, 4]-> v1
vs -[8, 8, 1]-> v2
v2 -[5, 4, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 4, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 4, 2]-> vt
第5轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[4]-> v1
v1 -[-4]-> vs
v2 -[-1]-> vs
v2 -[2]-> v1
v1 -[-2]-> v2
vt -[-1]-> v1
v2 -[3]-> v3
v3 -[-3]-> v2
v1 -[6]-> v3
vt -[-2]-> v3
调整到最后的网络：
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 3, 4]-> v1
vs -[8, 8, 1]-> v2
v2 -[5, 4, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 4, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 4, 2]-> vt
最小花费:55
最大流网络
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 9, 4]-> v1
vs -[8, 2, 1]-> v2
v2 -[5, 0, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 2, 3]-> v3
v1 -[2, 2, 6]-> v3
v3 -[4, 4, 2]-> vt
第1轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[1, 4]-> v1
v1 -[9, -4]-> vs
vs -[6, 1]-> v2
v2 -[2, -1]-> vs
v2 -[5, 2]-> v1
vt -[7, -1]-> v1
v2 -[8, 3]-> v3
v3 -[2, -3]-> v2
v3 -[2, -6]-> v1
vt -[4, -2]-> v3
调整后的g
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 4, 4]-> v1
vs -[8, 7, 1]-> v2
v2 -[5, 5, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 2, 3]-> v3
v1 -[2, 2, 6]-> v3
v3 -[4, 4, 2]-> vt
第2轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[6, 4]-> v1
v1 -[4, -4]-> vs
vs -[1, 1]-> v2
v2 -[7, -1]-> vs
v1 -[5, -2]-> v2
vt -[7, -1]-> v1
v2 -[8, 3]-> v3
v3 -[2, -3]-> v2
v3 -[2, -6]-> v1
vt -[4, -2]-> v3
调整后的g
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 4, 4]-> v1
vs -[8, 7, 1]-> v2
v2 -[5, 3, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 4, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 4, 2]-> vt
第3轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[6, 4]-> v1
v1 -[4, -4]-> vs
vs -[1, 1]-> v2
v2 -[7, -1]-> vs
v2 -[2, 2]-> v1
v1 -[3, -2]-> v2
vt -[7, -1]-> v1
v2 -[6, 3]-> v3
v3 -[4, -3]-> v2
v1 -[2, 6]-> v3
vt -[4, -2]-> v3
调整后的g
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 3, 4]-> v1
vs -[8, 8, 1]-> v2
v2 -[5, 4, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 4, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 4, 2]-> vt
第4轮调整
增流网络Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[7, 4]-> v1
v1 -[3, -4]-> vs
v2 -[8, -1]-> vs
v2 -[1, 2]-> v1
v1 -[4, -2]-> v2
vt -[7, -1]-> v1
v2 -[6, 3]-> v3
v3 -[4, -3]-> v2
v1 -[2, 6]-> v3
vt -[4, -2]-> v3
调整到最后的网络：
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 3, 4]-> v1
vs -[8, 8, 1]-> v2
v2 -[5, 4, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 4, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 4, 2]-> vt
最小花费:55