Home > matgraph > @graph > color.m

color

PURPOSE ^

color(g,algo) --- color the graph g by a given algorithm

SYNOPSIS ^

function p = color(g,algo,max_time)

DESCRIPTION ^

 color(g,algo) --- color the graph g by a given algorithm
 The algorithms are as follows:

 'greedy':     the default, puts vertices in descending order of degree 
               and runs sequential coloring

 'rs':         random sequence, puts vertices in random order and 
               runs sequential coloring

 'repeat':     runs the 'rs' algorithm repeatedly until a fixed amount
               of time passes (30 seconds); this can also be called as
               color(g,'repeat',max_time)

 'optimal':    always finds a minimum coloring (slow on large graphs)

 'matlab':     use the COLOR method from the Optimization Toolbox
               (this is experimental --- it appears to give the same
               result as 'greedy')

 Algorithms rs, repeat, and optimal coded by Brian Towne.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function p = color(g,algo,max_time)
0002 % color(g,algo) --- color the graph g by a given algorithm
0003 % The algorithms are as follows:
0004 %
0005 % 'greedy':     the default, puts vertices in descending order of degree
0006 %               and runs sequential coloring
0007 %
0008 % 'rs':         random sequence, puts vertices in random order and
0009 %               runs sequential coloring
0010 %
0011 % 'repeat':     runs the 'rs' algorithm repeatedly until a fixed amount
0012 %               of time passes (30 seconds); this can also be called as
0013 %               color(g,'repeat',max_time)
0014 %
0015 % 'optimal':    always finds a minimum coloring (slow on large graphs)
0016 %
0017 % 'matlab':     use the COLOR method from the Optimization Toolbox
0018 %               (this is experimental --- it appears to give the same
0019 %               result as 'greedy')
0020 %
0021 % Algorithms rs, repeat, and optimal coded by Brian Towne.
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 % Random sequence
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 % Starts w/ greedy coloring, then loops through random permutations
0077 % until it finds an optimal coloring.
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) % if rs_color returned w/o exhausting max_colors
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 % Finds a minimum coloring for g. Works by calling complete_extend.
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 % Recursive function. Loops through every possible color for a given vertex.
0106 % p is the current coloring. best is the best coloring found thus far.
0107 
0108 n = nv(g);
0109 vneig = neighbors(g,v);  % neighbors of v
0110 cneig = unique(colors(vneig));  % colors on neighbors
0111 avail = setdiff(1:min(v,np(best)-1),cneig); % colors available
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 % Runs sequential coloring on vertices in order of vlist
0135 % Exits if it uses more than max_colors. Setting max_colors = nv(g)
0136 % means this will never happen.
0137 
0138 n = nv(g);
0139 colors = zeros(1,n);
0140 
0141 % scan vertices by order in vlist
0142 for k=1:n
0143     v = vlist(k);
0144     vneig = neighbors(g,v);  % neighbors of v
0145     cneig = unique(colors(vneig));  % colors on neighbors
0146     if length(cneig) == 0
0147         mc = 0;
0148     else
0149         mc = cneig(length(cneig)); % max color seen on neighbors
0150     end
0151     avail = setdiff(1:mc,cneig); % colors available (if any)
0152     if isempty(avail)
0153         if mc+1 > max_colors % if max_colors is exhausted, exit
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 % Uses the COLOR method from the optimization toolbox.
0177 % That COLOR takes as input an interesection graph representation of g. The
0178 % easiest way for us to do that is to use the incidence matrix, but perhaps
0179 % if we used a smarter intersection graph representation, we could get
0180 % better results from the Optimization Toolbox's COLOR.
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

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