I want to generate a random graph using MATLAB
with the following properties:
- having 21 vertices. i.e. odd number of vertices
- the degree of all vertices is 5 except at one vertex with degree 6.
I have tried the following MATLAB
code. But it will not give me the required graph . I was wondering if someone can help me?
function A = RandomGraph(n, d)
n = 21; % Number of vertices
d = 5; %degree at vertex
matIter = 10;
%a list of open half-edges
U = repmat(1:n,1,d);
%the graphs adajency matrix
A=sparse(n,n);
edgesTested=0;
repetition=1;
%continue until a proper graph is formed
while ~isempty(U) && repetition < matIter
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);
if v1==19
d = 6; %set degree 6 at vertex 19
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);
A = sparse(n,n);
end
else
%add edge to graph
A(v1, v2)=1;
A(v2, v1)=1;
%remove used half-edges
v = sort([i1,i2]);
U = [U(1:v(1)-1), U(v(1)+1:v(2)-1), U(v(2)+1:end)];
end
%plot graph
G=graph(A);
%unlabelled graph plot
plot(G,'-','NodeLabel',{})
end
function msg=isRegularGraph(G)
msg=[];
%check symmetry
if (norm(G-G','fro')>0)
msg=[msg,' is not symmetric, '];
end
%check parallel edged
if (max(G(:))>1)
msg=[msg,sprintf(' has %d parallel edges, ',length(find(G(:)>1)) )];
end
if (norm(diag(G))>0)
msg=[msg,sprintf(' has %d self loops, ',length(find(diag(G)>0)) )];
end
Aucun commentaire:
Enregistrer un commentaire