function [ A , reglatt ] = gen_sw2( N , k_init , p_a , quiet)
%GEN_SW2  Generates a small world network
%
%  GEN_SW2(N,k_init,p_a) uses a variation of the method 
%      proposed by Watts and Strogatz (1998) to generate a
%      network with the small world character (if the 
%      parameters are chosen appropriately):
%      N  is total number of nodes, k_init is the initial 
%      node degree of the network (k_init must be pair!, so 
%      that each node is connected to its 1st ... k_init-th
%      neighbours), and  p_a  is the probability of *adding*
%      a shortcut.
%
%  Last change:  10/2/2005 - Florian Knorn

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

if p_a < 0 || p_a > 1
	error('p_a must be a probability, so 0 <= p_a <= 1 !');
end

if mod(k_init,2) || k_init==0
	error('k must be pair and nonzero !');
end

if mod(N,2) && N-k_init < 1
	error('k too large');
end

if ~mod(N,2) && N-k_init < 2
	error('k too large');
end

if nargin ~= 4
	quiet = 0;
end

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

% step 1 : generate regular 1D-lattice (upper triangle part of A only -> reduces work)
A = logical(sparse(N,N));

for k=1:k_init/2
	A = A | spdiags(ones(N,1),k,N,N); A = A | spdiags(ones(N,1),(N-k),N,N);
end

% step 2 : add in total n*k_0/2*p_a
[i,j] = find(A); added_shortcuts_counter = 0;

for curr=1:length(i)
	
	if rand <= p_a       % go ahead, add edge !
		added_shortcuts_counter = added_shortcuts_counter+1;
		
		% now try to find a spot for the new egde ...
		j_attempt = randperm(N);  % get a random permuation for the column indices
		l = 1;%    ... which is nonoccupied   AND  not on the main diagonal
		while A(i(curr),j_attempt(l)) || A(j_attempt(l),i(curr)) ...
				|| ( j_attempt(l) == i(curr) )
			l = l+1;
		end

		% found candidate -> new one
		if i(curr) > j_attempt(l) % edge would end up in low triangle part -> "transpose"
			A(j_attempt(l),i(curr)) = true;
		else
			A(i(curr),j_attempt(l)) = true;
		end

	end
end

% create full adjacency matrix by adding the transposed of the (up to now) upper triangle
A = A | A';

if added_shortcuts_counter
	reglatt = false;
else
	reglatt = true;
end

if ~quiet
	disp([ ...
		sprintf('Small-World-Network2 of %i nodes and %i edges created',N,nnz(A)/2) ...
		sprintf('\nusing k_init = %i and p_a = %f.',k_init,p_a) ...
		sprintf('  %i shortcuts added.',added_shortcuts_counter)]);
end