% author: Ahmad Humayun
% date: March 2008
% version: 0.01
function [ k r_cutoff c_cutoff r_remaining c_remaining ] = minLineCover( X, r_removed, c_removed )
%Returns the minumun number of lines required to cover all zeros
% it returns 1 value, stating the no. of row of cut-off lines made
% and four vectors: two vectors telling the lines of rows and
% columns that got cut-off, the two other vectors show the rows and
% columns remaining. The X argument gives the matrix on which the
% computation needs to be done, and the other two arguments can be
% passed a vector of rows and cols which need to be ignored for the
% computation
X_temp = X;
[m n] = size(X_temp);
X_temp(r_removed,:) = 1; %mark the said rows with non-zero value
X_temp(:,c_removed) = 1; %mark the said cols with non-zero value
k = 0; %no. of lines cutting through zeros
r_cutoff = []; %we start off with no cut-off lines
c_cutoff = [];
r_remaining = 1:m; %we start off with a whole list of lines
c_remaining = 1:n;
while nnz(X_temp) < m*n %keep running till no zeros present
[R C] = find(X_temp == 0); %find all non-zero values
[zeros_row_span temp] = size(unique(R)); %number of rows over which the zeros come
[zeros_col_span temp] = size(unique(C)); %number of cols over which the zeros come
if zeros_row_span == zeros_col_span
%only mark off the row lines or col lines which have the lowest
%chance as returned by lineCrossChance()
row_min_chance = 1; %set chance for rows to max value
min_chance_rows = []; %array which houses rows having the min chance
col_min_chance = 1; %set chance for cols to max value
min_chance_cols = []; %array which houses cols having the min chance
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
row_zeros = sum((X_temp == 0)'); %number of zeros in all rows
max_row_zeros = max(row_zeros); %max number of zeros in a row
[temp row_mz] = find(row_zeros == max_row_zeros); %choose all rows having the max no. of zeros
%add all chance values for all rows having the max no. of zeros
for r = row_mz
temp = lineCrossChance(X_temp, r, 0); %calculate the chance for each row
min_chance_rows = [ min_chance_rows temp ]; %add chance value to the array
end
row_min_chance = min(min_chance_rows); %find the min chance in all rows
row_mz( min_chance_rows ~= row_min_chance ) = []; %discard rows which are not min chance
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
col_zeros = sum((X_temp == 0)); %number of zeros in all cols
max_col_zeros = max(col_zeros); %max number of zeros in a col
[temp col_mz] = find(col_zeros == max_col_zeros); %choose all cols having the max no. of zeros
%add all chance values for all cols having the max no. of zeros
for c = col_mz
temp = lineCrossChance(X_temp, c, 1); %calculate the chance for each col
min_chance_cols = [ min_chance_cols temp ]; %add chance value to the array
end
col_min_chance = min(min_chance_cols); %find the min chance in all cols
col_mz( min_chance_cols ~= col_min_chance ) = []; %discard cols which are not min chance
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%mark of only rows and cols which have the minimum chance that
%there would be normals crossing over their zeros
if row_min_chance <= col_min_chance
X_temp(row_mz,:) = 1; %mark the whole row(s) with a non-zero no.
r_cutoff = [ r_cutoff row_mz ]; %add row(s) to cut off rows
r_remaining(row_mz) = m+1; %mark row(s) for cut off
%adjust value of the no. of lines cutoff
[temp row_mz] = size(row_mz);
k = k + row_mz;
else
X_temp(:,col_mz) = 1; %mark the whole col(s) with a non-zero no.
c_cutoff = [ c_cutoff col_mz ]; %add col(s) to cut off cols
c_remaining(col_mz) = n+1; %mark col(s) for cut off
%adjust value of the no. of lines cutoff
[temp col_mz] = size(col_mz);
k = k + col_mz;
end
else
if zeros_row_span < zeros_col_span
%mark all row lines which have the highest no. of zeros
row_zeros = sum((X_temp == 0)'); %number of zeros in all rows
max_row_zeros = max(row_zeros); %max number of zeros in a row
[temp row_mz] = find(row_zeros == max_row_zeros); %choose all rows having the max no. of zeros
X_temp(row_mz,:) = 1; %mark the whole row(s) with a non-zero no.
r_cutoff = [ r_cutoff row_mz ]; %add row(s) to cut off rows
r_remaining(row_mz) = m+1; %mark row(s) for cut off
%adjust value of the no. of lines cutoff
[temp row_mz] = size(row_mz);
k = k + row_mz;
else
%mark all col lines which have the highest no. of zeros
col_zeros = sum((X_temp == 0)); %number of zeros in all cols
max_col_zeros = max(col_zeros); %max number of zeros in a col
[temp col_mz] = find(col_zeros == max_col_zeros); %choose all cols having the max no. of zeros
X_temp(:,col_mz) = 1; %mark the whole col(s) with a non-zero no.
c_cutoff = [ c_cutoff col_mz ]; %add col(s) to cut off cols
c_remaining(col_mz) = n+1; %mark col(s) for cut off
%adjust value of the no. of lines cutoff
[temp col_mz] = size(col_mz);
k = k + col_mz;
end
end
end
r_remaining(r_remaining == m+1) = []; %remove cut off rows
c_remaining(c_remaining == n+1) = []; %remove cut off cols
end
function chance = lineCrossChance( X, r_c_no, line_considered )
%The chance that it would be a bad idea to mark the line being
%considered
% This function just gives an approximate (not a perfectly reliable
% measure) measue of probability of lines crossing normal to the
% line given. In other words if the line wasn't drawn what is the
% probability that a line would have still crossed its zero points.
% From this line's perspective marking off this line given a high
% chance (return value) would be a bad idea. line_considered 0 is a
% row line, and 1 is a column line.
X_zeros = X == 0; %get matrix where 0s are 1s and every other thing is 0
[m n] = size(X); %get the size of the matix
col_zeros = sum(X_zeros); %get the number of zeros in all cols
row_zeros = sum(X_zeros')'; %get the number of zeros in all rows
if line_considered == 0 %if a row line
no_zeros = sum( X_zeros(r_c_no,:) ); %no. of zeros in the row line being considered
row_zeros_m = row_zeros * ones(1,n); %get the matrix where elem depicts zeros in that row
col_zeros = X_zeros(r_c_no,:) .* col_zeros; %ignore cols which dont have 0s on the line being considered
row_zeros_m = X_zeros .* row_zeros_m; %ignore all row zero values where there is no zero
col_zeros_m = ones(m,1) * col_zeros; %expand col_zeros to a matrix
%delete the row on which the considered line from both matrices
X_zeros(r_c_no,:) = [];
row_zeros_m(r_c_no,:) = [];
col_zeros_m(r_c_no,:) = [];
row_zeros_m = row_zeros_m + col_zeros_m; %add both matrices to finally calculate the denominator
row_zeros_m = col_zeros_m ./ row_zeros_m; %get the probabilities for all zero values over each col
%ignore irrelevant values of NaN and 1. 1 because it means that at
%the same element there was a zero before
row_zeros_m( (row_zeros_m == 1) | isnan(row_zeros_m) ) = 0;
row_zeros_sum = sum(row_zeros_m); %add the chances for each point
row_zeros_sum = row_zeros_sum(row_zeros_sum ~= 0) ./ (col_zeros(row_zeros_sum ~= 0) - 1); %take out avg chance
chance = sum(row_zeros_sum) / no_zeros; %finally calculate the chance value for the given row line
else %if a col line
no_zeros = sum( X_zeros(:,r_c_no) ); %no. of zeros in the col line being considered
col_zeros_m = ones(m,1) * col_zeros; %get the matrix where elem depicts zeros in that col
row_zeros = X_zeros(:,r_c_no) .* row_zeros; %ignore rows which dont have 0s on the line being considered
col_zeros_m = X_zeros .* col_zeros_m; %ignore all row zero values where there is no zero
row_zeros_m = row_zeros * ones(1,n); %expand row_zeros to a matrix
%delete the row on which the considered line from both matrices
X_zeros(:,r_c_no) = [];
col_zeros_m(:,r_c_no) = [];
row_zeros_m(:,r_c_no) = [];
col_zeros_m = col_zeros_m + row_zeros_m; %add both matrices to finally calculate the denominator
col_zeros_m = row_zeros_m ./ col_zeros_m; %get the probabilities for all zero values over each row
%ignore irrelevant values of NaN and 1. 1 because it means that at
%the same element there was a zero before
col_zeros_m( (col_zeros_m == 1) | isnan(col_zeros_m) ) = 0;
col_zeros_sum = sum(col_zeros_m')'; %add the chances for each point
col_zeros_sum = col_zeros_sum(col_zeros_sum ~= 0) ./ (row_zeros(col_zeros_sum ~= 0) - 1); %take out avg chance
chance = sum(col_zeros_sum) / no_zeros; %finally calculate the chance value for the given col line
end
end