function s = misluby(A, xy);
% MISLUBY : Luby's randomized independent set algorithm
%
% s = misluby(A) returns a maximal independent set of vertices
% in the undirected graph whose adjacency matrix is A
% s = misluby(A, xy) also draws pictures with coords xy

picture = nargin > 1;
A = A | A';
A = A - diag(diag(A));
n = length(A);

if picture
    gplotg(A,xy,'w'); title('Input graph'); 
    disp('hit space to continue'); pause
end;

s = [];         % independent set
c = ones(1,n);  % candidate vertex map
k = 0;
while nnz(c) > 0
    k = k+1;
    r = rand(1,n);
    mask = c';
    for v = find(c)
        adjv = find(A(:,v) & mask);
        if r(v) < min([ inf r(adjv)])
            s = [s v];
            c(v) = 0;
            c(adjv) = 0;
        end;
    end;
    if picture
        highlight(A,xy,s,'r','w', 20);
        title(['After phase ' num2str(k) ', size ' num2str(length(s))]);
        fprintf('Phase %d: MIS size = %d\n', k, length(s));
        disp('hit space to continue'); pause
    end;
end;
if ~picture
    fprintf('Phase %d: MIS size = %d\n', k, length(s));
end;