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.
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'));
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.
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;
70
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?