0001 function [is, rounds] = mis (G)
0002 % MIS - Find a maximal independent vertex set in a graph G
0003 %       using Luby's algorithm.
0004 %
0005 % [IS, rounds] = MIS (G)
0006 %
0007 % Input:  G     - undirected graph (symmetric matrix)
0008 %
0009 % Output: IS     - Set of maximally independent vertices
0010 %         rounds - Number of rounds used
0011 %
0012 % Viral Shah (C) 2005. All rights reserved.
0013 
0014 
0015 warning off MATLAB:divideByZero
0016 
0017 is = [];
0018 n = length (G);
0019 map = 1:length(G);
0020 G = G - diag(diag(G));
0021 
0022 rounds = 0;
0023 while n > 0
0024     rounds = rounds + 1;
0025     n = length (G);
0026 
0027     fprintf ('Round %d: %d nodes\n', rounds, n);
0028     
0029     % Select vertices where rand < 1 / (2d)
0030     % Degree 0 nodes always get chosen.
0031     deg = full(sum (G,2));
0032     prob = 1 ./ (2 * deg);
0033     select = rand(n,1) <= prob;
0034     
0035     % If neighbours selected, keep vertex with higher degree
0036     neigh = select & G * select;
0037     if ~isempty(neigh)
0038         f = find(neigh);
0039         degf = deg(f);
0040         Gneigh = G (f, f);
0041         [I J] = find(Gneigh);
0042         keep = degf(I) < degf(J);
0043         fk = [I(keep); J(keep == 0)];
0044         select(f(fk)) = 0;
0045     end
0046     
0047     % Add selected vertices and degree 0 to independent set
0048     is = [is map(select)];
0049     
0050     % Exclude neighbours of selected vertices from further consideration
0051     select = select | G * select;
0052     remain = select == 0;
0053     
0054     % Iterate on remaining subgraph
0055     G = G (remain, remain);
0056     map = map (remain);   
0057 end
0058 
0059 warning on MATLAB:divideByZero
0060