0001 function p = color(g,algo,max_time)
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020
0021
0022
0023 if nargin <= 1
0024 algo = 'greedy';
0025 end
0026
0027
0028 switch lower(algo)
0029 case 'greedy'
0030 p = greedy_color(g);
0031 case 'rs'
0032 p = rs_color(g);
0033 case 'repeat'
0034 if nargin <=2
0035 max_time = 30;
0036 end
0037 p = repeat(g,max_time);
0038 case 'optimal'
0039 p = optimal_color(g);
0040 case 'matlab'
0041 p = matlab_color(g);
0042 otherwise
0043 error(['Algorithm "', algo, '" unimplemented']);
0044 end
0045
0046
0047
0048
0049
0050
0051 function p = greedy_color(g)
0052
0053 n = nv(g);
0054 d = deg(g);
0055 [dd,vlist] = sort(-d);
0056 clear dd;
0057 p = sequential_color(g,vlist,n);
0058 return
0059
0060
0061
0062 function p = rs_color(g,max_colors)
0063
0064
0065 n = nv(g);
0066 if nargin <= 1
0067 max_colors = n;
0068 end
0069 vlist = randperm(n);
0070 p = sequential_color(g,vlist,max_colors);
0071 return
0072
0073
0074
0075 function p = repeat(g,max_time)
0076
0077
0078
0079 tic;
0080 n = nv(g);
0081 p = greedy_color(g);
0082 max_colors = np(p)-1;
0083 while (toc < max_time)
0084 temp = rs_color(g,max_colors);
0085 if ~ (np(temp)==0)
0086 p = temp;
0087 max_colors = np(p)-1;
0088 end
0089 end
0090 return
0091
0092
0093
0094 function p = optimal_color(g)
0095
0096
0097 n = nv(g);
0098 p = greedy_color(g);
0099 p = complete_extend(g,1,zeros(1,n),p);
0100 return
0101
0102
0103
0104 function p = complete_extend(g,v,colors,best)
0105
0106
0107
0108 n = nv(g);
0109 vneig = neighbors(g,v);
0110 cneig = unique(colors(vneig));
0111 avail = setdiff(1:min(v,np(best)-1),cneig);
0112 for k=avail
0113 colors(v)=k;
0114 if v == n
0115 mc = max(colors);
0116 cpart = cell(1,mc);
0117 for k=1:mc
0118 cpart{k} = find(colors==k);
0119 end
0120 p = partition(cpart);
0121 if np(p) < np(best)
0122 best = p;
0123 end
0124 else
0125 best = complete_extend(g,v+1,colors,best);
0126 end
0127 end
0128 p = best;
0129 return
0130
0131
0132
0133 function p = sequential_color(g,vlist,max_colors)
0134
0135
0136
0137
0138 n = nv(g);
0139 colors = zeros(1,n);
0140
0141
0142 for k=1:n
0143 v = vlist(k);
0144 vneig = neighbors(g,v);
0145 cneig = unique(colors(vneig));
0146 if length(cneig) == 0
0147 mc = 0;
0148 else
0149 mc = cneig(length(cneig));
0150 end
0151 avail = setdiff(1:mc,cneig);
0152 if isempty(avail)
0153 if mc+1 > max_colors
0154 p = partition(0);
0155 return
0156 else
0157 colors(v) = mc+1;
0158 end
0159 else
0160 colors(v) = min(avail);
0161 end
0162 end
0163
0164 mc = max(colors);
0165 cpart = cell(1,mc);
0166 for k=1:mc
0167 cpart{k} = find(colors==k);
0168 end
0169 p = partition(cpart);
0170 return
0171
0172
0173
0174
0175 function p = matlab_color(g)
0176
0177
0178
0179
0180
0181 M = incidence_matrix(g)';
0182 i = color(M);
0183 nc = max(i);
0184 parts = cell(nc,1);
0185 for k=1:nc
0186 parts{k} = find(i==k);
0187 end
0188 p = partition(parts);
0189 return
0190
0191