View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Random Regular generator

3.7 | 4 ratings Rate this file 10 Downloads (last 30 days) File Size: 2.54 KB File ID: #29786 Version: 1.0

Random Regular generator


golan pundak (view profile)


creates a random regular graph in the pairing model

| Watch this File

File Information

the function:
A = createRandRegGraph(vertNum, deg)
create a simple d-regular undirected graph
vertNum - number of vertices.
deg - the degree of each vertex.
A is asparse matrix representation of the graph.
reference for "The pairing model":

MATLAB release MATLAB 7.11 (R2010b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (9)
10 Jul 2016 Vikash Sehwag

19 May 2016 a b

a b (view profile)

thank was really useful

Comment only
31 Jul 2013 golan pundak

golan pundak (view profile)

Poormina: This code does (should) produce single undirected edge between nodes.
As a note: If you don't care about multiple edges and self loops there is a much simpler algorithm: pick d/2 permutations at random.
The reason this code is complicated is because it avoids multiple edges and self loops.

Comment only
31 Jul 2013 Poornima

Dear Golan
Thank you. That was really a valuable suggestion! :)
Well, When I meant 'one edge', I meant undirected edges.... or a single edge bw nodes.

29 Jul 2013 golan pundak

golan pundak (view profile)


You can add weights by multiplying the output with a random matrix
A_W = A.*rand(size(A,1), size(A,2))

Not sure what do you mean by 'one edge'. If you want to edges to be directed the nice property of d-regularity will be lost.

Comment only
29 Jul 2013 Poornima

A very nice script. Thank you.

Is it possible to display the graph with just one edge between the nodes and not two with this code? Also, is it possible add weights to the edges? Thanks in advance...

h = view(biograph(G,[],'ShowArrows','Off','ShowWeights','on'));

26 Apr 2012 Felix Goldberg

Overall, very nice.
But I'm afraid a bug may be lurking somewhere. Sometimes I call this function and get a zero matrix. Is this a bug or a feature?

12 Feb 2012 golan pundak

golan pundak (view profile)

So it seems these are all problems of dynamically allocating memory and coping data. Here are 2 optimizations that can solve this:
1. Replace the sparse n*n matrix A by a preallocated n*d adjacency list, filled initially with -1.

2. Instead of recreating U (half edges), keep its size as a separate variable and only swap elements when updating it.

Maybe I'll get to it some day :)

Comment only
12 Feb 2012 Derek O'Connor

This is a very useful function for graph-algorithm theoreticians and testers. However, its usefulness is limited by a severe bottleneck which occurs here:

67 %add edge to graph
5.61 75000 68 A(v1, v2)=1;
5.26 75000 69 A(v2, v1)=1;
71 %remove used half-edges
0.36 75000 72 v = sort([i1,i2]);
26.05 75000 73 U = [U(1:v(1)-1), U(v(1)+1:v(2)-1), U(v(2)+1:end)];
0.01 75000 74 end
0.65 75016 75 end

41.00 Total Time

As usual, the problem is caused by the inappropriate use of Matlab's powerful array manipulation operations.

Can the author devise a better way to remove the half-edges?

Comment only

Contact us