function [ A ] = gen_sf( n , n_0 , m  , quiet)
%GEN_SF  Generates a scale-free network
%
%  GEN_SF(n,n_0,m) uses the method proposed by Barabási and Albert
%    in 2000 but with p=q=0 to generate a network with the scale free
%    character and gamma ~ -3:  n  is the targeted number of nodes,
%    n_0 is the initial number of nodes (also called m_0) and  m  is
%    the number of edges added at each time step.
%
%    Note that here: the number of total steps is  t = n - n_0
%
%  Last change:  10/2/2005 - Florian Knorn

if nargin < 3
	error('Please provide enough input arguments !');
end

if m > n_0
	error('m must be <= n_0 !');
end

if nargin ~= 4
	quiet = 0;
end

rand('state',sum(100*clock));		% reset random number generator to a different state

A = logical(sparse(n,n));

if n_0 == 1 % danger of dividing by zero at p_a
	fake = true;
else % more then 1 initial node: create fully conn graph on them
	fake = false;
	A(1:n_0,1:n_0) = true(n_0,n_0) - logical(speye(n_0,n_0));
end

for t = 1:n-n_0 % time-step-loop
	if fake
		pcum = 1; % faked cumulative sum for t == 1
		if t > 1
			fake = false; % stop faking for t > 2
			% we now should 2 nodes and 1 edge -> p_a = 1/2 | 1/2
			pcum = [.5 1];
		end
	else
		deg = sum( A(1:n_0+t-1,1:n_0+t-1) , 2); % node degrees
		pcum = cumsum( deg / sum(deg) ); % cum probs
	end

	% let's place the m new edges
	for j = 1:m

		succeeded = false;
		while ~succeeded % while not succeeded in placing the new edge

			% determine winning node that'll get an edge with the new node
			temp = find(pcum>rand);
			
			% check if we can place the edge here
			if ~A(temp(1),n_0+t)
				succeeded = true;
			end
		end

		% now, place the edge
		A(temp(1),n_0+t) = true; A(n_0+t,temp(1)) = true;

	end

end

if ~quiet
	disp(sprintf('Scale-free graph with %i nodes and %i edges successfully created',n,nnz(A)/2));
	disp(sprintf('adding m = %i nodes in each of the t = %i steps',m,n-n_0));
end