% This generates the Laplacian of a graph. It starts by constructing k
% cliques Ci, of sizes m1,...,mk. It joins all edges of Ci, i = 1,...,k, to
% all edges of Ck. Random edges are then added to the complement graph,
% according to the specified percentage.

function [L,edgenumber] = graph_gen(m,p)

% input
% m   - column vector containing sizes of the k cliques
% p   - percentage of edges in the complement graph to be added
%
% Output
% L          - Laplacian matrix
% edgenumber - number of edges actually added

if size(m,1) < size(m,2) % if m is row vector
  m = m';
end

if p < 0 || p > 100
  error(' p has to be between 0 and 100\n')
end

n = sum(m);
k = size(m,1);

% generate the core graph
L = sparse(n,n);
mcount = 0;
for i = 1:k
  L(mcount + 1:mcount + m(i),mcount + 1:mcount + m(i)) = -1;
  L(mcount + 1:mcount + m(i),end-m(k)+1:end) = -1;
  L(end-m(k)+1:end,mcount + 1:mcount + m(i)) = -1;
  mcount = mcount + m(i);
end

% generate random edges 
[I,J] = find(L == 0); % entries corresponding to no edge
card = sum(J > I); % count only upper triangular non-edges
edgenumber = floor(p*card/100); % number of edges to add

% extract only those entries from upper triangular part
index2 = find(J > I);
I2 = I(index2); J2 = J(index2);

randcard = randperm(card); % random permutation of size card
count = sub2ind([n n],I2,J2); % change to vector indexing

tmp = spalloc(n,n,edgenumber);
tmp(count(randcard(1:edgenumber))) = -1;

L = L + tmp + tmp'; % symmetrize

% form Laplacian matrix
sumL = sum(L,2);
for i = 1:n
  L(i,i) = -sumL(i) - 1;
end