0001 function out = chromatic_poly(g)
0002
0003
0004
0005
0006 out = chrompoly(double(matrix(g)));
0007
0008
0009
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
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
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
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
0054
0055
0056
0057
0058
0059 nb1=find(A(v1,:)==1);
0060 nbv=valseq(nb1);
0061 v2=nb1(min(find(nbv==max(nbv))));
0062
0063
0064
0065 A1=A;
0066 A1(v1,v2)=0;A1(v2,v1)=0;
0067 m1=chrompoly(A1);
0068
0069
0070
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
0096
0097 A1=A;
0098 A1(v1,v2)=1;A1(v2,v1)=1;
0099 m1=chrompoly(A1);
0100
0101
0102
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;
0122 end;
0123 end;
0124 end;
0125
0126
0127
0128
0129
0130
0131
0132
0133
0134
0135
0136
0137
0138
0139
0140
0141
0142
0143
0144
0145
0146
0147
0148
0149
0150
0151
0152
0153