match.m

清华大学运筹学课件

%match.m
%This program solves the maximum matching problem.

s=input('Enter the vertices number of S:s= ')
t=input('Enter the vertices number of T:t= ')
W=input('Enter the matrix of the graph:[W(1,1),..,W(1,t);..;W(s,1),..,W(s,t)]=') 
%(0,1)-matrix
st=s;
if t<s  st=t;  end

%step0: preparation

M=zeros(s,t); %M is the maximun-edges matching 
P=zeros(s,t); %P is the M-argument path  
N=zeros(1,s); %N(i)=1----the ith vertix hasn't been chosen 
L=ones(1,(s+t))*inf; % L is the vertix labelling
u=0; 

%main steps

for z=1:st %the times of the circulation
   
   if u==0 % if u==1 then step1.3 goto step 1.2
      x=0; %step1.1
      for i=1:s %number of M-unsaturated vertices
         if all(M(i,:)==0)==1   L(i)=0;
            N(i)=1; x=x+1; 
         end     
      end  
      if x==0 %step1.1
         break
      end
   end
   
%step1.2
   q=0;
   for i=1:s %pick out a vertix x(i)
      if (L(i)~=inf)&(N(i)==1)  q=1;
         break
      end
   end
   
   if q==0 %goto step3 
      break
   end  
   
   for j=1:t %step1.3: change the labelling of vertix y(j) 
      if (W(i,j)==1)&(L(s+j)==inf)  L(s+j)=i;   end
   end  
      
   k=inf; x=0;
   for j=1:t %step1.3
      if (L(s+j)==i)&(all(M(:,j)==0)==1)  k=0; x=s+j;
         break
      elseif (L(s+j)==i)&(all(M(:,j)==0)==0)   k=1;  
      end     
   end
   
%step2
   if k==0  
      while (L(x))~=0 %M-argument path 
         y=L(x); P(y,j)=1; 
         if (L(y))==0
            break
         else   
            x=L(y); P(y,j)=1;
         end
      end   
      for g=1:s %M=M^P
         for h=1:t
            if M(g,h)>=P(g,h)  M(g,h)=M(g,h)-P(g,h);
            else   M(g,h)=P(g,h)-M(g,h);
            end
         end 
      end 
      L=ones(1,(s+t))*inf; % delete the vertices labelling
      P=zeros(s,t); %delete the M-argument path  
   end
   
   if k==1 %step1.3
      N(i)=0; u=1;
      for j=1:t
         for l=1:s
            if (W(i,j)==1)&(M(l,j)==1)  L(l)=j; N(l)=1; end
         end
      end
   end 
      
end

input('the maximun matching is:')
M