edge_color(g,algo) --- find a proper edge coloring of the graph g The returned matrix has three columns. Each row of this matrix of the form [i j c] where ij is an edge of the graph and c is a color number (from 1 to the number of colors used). algo denotes an algorithm. The choices are: greedy: use a greedy coloring, based on the line graph (default) optimal: create an optimal coloring, based on the line graph vizing: create a coloring that uses at most max(deg(g))+1 colors NOTE: THIS IS UNIMPLEMENTED AT THIS TIME!
0001 function c = edge_color(g,algo) 0002 % edge_color(g,algo) --- find a proper edge coloring of the graph g 0003 % The returned matrix has three columns. Each row of this matrix of the 0004 % form [i j c] where ij is an edge of the graph and c is a color number 0005 % (from 1 to the number of colors used). 0006 % 0007 % algo denotes an algorithm. The choices are: 0008 % 0009 % greedy: use a greedy coloring, based on the line graph (default) 0010 % 0011 % optimal: create an optimal coloring, based on the line graph 0012 % 0013 % vizing: create a coloring that uses at most max(deg(g))+1 colors 0014 % NOTE: THIS IS UNIMPLEMENTED AT THIS TIME! 0015 0016 if nargin < 2 0017 algo = 'greedy'; 0018 end 0019 0020 switch (lower(algo)) 0021 case {'greedy','optimal'} 0022 h = graph; 0023 line_graph(h,g); 0024 p = color(h,algo); 0025 c = [edges(g), array(p)']; 0026 free(h); 0027 0028 case 'vizing' 0029 warning('edge_color:novizing',... 0030 'The "vizing" algorithm is not implemented. Using greedy algorithm.') 0031 c = edge_color(g,'greedy'); 0032 0033 otherwise 0034 error(['Unknown algorithm: ', algo]); 0035 end