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: 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