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: This function is called by:

SUBFUNCTIONS ^

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