bipartite_graph.py

#!/usr/bin/python
# coding: utf-8
from collections import deque
#==============================================================================
# Hungarian Algorithm, find maximum matching
#==============================================================================
class HungarianAlgorithm(object):
    def __init__(self,graph):
        """
        @graph:图的矩阵表示
        """
        self.graph=graph
        self.n=len(graph)       

    def find(self,x):
        for i in range(self.n):
            if self.graph[x][i]==1 and not self.used[i]:
                self.used[i]=1#放入交替路
                if self.match[i]==-1 or self.find(self.match[i])==1:
                    self.match[i]=x
                    self.match[x]=i
                    print(x+1,'->',i+1)
                    return 1
        return 0
        
    def hungarian_dfs(self):
        """递归形式, Depth First Search 
        """
        self.match = [-1] * self.n # 记录匹配情况 (current matching records)
        self.used = [False] * self.n # 记录是否访问过 (visited)
        m = 0
        for i in range(self.n):
            if self.match[i] == -1:
                self.used = [False] * self.n
                # print('Matching:', i)
                m += self.find(i)
        return m
    
    def hungarian2(self):
        """循环形式, Breadth First Search
        """
        match = [-1] * self.n#记录匹配情况
        used = [-1] * self.n#记录是否访问过
        Q = deque()  #设置队列
        ans = 0
        prev = [0] * self.n  #代表上一节点
        for i in range(self.n): 
            if match[i]==-1:
                Q.clear()
                Q.append(i)
                prev[i] = -1 #设i为出发点
                flag = False #未找到增广路
                while len(Q) > 0 and not flag:
                    u = Q.popleft()
                    for j in range(self.n):
                        if not flag and self.graph[u][j]==1 and  used[j]!=i:
                            used[j]=i        
                            if match[j]!=-1:
                                Q.append(match[j])
                                prev[match[j]]=u#记录点的顺序
                            else:
                                flag=True
                                d=u
                                e=j
                                while(d!=-1):#将原匹配的边去掉加入原来不在匹配中的边
                                    t=match[d]
                                    match[d]=e
                                    match[e]=d
                                    d=prev[d]
                                    e=t
                                # print('mathch:',match)
                                # print('prev:',prev)
                                # print('deque',Q)
                if  match[i]!=-1:#新增匹配边
                    ans+=1
        return ans
        

if __name__ == '__main__':
    def do1():  
        graph=[(0,0,0,0,1,0,1,0),
           (0,0,0,0,1,0,0,0),
           (0,0,0,0,1,1,0,0),
           (0,0,0,0,0,0,1,1),
           (1,1,1,0,0,0,0,0),
           (0,0,1,0,0,0,0,0),
           (1,0,0,1,0,0,0,0),
           (0,0,0,1,0,0,0,0)]
        h=HungarianAlgorithm(graph)
        print (h.hungarian1())
    
    def do2():  
        graph=[(0,0,0,0,1,0,1,0),
           (0,0,0,0,1,0,0,0),
           (0,0,0,0,1,1,0,0),
           (0,0,0,0,0,0,1,1),
           (1,1,1,0,0,0,0,0),
           (0,0,1,0,0,0,0,0),
           (1,0,0,1,0,0,0,0),
           (0,0,0,1,0,0,0,0)]
        h=HungarianAlgorithm(graph)
        print (h.hungarian2())
    
    do1()
    do2()