Description of edge_color

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:

• color color(g,algo) --- color the graph g by a given algorithm
• edge_color edge_color(g,algo) --- find a proper edge coloring of the graph g
• edges edges(g) --- list the edges in g as a 2-column matrix
• free free(g) --- free the graph from the system
• graph graph: constructor for the graph class
• line_graph line_graph(g,h) --- set g to be the line graph of h

This function is called by:

• cdraw cdraw(g,coloring) -- draw g with a given vertex coloring
• draw draw(g) --- draw g in a figure window
• edge_color edge_color(g,algo) --- find a proper edge coloring of the graph g

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