Home > matgraph > @graph > chromatic_poly.m

chromatic_poly

PURPOSE ^

chrompoly(g) --- find the chromatic polynomial of g

SYNOPSIS ^

function out = chromatic_poly(g)

DESCRIPTION ^

 chrompoly(g) --- find the chromatic polynomial of g
 Warning: This algorithm is slow and unusable except for small graphs.
 Author: James Preen

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function out = chromatic_poly(g)
0002 % chrompoly(g) --- find the chromatic polynomial of g
0003 % Warning: This algorithm is slow and unusable except for small graphs.
0004 % Author: James Preen
0005 
0006 out = chrompoly(double(matrix(g)));
0007 
0008 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0009 % Here is James Preen's .m file very lightly edited %
0010 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0011 function out = chrompoly(A)
0012 
0013 out=[];
0014 n=size(A,1);
0015 e=sum(sum(A))/2;
0016 
0017 if e==0,
0018     out(n+1)=0;out(1)=1;
0019     %  disp(['that is k bar ' num2str(n)]);
0020 else
0021     somenew=1;
0022     nb=ceil(rand(1)*n);
0023     while somenew,
0024         nb2=rem(find(A(nb',:)')-1,n)+1;
0025         nb2=nb2';
0026         nb3=unique([nb nb2]);
0027         if size(nb3,2)==size(nb,2), somenew=0;end;
0028         nb=nb3;
0029     end
0030     if size(nb,2)<n,
0031         %       disp(['disconnected set: ' num2str([nb])]);
0032         nb2=setdiff(1:n,nb);
0033         A1=A;A1(:,nb2)=[];A1(nb2,:)=[];
0034         A2=A;A2(:,nb)=[];A2(nb,:)=[];
0035         out=conv(chrompoly(A1),chrompoly(A2));
0036     else
0037         valseq=sum(A);
0038         v1 = min(find(valseq==max(valseq)));
0039         if valseq(v1)==n-1,
0040             %   disp(['deleting vertex ' num2str([v1])]);
0041             A(v1,:)=[];A(:,v1)=[];
0042             p=chrompoly(A);
0043             bp=[1 -1];tp=[1];
0044             len=size(p,2);m3a=[];
0045             for i=1:size(p,2)
0046                 m3a=[0 m3a] + p(len+1-i)*tp;
0047                 tp=conv(tp,bp);
0048             end;
0049             out=[m3a 0];
0050         else
0051     
0052             if e < n*(n-1)/2,
0053                 %     %choose 2 random vertices
0054                 %     p=find(valseq>0);
0055                 %     v1=p(ceil(rand(1)*size(p,2)));
0056                 %     nb1=find(A(v1,:)==1);
0057                 %     v2=nb1(ceil(rand(1)*valseq(v1)));
0058 
0059                 nb1=find(A(v1,:)==1);
0060                 nbv=valseq(nb1);
0061                 v2=nb1(min(find(nbv==max(nbv))));
0062 
0063                 %deletion
0064                 %   disp(['deleting edge ' num2str([v1 v2])]);
0065                 A1=A;
0066                 A1(v1,v2)=0;A1(v2,v1)=0;
0067                 m1=chrompoly(A1);
0068     
0069                 %contraction
0070                 %    disp(['contracting edge ' num2str([v1 v2])]);
0071                 A2=A;
0072                 A2(v1,:)=(A2(v2,:)+A2(v1,:))>0;
0073                 A2(:,v1)=(A2(:,v2)+A2(:,v1))>0;
0074                 A2(v1,v1)=0;A2(:,v2)=[];A2(v2,:)=[];
0075                 m2=chrompoly(A2);
0076     
0077                 s1=size(m1,2);
0078                 s2=size(m2,2);
0079                 pd=zeros(1,abs(s2-s1));
0080     
0081                 if s1>s2,
0082                     out=m1 - [pd m2];
0083                 elseif s2>s1,
0084                     out=[pd m1] - m2;
0085                 else
0086                     out= m1 - m2;
0087                 end
0088             else
0089     
0090                 nb1=find(A(v1,:)==0);
0091                 nbv=valseq(nb1);
0092                 v2=v1;
0093                 while v2==v1, v2=nb1(min(find(nbv==max(nbv)))); end;
0094 
0095                 %deletion
0096                 %   disp(['adding edge ' num2str([v1 v2])]);
0097                 A1=A;
0098                 A1(v1,v2)=1;A1(v2,v1)=1;
0099                 m1=chrompoly(A1);
0100     
0101                 %contraction
0102                 %    disp(['contracting edge ' num2str([v1 v2])]);
0103                 A2=A;
0104                 A2(v1,:)=(A2(v2,:)+A2(v1,:))>0;
0105                 A2(:,v1)=(A2(:,v2)+A2(:,v1))>0;
0106                 A2(v1,v1)=0;A2(:,v2)=[];A2(v2,:)=[];
0107                 m2=chrompoly(A2);
0108     
0109                 s1=size(m1,2);
0110                 s2=size(m2,2);
0111                 pd=zeros(1,abs(s2-s1));
0112     
0113                 if s1>s2,
0114                     out=m1 + [pd m2];
0115                 elseif s2>s1,
0116                     out=[pd m1] + m2;
0117                 else
0118                     out= m1 + m2;
0119                 end
0120 
0121             end; %del-cont  / add-id
0122         end;
0123     end;
0124 end; %if e==0
0125 
0126 
0127 
0128 %%% OLD VERSION
0129 %
0130 % n = nv(g);
0131 % m = ne(g);
0132 %
0133 % if m==0
0134 %     p = zeros(1,n+1);
0135 %     p(1) = 1;
0136 %     return
0137 % end
0138 %
0139 % elist = edges(g);
0140 % u = elist(1,1);
0141 % v = elist(1,2);
0142 %
0143 % h = graph;
0144 % copy(h,g);
0145 %
0146 % delete(h,u,v);
0147 % p1 = chrompoly(h);
0148 % contract(h,u,v);
0149 % p2 = chrompoly(h);
0150 %
0151 % p = p1 - [0,p2];
0152 %
0153 % free(h);

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003