function [ c , k0count ] = cc( A )
%CC  Calculates clustering coefficient
%
%   CC(A) returns the clustering coefficient, as defined 
%       by Watts & Strogatz.
%
%       Note: A MUST be undirected ! isolated nodes get 
%       c_i = 0 ; nodes with degree 1 get c_i = 1
%
%  Last change:  10/2/2005 - Florian Knorn

if nargin ~= 1
    error('Please input adjacency matrix !');
else
	n = size(A,1);
	if n ~= size(A,2)
        error('Please input SQUARE matrix !');
	end
	if nnz(A-A')
		error('Algorithm only designed for undirected graphs !');
	end
end

N = size(A,1); c=[]; k0count = 0; k1count = 0;

if N <= 3000 % use faster method using A^3
	ti = diag((double(A))^3)/2; % get all diag entries (no. triang)
	ki = sum(A,2); % get all rowsums (no. neighbors)

	k0 = find(ki==0);	k1 = find(ki==1); % find ki = 0 and ki = 1
	k0count = length(k0); k1count = length(k1); % count them

	ni = ki.*(ki-1)/2; clear ki; % calc no. possible edges b/w neighb.

	useme = find(ni>0); % find all non-zero ni's (prevent div. by 0)
	c = full(mean(ti(useme)./ni(useme))); % calc the actual mean

else % use slower, but less memory consuming method
	
	% for each of the N nodes:
	for i = 1:N
		% step 1: find immediate neighbors of node i:
		nb = find(A(i,:)); % N_i
		nnb = length(nb); % |N_i| = k_i

		if nnb == 0 % if k_i = 0 or 1 -> cc concept not applicable
			k0count = k0count + 1; c(i) = NaN; continue
		elseif nnb == 1
			k1count = k1count + 1; c(i) = NaN; continue
		end

		% step 2: count egdes amongst the neighbors of node i
		edgecount = 0;
		for j = 1:nnb
			for k = j+1:nnb % symmetry saves work: k > j
				if A(nb(j),nb(k))
					edgecount = edgecount + 1;
				end
			end

		end

		% step 3: c_i = existant_edges / possible_edges between neighbors
		c(i) = 2*edgecount / (nnb*(nnb-1));

	end

	% finish by calculating average over all non-NaNs
	if sum(isnan(c))~=length(c)
		c = mean( c(find(~isnan(c))) );
	else
		c = 0;
	end
	%
	% if k0count || k1count
	% 	disp([sprintf('There have been %i nodes with degree 0',k0count) ...
	% 		sprintf(', and %i nodes with degree 1',k1count)]);
end