Description of line_graph

Home > matgraph > @graph > line_graph.m

line_graph

PURPOSE

line_graph(g,h) --- set g to be the line graph of h

SYNOPSIS

function line_graph(g,h)

DESCRIPTION

 line_graph(g,h) --- set g to be the line graph of h
 The line graph of h is the intersection graph of its edges.

CROSS-REFERENCE INFORMATION

This function calls:

• add add --- add edge(s) to the graph
• clear_edges clear_edges(g) --- delete all edges of g
• edges edges(g) --- list the edges in g as a 2-column matrix
• embed embed --- create an embedding for a graph
• getxy getxy(g) --- give g's embedding (or [] if g doesn't have one)
• hasxy hasxy(g) --- determine if an embedding has been created for g
• resize resize(g,n) --- change the number of vertices in g to n
• rmxy rmxy(g) --- erase g's embedding
• size size(g) --- returns [nv,ne] for the graph

This function is called by:

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

SUBFUNCTIONS

• function yn = common_endpoint(e1,e2)

SOURCE CODE

0001 function line_graph(g,h)
0002 % line_graph(g,h) --- set g to be the line graph of h
0003 % The line graph of h is the intersection graph of its edges.
0004 
0005 elist = sortrows(edges(h));
0006 [m,c] = size(elist);
0007 
0008 resize(g,m);
0009 rmxy(g);
0010 clear_edges(g);
0011 
0012 for i=1:m-1;
0013     a = elist(i,:);
0014     for j=i+1:m
0015         b = elist(j,:);
0016         if common_endpoint(a,b)
0017             add(g,i,j);
0018         end
0019         if (a(2) < b(1))
0020             break
0021         end
0022     end
0023 end
0024 
0025 
0026 if hasxy(h)
0027     xy = getxy(h);
0028     gxy = zeros(m,2);
0029     for i=1:m
0030         a = elist(i,1);
0031         b = elist(i,2);
0032         gxy(i,:) = (xy(a,:) + xy(b,:))/2;
0033     end
0034     embed(g,gxy);
0035 end
0036 
0037 
0038 function yn = common_endpoint(e1,e2)
0039 yn = ( e1(1) == e2(1) ) | ( e1(1) == e2(2) ) | ( e1(2) == e2(1) ) | ...
0040     (e1(2) == e2(2));
0041

---

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