First of all, I'm not 100% sure if Matlab is allowed on stack overflow; if I'm violating the rules tell me and I'll delete the question.
I'm currently studying percolation on a 2D surface (using a matrix for it), and I've written an algorithm that is able to check for percolation and label all cluster in a grid. The algorithm i wrote isn't very efficient and i've been tasked to implement the HK algorithm to do the same, more efficently since the HK doesn't "look behind".
FYI -> reticolo stands for grid, reticle
The "main" part of the program seems to work fine. Whenever i used my own way instead of the Find function i also found that in random grid where there aren't any cells that have BOTH up and left NN, everything works fine and the whole grid gets labelled correctly.
That also means that techincally the Union-Find part of the algorithm isn't really needed if the grid generated has cells that do not have both neighbors to the left and above, but that is clearly irrealistic.
What seems to be giving me problems is implementing correctly the Find function.
If anyone is able to help, I'd appreciate. Thanks
function A = HK(p,L)
if nargin == 0,0;
p = 0.55;
L = 4;
end
A.reticolo = rand(L)<p; % matrix field with prob p
A.label = zeros(L); % label field
A.prob = p; % prob field
idx = reshape(1:L^2, L, L);
nnl = [zeros(L,1) idx(:,1:L-1)]; % find near neighbor (NN) on the left
nnu = [zeros(1,L); idx(1:L-1,:)]; % find NN up
largest_label = 1;
for i = 1:L^2
left = i-L;
up = i-1;
if(A.reticolo(i) && ~A.label(i)) %If the site is coloured and has no label
%if it has NN-left and NN-up
if (nnu(i) && nnl(i) && A.reticolo(nnu(i)) && A.reticolo(nnl(i))) %#ok<*ALIGN>
% A.label(i) = min(A.label(i-L), A.label(i-1)); -> i tried
% a workaround that didn't really work
Union(left, up);
% If there's a NNL
elseif (nnl(i) && A.reticolo(nnl(i)))
A.label(i) = A.label(nnl(i)); %-> this is what i'm using
% since Find isn't working. This works for up and left cases.
% A.label(i) = Find(left); -> I should be using this instead
% If there's a NNU
elseif (nnu(i) && A.reticolo(nnu(i)))
A.label(i) = A.label(nnu(i));
%A.label(i) = Find(up) -> again, i should be using this instead of the line above
% If it doesn't have neighbours at all
else,
largest_label = largest_label +1;
A.label(i) = largest_label;
end
end
end
function F = Find(x)
while A.label(x) ~= x %here there seems to be a problem, that i don' get
x = A.label(x);
end
F = x;
end
function Union(x,y)
A.label(Find(x)) = Find(y);
end
end
And the errors I'm getting
Array indices must be positive integers or logical values.
Error in HK/Find (line 56)
while A.label(x) ~= x
Error in HK/Union (line 63)
A.label(Find(x)) = Find(y);
Error in HK (line 32)
Union(left, up);