wmatch.m

清华大学运筹学课件

%wmatch.m
%This program solves the maximum-weight matching problem.

n=input('Enter the number of the verties of |T|=|S|=n=')
W=input('Enter the matrix of the graph:[W(1,1),..,W(1,n);..;W(n,1),..,W(n,n)]= ') 
%W(i,j)=0 if (i,j) isn't in graph
L=zeros(1,(2*n)); %L is a feasible vertix labelling
   d=max(max(W,[],2));
   for i=1:n   L(1,i)=d;  end  
M=zeros(n); %M is the maximun-edges matching in W
S=zeros(1,n);  T=zeros(1,n);  r=1;  q=1;

%main steps

while nnz(M)<n %M isn't a perfect matching
   
%step0 and step1
   
   if q==1 
      
%step0
      G=zeros(n); %G is the equality subgraph
      if r==1 
         %search equality subgraph G(L)
         for i=1:n 
            for j=1:n
               if L(i)+L(n+j)==W(i,j)  G(i,j)=1;   end
            end
         end %search end
      end 
%step0 end
   
%step1
      for i=1:n %search a M-unsaturated vertix 
         if all(M(i,:)==0)==1    S(i)=1;  
            break
         end
      end %search end
%step1 end
   
   end 
%step0 and step1 end
   
%step2
   %test if N(S)=T
   a=0;
   for i=1:n
      if (S(i)==1)&(all(G(i,:)==0))  a=0; %i is a isolated vertix
      else
         for j=1:n
            if (S(i)==1)&(G(i,j)==1)&(T(j)==0)  a=1; y=j; u=i; %N(S)>T
               break
            end
         end
      end
   end %test end
   
   if a==0 %N(S)=T
      r=1; q=1; %goto step0
      %change vertix labelling
      for v=1:n 
         if S(v)==1   L(v)=L(v)-1;
         elseif T(v)==1   L(v)=L(v)+1;
         end
      end%change end
      
%step3   
   elseif a==1 %N(S)>T
      r=0;
      if all(M(:,y)==0)==0 %y is M-saturated
         q=0; %goto step2
         %change S and T
         for z=1:n
            if M(z,y)~=0   S(z)=1;  T(y)=1;    end
         end %change end
      else   
         %M=M^P
         M(u,y)=W(u,y);  
         %clear S and T
         S=zeros(1,n);  T=zeros(1,n);
      end
   end 
%step2 and step3 end
   
end

input('the maximun-weight matching is:')
M