function [ l , ncc, slcc, d , conn] = avl( A , quiet )
%AVL  calculates the average path length
%   l = AVL(A) calculates the average path length  l  (as of the
%       average number of edges in the shorest path between every
%       pair of nodes).
%
%   [ l , ncc , slcc ] = AVL(A) additionally returns  ncc  and  slcc
%       which are number of connected components and the size of the
%       largest one (i.e. the number of nodes in it)
%
%   [ l , ncc , slcc , d , conn ] = AVL(A) additionally returns the
%       diameter  d  of the graph (i.e. the longest geodesic) as well
%       as the boolean  conn  which is true only if the graph is 
%       connected
%
%   Note: if the graph is disconnected, the average is calculated
%   only over all existing geodesics.
%
%  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 nargin ~= 2
		quiet = false;
	end
end

% some initialisation
nn = n^2; m = 0; count = []; deltannz = 42; warning off;

if issparse(A) % nice, we're dealing with sparse matricies
	A = logical(A); Asum2 = logical(speye(n)); Am = Asum2;
	while (nnz(Asum2) ~= nn) && (deltannz ~= 0) && (m <= n)
		m = m + 1; Am = logical(double(Am)*A);
		Asum1 = Asum2; Asum2 = Asum1 | Am;
		deltannz = nnz(Asum2)-nnz(Asum1); % increase of new shortest paths
		count(m) = deltannz; % store increase
	end
else % we're not dealing with matricies in the sparse format
	Asum2 = eye(n);
	while (length(find(Asum2)) ~= nn) && (deltannz ~= 0) && (m <= n)
		m = m + 1; Asum1 = Asum2; Asum2 = Asum1 + A^m;
		deltannz = length(find(Asum2)) - length(find(Asum1)); % increase of new shortest paths
		count(m) = deltannz; % store increase
	end
end

% finish calculating average path length
l = 0;
for i=1:length(count)
	l = l + count(i)*i;
end
cs = sum(count);
if cs, l = l/cs; end

% if graph is not connected, count ncc, find slcc and output warning
if (deltannz == 0) || (m == n)
	ncc = 0;
	scc = [];
	while ~isempty(Asum2)
		any1 = find(any(Asum2)); first1 = any1(1);
		ncc = ncc + 1;					% increase count of cc
		zeroz=find(Asum2(first1,:)==0); % grab zero entries ...
		scc(ncc) = size(Asum2,1) - length(zeroz); % scc = nnz(first row) = size - nnz
		Asum2 = Asum2(zeroz,zeroz);		% Asum2 = all zero-rows+columns
	end

	slcc = max(scc);
	if isempty(slcc)
		slcc = 1;
	end
	d = m-1;
	if ~quiet, disp(sprintf('Diameter of this NOT CONNECTED graph: %i',d)); end
	conn = false;
else
	ncc = 1;
	slcc = n;
	d = m;
	if ~quiet, disp(sprintf('Diameter of this graph: %i',d)); end
	conn = true;
end

warning on;