bimatichhungary.m

偶图最大匹配完全照算法说明利用集合运算实现的matlab代码。这里需要大家讨论的是增广路的选取的算法

function biMatichHungary(X,Y,E,M)
    if nargin<1
        X=1:5;
        Y=6:10;
        E=[1 0 0 1 0;
            0 1 1 0 1;
            0 1 0 0 0;
            0 0 1 1 0
            0 0 0 0 1];
        %M=[1,2,3,4,5;6,7,8,9,10];
        M=[1 3 4 5;9 7 8 10];
    end
    plotmatch(X,Y,E,M)
    flag=0;
    if isempty(M)
        Y1=find(E(1,:)>0);
        if isempty(Y1)
            disp('No perfect match')
            return
        end
        M=[X(1);Y(Y1(1))];
    end
    if ~isempty(setdiff(X,M(1,:)))
        XM=setdiff(X,M(1,:));
        u=XM(1);
        flag=1;
    end
    while flag
        S=[u];
        R=[u];
        T=[];
        while flag
            % P(S)
            PS=[];
            for i=1:length(S)
                j=find(S(i)==X);
                yset=find(E(j,:)>0);
                PS=union(PS,Y(yset));
            end
            % PsT=P(S)-T
            PsT=setdiff(PS,T);
            if isempty(PsT)
                disp('No perfect match')
                flag=0;
                break;
            else
                PsTM=setdiff(PsT,M(2,:));
                if isempty(PsTM)
                    y=PsT(1);
                    z=M(1,find(y==M(2,:)));
                    %find(yz in M)
                    S=union(S,[z]);
                    T=union(T,[y]);
                    R=[R,y,z];
                else
                    y=PsTM(1);
                    %find R(u,y)
                    R=[R,y];
                    Rflag=1;
                    while Rflag
                        if length(R)<3
                            Rflag=0;
                            break;
                        end                        
                        Rflag=0;
                        i=length(R);
                        while i>=3
                            iY=find(R(i)==Y);
                            iX=find(R(i-1)==X);
                            if E(iX,iY)==0
                                %R=setdiff(R,[R(i-1),R(i-2)])
                                R=[R(1:i-3),R(i:end)];
                                Rflag=1;
                            end
                            i=i-2;
                        end
                    end
                    
                    ER=[]
                    for i=1:length(R)-1
                        if mod(i,2)
                            ER=[ER,[R(i);R(i+1)]];
                        else
                            ER=[ER,[R(i+1);R(i)]];
                        end
                    end
                    %M=(M-E(R))+(E(R)-M)
                    M=MaddER(M,ER);
                    
                    flag=0;
                    if ~isempty(setdiff(X,M(1,:)))
                        XM=setdiff(X,M(1,:));
                        u=XM(1);
                        flag=1;
                        break
                    end
                end
            end
        end
    end
    pause(1)
    plotmatch(X,Y,E,M)
function MER=MaddER(M,ER)
    %M=(M-E(R))+(E(R)-M)
    flag=0;
    if size(M,1)==2
        flag=1;
        M=M';
        ER=ER';
    end
    c=setdiff(M,ER,'rows');
    d=setdiff(ER,M,'rows');
    MER=union(c,d,'rows');
    if flag
        MER=MER';
    end
    return