Description of random_regular

Home > matgraph > @graph > random_regular.m

random_regular

PURPOSE

random_regular(g,n,k) --- create a random regular graph

SYNOPSIS

function random_regular(g,n,k)

DESCRIPTION

 random_regular(g,n,k) --- create a random regular graph
 g is the graph to be overwritten
 n is the number of vertices
 k is the degree

 Note: This is a proof-of-concept version; no claims that this
 implementation is efficient!

CROSS-REFERENCE INFORMATION

This function calls:

• add add --- add edge(s) to the graph
• clear_edges clear_edges(g) --- delete all edges of g
• clear_labels clearl_labels(g) --- delete all labels in g
• copy copy(g,h) --- overwrite g with a copy of h
• free free(g) --- free the graph from the system
• graph graph: constructor for the graph class
• ne ne(g) --- number of edges in g or ne(g,h) --- check for inequality
• rmxy rmxy(g) --- erase g's embedding

This function is called by:

SOURCE CODE

0001 function random_regular(g,n,k)
0002 % random_regular(g,n,k) --- create a random regular graph
0003 % g is the graph to be overwritten
0004 % n is the number of vertices
0005 % k is the degree
0006 %
0007 % Note: This is a proof-of-concept version; no claims that this
0008 % implementation is efficient!
0009 
0010 if mod(n*k,2)==1
0011     error('We number have n*k even or no regular graph is possible');
0012 end
0013 
0014 if (k>n-1)
0015     error('Degree too large');
0016 end
0017 
0018 if (k<0)
0019     error('Degree must be nonnegative')
0020 end
0021 
0022 h = graph(n);  % scratch graph
0023 
0024 while(true)
0025     clear_edges(h);
0026     p = randperm(n*k);
0027     elist = reshape(p,n*k/2,2);
0028     elist = mod(elist,n)+1;
0029     if any(elist(:,1)==elist(:,2))  % reject if there's a loop
0030         continue
0031     end
0032     add(h,elist);
0033     if ne(h)== n*k/2
0034         break
0035     end
0036 end
0037 
0038 copy(g,h);
0039 rmxy(g);
0040 clear_labels(g);
0041 
0042 free(h);

---

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