Home > matgraph > @graph > edge_color.m

edge_color

PURPOSE ^

edge_color(g,algo) --- find a proper edge coloring of the graph g

SYNOPSIS ^

function c = edge_color(g,algo)

DESCRIPTION ^

 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!

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

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

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