bipmatch --- maximum matching in a bipartite graph This may be called either as bipmatch(g,X,Y) or bipmatch(g,p). In either case, g is any graph. X,Y are disjoint sets of vertices of g or p is a partition of a subset of V(g) into two parts. In either case, this returns a maximum matching on the bipartite (sub)graph of G with bipartition (X,Y).
0001 function elist = bipmatch(g,X,Y) 0002 % bipmatch --- maximum matching in a bipartite graph 0003 % This may be called either as bipmatch(g,X,Y) or bipmatch(g,p). 0004 % In either case, g is any graph. 0005 % X,Y are disjoint sets of vertices of g or p is a partition of a subset of 0006 % V(g) into two parts. 0007 % In either case, this returns a maximum matching on the bipartite 0008 % (sub)graph of G with bipartition (X,Y). 0009 0010 0011 if nargin==2 0012 c = parts(X); 0013 if length(c) ~= 2 0014 error('partition must have two parts'); 0015 end 0016 X = c{1}; 0017 Y = c{2}; 0018 else 0019 X = unique(X); 0020 Y = unique(Y); 0021 end 0022 0023 if length(intersect(X,Y)) > 0 0024 error('The sets X and Y must be disjoint') 0025 end 0026 0027 n = nv(g); 0028 0029 Z = union(X,Y); 0030 0031 if any(Z<1) | any(Z>n) 0032 error('Some vertices out of range') 0033 end 0034 0035 A = matrix(g); 0036 A = A(X,Y); 0037 0038 p = dmperm(A); % one of Matlab's best kept secrets :-) 0039 0040 yidx = find(p); 0041 xidx = p(p>0); 0042 0043 x = X(xidx); 0044 y = Y(yidx); 0045 0046 elist = [ x(:), y(:)]; 0047 elist = sortrows(elist);