跳转至

Ford-Fulkerson算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# -*- coding: utf-8 -*-
class Edge(object):
    """
        定义有向边Edge类

        source:     源结点
        target:     目标结点
        capacity:   边的容量
        返回值格式: source->target:capacity
    """
    def __init__(self, u, v, w):
        self.source = u   #源结点
        self.target = v   #目标结点
        self.capacity = w #容量
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.target, self.capacity)

class FlowNetwork(object):
    """
        定义流网络图FlowNetwork类

        adj[vertex]: 以vertex为源结点的所有边的集合
        flow[edge]:  有向边edge的流量   
    """
    def __init__(self):
        self.adj = {}
        self.flow = {}

    def add_vertex(self, vertex):  #向图中加入结点vertex
        self.adj[vertex] = []

    def get_edges(self, v):        #获取以v为源结点的所有边
        return self.adj[v]

    def add_edge(self, u, v, w=0): #向图中加入以u为源结点，以v为目标结点，w为容量的边
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)  #正向边，以u为源结点
        redge = Edge(v,u,0) #反向边，以v为源结点
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0  #初始流量都设置为0
        self.flow[redge] = 0

    def find_path(self, source, target, path):  #寻找增广路径
        if source == target:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and edge not in path:
                result = self.find_path(edge.target, target, path + [edge]) 
                if result != None:
                    return result

    def max_flow(self, source, target):
        path = self.find_path(source, target, []) 
        while path != None:  #当找不到增广路径时，根据最大流最小割定理，此时网络达到最大流
            residuals = [edge.capacity - self.flow[edge] for edge in path] #path的残存流量
            flow = min(residuals)
            for edge in path:
                self.flow[edge] += flow  #为每条边注入残存流量
                self.flow[edge.redge] -= flow  #为反向边注入反向流量
            path = self.find_path(source, target, []) 
        return sum(self.flow[edge] for edge in self.get_edges(source))

if __name__ == '__main__':
    g = FlowNetwork()
    Persons = {'Mike', 'Alice', 'Bob', 'Tom', 'John'}
    Jobs = {'Work1', 'Work2', 'Work3', 'Work4'}

    g.add_vertex('s') #增加虚拟源点's'
    g.add_vertex('t') #增加虚拟汇点't'
    for person in Persons:
        g.add_vertex(person)
        g.add_edge('s', person, 1)
    for job in Jobs:
        g.add_vertex(job)
        g.add_edge(job, 't', 1)

    g.add_edge('Mike', 'Work1', 2**32-1)
    g.add_edge('Alice', 'Work1', 2**32-1)
    g.add_edge('Alice', 'Work2', 2**32-1)
    g.add_edge('Bob', 'Work3', 2**32-1)
    g.add_edge('Tom', 'Work1', 2**32-1)
    g.add_edge('Tom', 'Work3', 2**32-1)
    g.add_edge('Tom', 'Work4', 2**32-1)
    g.add_edge('John', 'Work3', 2**32-1)
    g.add_edge('John', 'Work4', 2**32-1)

    print ('最大匹配数如下:')
    print (g.max_flow('s','t'))
    print ('流网络如下:')
    print (g.flow)