%largest class and number of classes
%for a binary matrix chosen at random
%with varying probabilities of 1s

n=1000; %matrix dimension
npr=100; %number of probabilities

pr=[0:1/(npr-1):1]*8/n;
 
mv=zeros(1,npr); 
nv=mv; 
mvt=mv;


for (ipr=1:npr)
    ipr
p=pr(ipr);
P=(rand(n,n)<p);
P1=((eye(n)+P)>0);
Q=(P1^2>0); 

while ~(isequal(P1,Q))
  P1=Q;
  Q=(P1^2>0); 
end
sf=zeros(1,n); 
ncl=0; maxcls=0;
for (i=1:n)
   if (sf(i)==0)
      ncl=ncl+1; 
      cls=0;
      %fprintf('%d:',i); 
      sf(i)=1; 
      closed=1; 
      for (j=1:n)
          if ((Q(i,j)>0)&&(Q(j,i)>0))
             %fprintf('%d ',j); 
             sf(j)=1;
             cls=cls+1;
          elseif (Q(i,j)>0)
             closed=0; 
          end
      end
%       for (j=(i+1):n)
%           if ((Q(i,j)>0)&&(Q(j,i)>0))
%              fprintf('%d ',j); 
%              sf(j)=1;
%           end
%       end
      %fprintf(' size=%d ', cls); 
      if (cls>maxcls) 
          maxcls=cls;
          if closed mvt(ipr)=0;
          else mvt(ipr)=1; 
          end
      end
%       if (closed) 
%           fprintf('r\n');
%       else
%           fprintf('t\n');
%           mvt=1; 
%       end
      
          
      %fprintf('\n'); 
   end
end
%fprintf('no of classes=%d\n', ncl);
%fprintf('max size of class=%d\n', maxcls);
nv(ipr)=ncl; mv(ipr)=maxcls;
end

plot(pr,nv, 'LineWidth',1.5, 'Color', [1 0 0] );
hold on;
plot(pr,mv, 'LineWidth',1.5, 'Color', [0 0 1] );

plot(pr(mvt==1),mv(mvt==1), '-o','LineStyle','none',  'MarkerSize', 2,...
    'MarkerFaceColor',[0,0,1], 'MarkerEdgeColor', 'none');
plot(pr(mvt==0),mv(mvt==0), '-o','LineStyle','none',  'MarkerSize', 3,...
    'MarkerFaceColor',[0,1,0], 'MarkerEdgeColor', 'none');
str=strcat('Classes in a random transition matrix,', 'n', sprintf('=%d', n));

title(str,'FontSize',10);
xlabel('$p$', 'Interpreter', 'Latex')
ylabel('largest class (blue), no. of classes (red)', 'Interpreter', 'Latex');
str=strcat('n', sprintf('=%d', n));
 

hold off;











   
