vendredi 3 avril 2020

generating a random graph with a special case using MATLAB

I want to generate a random graph using MATLAB with the following properties:

  1. having 21 vertices. i.e. odd number of vertices
  2. 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