Home > track > greedySearch.m

greedySearch

PURPOSE ^

SYNOPSIS ^

function matching = greedySearch(H,idTable,M,N)

DESCRIPTION ^

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function matching = greedySearch(H,idTable,M,N)
0002 [R,C] = size(H);
0003 tVal = Inf;
0004 matching = ones(R,C)*tVal;
0005 [val r c] = findMin(H);
0006 
0007 while val<tVal   
0008 
0009     ind = idTable{r,c};
0010 
0011     switch length(ind)                
0012         case 2 % 1:1 Normal
0013             matching(r,c) = val;
0014 %             H(r,:) = Inf;
0015 %             H(:,c) = Inf;
0016             H(searchRow(idTable,ind,1,M,N),:) = Inf;
0017             H(:,searchCol(idTable,ind,2,M,N)) = Inf;
0018 
0019         case 3 % 2:1 Merge
0020             if (findMinByRowId(H,idTable,ind(1),M,N) + ...
0021                     findMinByRowId(H,idTable,ind(2),M,N) < 2)
0022                 H(r,:) = Inf;
0023             else
0024                 matching(r,c) = val;
0025                 %             H(r,:) = Inf;
0026                 H(searchRow(idTable, ind,1,M,N),:) = Inf;
0027                 H(searchRow(idTable, ind,2,M,N),:) = Inf;
0028                 H(:, searchCol(idTable, ind,3,M,N)) = Inf;
0029             end
0030         case 4 % 1:2 Split
0031             matching(r,c) = val;
0032 %             H(r,:) = Inf;
0033             H(searchRow(idTable,ind,1,M,N),:) = Inf;
0034             H(searchRow(idTable,ind,2,M,N),:) = Inf;
0035             H(:,searchCol(idTable,ind,3,M,N)) = Inf;
0036             H(:,searchCol(idTable,ind,4,M,N)) = Inf;
0037             
0038         otherwise
0039             disp('Invalid match');
0040     end
0041     [val r c] = findMin(H);      
0042 end
0043 
0044 %%-------------------------------------------------------------------------
0045 
0046     function pos = searchRow(idTable, ind,x,M,N)
0047         pos = [];
0048         [R C] = size(idTable);
0049         switch length(ind)
0050             case 2
0051                 for rr = 1: R
0052                     if (length(idTable{rr,1})==2) && (idTable{rr,1}(1) == ind(x))
0053                         pos = [pos rr];
0054                     elseif (length(idTable{rr,1})==3) && ...
0055                             ((idTable{rr,1}(1) == ind(x))||(idTable{rr,1}(2) == ind(x)))
0056                         pos = [pos rr];
0057                     elseif (N<C) && (length(idTable{rr,N+1})==4) && ...
0058                             ((idTable{rr,N+1}(1) == ind(x))||(idTable{rr,N+1}(2) == ind(x)))
0059                         pos = [pos rr];
0060                     end
0061                 end
0062             case 3
0063                 for rr =  1:R
0064                    if (length(idTable{rr,1})==2) && (idTable{rr,1}(1) == ind(x))
0065                        pos = [pos rr];
0066                    
0067                    elseif (length(idTable{rr,1})==3) && ...
0068                            ((idTable{rr,1}(1) == ind(x)) || (idTable{rr,1}(2) == ind(x)))
0069                        pos = [pos rr];
0070                    elseif (N<C) && (length(idTable{rr,N+1})==4) && ...
0071                                 ((idTable{rr,N+1}(1) == ind(x)) || (idTable{rr,N+1}(2) == ind(x)))
0072                             pos = [pos rr];
0073                    end
0074                 end  
0075             case 4
0076                 for rr =  1:R
0077 
0078                     if ((length(idTable{rr,1})==2) && (idTable{rr,1}(1) == ind(x)))
0079                         pos = [pos rr];
0080                     elseif (length(idTable{rr,1})==3) && ...
0081                             ((idTable{rr,1}(1) == ind(x)) || (idTable{rr,1}(2) == ind(x)))
0082                         pos = [pos rr];
0083                     elseif (N<C) && (length(idTable{rr,N+1})==4) && ...
0084                             ((idTable{rr,N+1}(1) == ind(x)) || (idTable{rr,N+1}(2) == ind(x)))
0085                         pos = [pos rr];
0086                     end
0087 
0088                 end
0089         end
0090     end
0091 
0092     function pos = searchCol(idTable, ind, x,M,N)
0093         pos= [];
0094         [R C] = size(idTable);
0095         switch length(ind)
0096             case 2
0097                 for cc = 1: C
0098                     if (length(idTable{1,cc})==2) && (idTable{1,cc}(2) == ind(x))
0099                         pos = [pos cc];
0100                     
0101                     elseif (length(idTable{1,cc})==3) && (idTable{1,cc}(3) == ind(x))
0102                         pos = [pos cc];
0103                     elseif (M<R) && ((length(idTable{M+1,cc})==4) &&...
0104                             ((idTable{M+1,cc}(3) == ind(x))||idTable{M+1,cc}(4) == ind(x)))
0105                         pos = [pos cc];
0106                     end
0107                 end
0108             case 3
0109                 for cc = 1: C
0110                     if (length(idTable{1,cc})==2) && (idTable{1,cc}(2) == ind(x))
0111                         pos = [pos cc];
0112                     end
0113                     if (length(idTable{1,cc})==3) && (idTable{1,cc}(3) == ind(x))
0114                         pos = [pos cc];
0115                     elseif (M<R)&& ((length(idTable{M+1,cc})==4) &&...
0116                             ((idTable{M+1,cc}(3) == ind(x))||idTable{M+1,cc}(4) == ind(x)))
0117                         pos = [pos cc];
0118                     end
0119                 end
0120             case 4
0121                 for cc = 1:C
0122 
0123                     if ((length(idTable{1,cc})==2) && (idTable{1,cc}(2) == ind(x)))
0124                         pos = [pos cc];
0125                     elseif ((length(idTable{1,cc})==3) && (idTable{1,cc}(3) == ind(x)))
0126                         pos = [pos cc];
0127                     elseif (M<R) && ((length(idTable{M+1,cc})==4) && ...
0128                             ((idTable{M+1,cc}(3) == ind(x)) ||idTable{M+1,cc}(4) == ind(x)))
0129                         pos= [pos cc];
0130                     end
0131 
0132                 end
0133         end
0134     end
0135 
0136     function minVal = findMinByRowId(H,idTable,r,M,N)
0137         rr =1; 
0138         minVal = [];
0139         while (rr <=M) && isempty(minVal)
0140             if (idTable{rr,1}(1)==r)
0141                 minVal = min(H(rr,:));                
0142             end
0143             rr = rr +1;
0144         end
0145     end
0146 
0147 end

Generated on Thu 17-Mar-2011 14:45:51 by m2html © 2005