function [Nnew, Enew] = MakeRandomGraph(N,p)
% Makes a random Erdos-Renyi graph G(N,p), i.e., with N verticess and each pair
% of vertices is connected by an edge with probability p.
% (See https://en.wikipedia.org/wiki/Erd?s?Rényi_model)
%
% Then the graph is tested for being connectded using the
% depth-first-dsearch algorithm (DFS).
% (See https://en.wikipedia.org/wiki/Depth-first_search)
%
% If the connected component containing vertex 1 contains at least 80% of vertices,
% the graph is accepted and output
% Nnew = the final number of vertices, 
% Enew is the list of edges, a #edges-by-2 array.
%
% Otherwise, a graph is regenerated and tested again.
%%
% N = 100;
% p = 0.1;
Nmin = floor(0.8*N);
flag = 0;
while flag == 0
    % Generate a gandom graph
    E = [];
    for i = 1 : N - 1
        for j = i + 1 : N
            eta = rand;
            if eta < p
                E = [E;i,j];
            end
        end
    end
    % Test the graph using the DFS
    % visited(i) = 1 if vertex i has been visited, 0 otherwise
    visited = zeros(N,1);
    visited = DFS(E,1,visited);
    ind = find(visited == 1); % find all visited vertices
    if length(ind) >= Nmin
        % accept the graph
        flag = 1;
        Nnew = length(ind);
        ie = find(visited(E(:,1)) == 1 & visited(E(:,2)) == 1);
        Enew = E(ie,:);
        % relabel vertices to make them numbered from 1 to Nnew
        newlabel = zeros(N,1);
        newlabel(ind) = [1 : Nnew]';
        Enew(:,1) = newlabel(Enew(:,1));
        Enew(:,2) = newlabel(Enew(:,2));
%         fprintf('Nvertices = %d, Nedges = %d\n',Nnew,size(Enew,1));
    end
end
end
%% Depth-First-Search
function visited = DFS(E,v,visited)
visited(v) = 1;
ind = find(E(:,1) == v | E(:,2) == v); % find vertices adjacent to v
if ~isempty(ind)
    nneib = length(ind);
    for k = 1 : nneib
        w = setdiff(E(ind(k),:),v); % get a neighbor of v
        if visited(w) == 0 % if this neighbor has not been visited yet
            visited = DFS(E,w,visited);
        end
    end
end
end

            