最大流，最小费最大流问题 python

徐少华 算法设计与分析 P145

解题思路

解题算法
最小费用最大流: 解法 I
步骤一：利用最大流算法, 将网络的流量调整到最大流
步骤二: 构建伴随网络流f的增流网络 D_f
步骤三: 在增流网络 D_f 中, 查找关于费用的负回路, 令 \(θ=minc_ij^' (c_ij^' 为负回路中各弧的容量)\), 若不存在负回路, 则说明当前网络流已经是最小费用流, 结束算法
步骤四： 针对负回路对应网络D中的圈, 若该圈是增流圈, 则把增流圈方向上与负回路方向一 致的所有弧的流量加上 θ , 把增流圈方向上与负回路方向相反的所有弧的流量减去 θ ; 若该圈不是增流圈, 则转到步骤二

流程图

代码实现

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])

        else:
            # 查找首尾节点
            for i in self.nodes.values():
                if i.prev_nodes == set():
                    self.head_node = i
                if i.next_nodes == set():
                    self.tail_node = i

    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, neg_loop, theta):

        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)
                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_loop(j):
                    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)):
            all_path_u.extend(list(itertools.permutations(nodes_ex, i)))

        all_chain_u = all_path_u

        # real_chain = []
        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:
                # 只有一个中间节点的情况
                # real_chain.append(i)
                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:
                # real_chain.append(i)
                yield gen_full_chain(i, tag_path)
        # return real_chain

    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 flow_augment(self):
        """
        构建增流网络
        :return:
        """
        nodes = self.get_node_names()
        # 先把点复制出来

        edges = []
        # 检查边是否是零流弧、饱和弧、非饱和弧

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

        return Graph(nodes=nodes, edges=edges)


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):
        """
        更新权重
        :param weight:
        :return:
        """
        self.weight = weight

    def __str__(self):
        return str(self.start) + " -" + str(list(self.weight)) + "-> " + str(self.end)

def is_loop(lis):
    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
# 生成图
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.max_flow_by_tag()
while True:
    # 构建增流网络
    df = g1.flow_augment()
    print("增流网络：\n", df)
    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 g1.is_add_loop(neg_loop):
            # 是增流圈
            g1.update_flow(neg_loop=neg_loop, theta=theta)
            print("更新后的图：\n", df)
    else:
        break
print(g1)
print("最小花费", g1.get_costs())

输出

增流网络：
 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
更新后的图：
 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
增流网络：
 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
更新后的图：
 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
增流网络：
 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
更新后的图：
 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
增流网络：
 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