I would like to construct a random graph with a given diameter which is 2.
The following MATLAB
code yields a graph with 21 nodes and the degree of all nodes is 5 except at one node (with degree 6). But the graph will not provide the required diameter (this code provides diameter 3). I need to get a graph with diameter 2. How could I rearrange the code so that I can get the graph with diameter 2? So far I have tried to use matlab
function distances(G)
, but it gives error. I don't know where I include it in my code, or any other technique. Also I tried backtracking technique (removing edges starting from the complete graph), but I got stuck. Please any help? Thank you.
function A = RandomRegularGraph(n, d)
clc;clear;close
n = 21; % Number of vertices
d = 5; %degree at all vertices, except at one vertex
matIter = 10;
%a list of open half-edges
U = repmat(1:n,1,d);
U(end+1)=U(end);
%the graphs adajency matrix
A=sparse(n,n);
edgesTested=0;
repetition=1;
%continue until a proper graph is formed
while ~isempty(U) && max(distances(G))==2 && repetition < matIter % max(distances(G))==2 means diameter of a graph is 2
edgesTested = edgesTested + 1;
%chose at random 2 half edges
i1 = ceil(rand*length(U));
i2 = ceil(rand*length(U));
v1 = U(i1);
v2 = U(i2);
end
%check that there are no loops nor parallel edges
if (v1 == v2) || (A(v1,v2) == 1)
%restart process if needed
if (edgesTested == n*d)
repetition=repetition+1;
edgesTested = 0;
U = repmat(1:n,1,d);
U(end+1)=U(end);
A = sparse(n,n);
end
else
%add edge to graph
A(v1, v2)=1;
A(v2, v1)=1;
%remove used half-edges
U([i1,i2])=[];
end
%plot graph
G=graph(A);
%unlabeled graph plot
plot(G,'-','NodeLabel',{})
end
Aucun commentaire:
Enregistrer un commentaire