Description of interval_graph

Home > matgraph > @graph > interval_graph.m

interval_graph

PURPOSE

interval_graph(g,ilist) --- create an interval graph

SYNOPSIS

function interval_graph(g,ilist)

DESCRIPTION

 interval_graph(g,ilist) --- create an interval graph
 ilist is an n-by-2 list of intervals.

CROSS-REFERENCE INFORMATION

This function calls:

• add add --- add edge(s) to the graph
• clear_edges clear_edges(g) --- delete all edges of g
• renumber renumber the vertices of a graph
• 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:

SUBFUNCTIONS

• function yn = meets(a,b)

SOURCE CODE

0001 function interval_graph(g,ilist)
0002 % interval_graph(g,ilist) --- create an interval graph
0003 % ilist is an n-by-2 list of intervals.
0004 
0005 [n,x] = size(ilist);
0006 
0007 for i=1:n
0008     ilist(i,:) = sort(ilist(i,:));
0009 end
0010 
0011 [ilist,idx] = sortrows(ilist);
0012 
0013 resize(g,n);
0014 clear_edges(g);
0015 rmxy(g);
0016 
0017 for i=1:n-1
0018     a = ilist(i,:);
0019     for j=i+1:n
0020         b = ilist(j,:);
0021         if (meets(a,b))
0022             add(g,i,j);
0023         end
0024         if a(2) < b(1)
0025             break
0026         end
0027     end
0028 end
0029 
0030 renumber(g,idx);
0031 
0032 
0033 function yn = meets(a,b)
0034 
0035 if (a(2) < b(1)) | (b(2) < a(1))
0036     yn = 0;
0037 else
0038     yn = 1;
0039 end

---

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