lundi 6 avril 2020

Constructing a random graph with given diameter in matlab

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