How to generate an undirected random graph with specified node number and diameter?

Suppose that node number is N. The graph has a diameter of D so that the graph must be connected. How to generate such a random graph with Matlab?

Answer 1

[Kartik Pontula]

You can accomplish this by pasting the following code into the script file generateGraph.m :-

function adjMat = generateGraph(N, D)
    % Initialize an empty N*N adjacency matrix
    adjMat = zeros(N);

    % Generate a random spanning tree using DFS
    visited = zeros(1, N);
    current = 1;
    stack = [];
    visited(current) = 1;
    while any(visited == 0)
        unvisited = find(visited == 0);
        next = unvisited(randi(length(unvisited)));
        adjMat(current, next) = 1;
        adjMat(next, current) = 1;
        stack = [stack, current];
        current = next;
        visited(current) = 1;
        while isempty(stack) == 0 && all(visited(stack) == 1)
            current = stack(end);
            stack(end) = [];
        end
    end

    % Connect remaining disconnected nodes to the spanning tree, for making the graph connected
    while any(visited == 0)
        unvisited = find(visited == 0);
        connectedNode = unvisited(randi(length(unvisited)));
        existingNodes = find(visited == 1);
        newNode = existingNodes(randi(length(existingNodes)));
        adjMat(connectedNode, newNode) = 1;
        adjMat(newNode, connectedNode) = 1;
        visited(connectedNode) = 1;
    end

    % Keep adding edges until the desired diameter D is reached
    diameter = computeDiameter(adjMat);
    while diameter < D
        % Randomly select two nodes that are not connected and add an edge between them. Repeat this until the diameter of the graph reaches D.
        unconnectedNodes = find(sum(adjMat) < N - 1);
        node1 = unconnectedNodes(randi(length(unconnectedNodes)));
        node2 = unconnectedNodes(randi(length(unconnectedNodes)));
        adjMat(node1, node2) = 1;
        adjMat(node2, node1) = 1;
        diameter = computeDiameter(adjMat);
    end
end

The above script also uses a helper function computeDiameter.m to check the diameter of the graph. Here is the function:

function diameter = computeDiameter(adjMat)
    % Compute the diameter of the graph using Floyd-Warshall algorithm
    N = size(adjMat, 1);
    distanceMatrix = adjMat;
    for k = 1:N
        for i = 1:N
            for j = 1:N
                if distanceMatrix(i, j) == 0 || (distanceMatrix(i, k) + distanceMatrix(k, j)) < distanceMatrix(i, j)
                    distanceMatrix(i, j) = distanceMatrix(i, k) + distanceMatrix(k, j);
                end
            end
        end
    end
    diameter = max(distanceMatrix(:));
end

Hope this helps!