function [ls,avpath]=pathlength(A)

%Calculates the longest shortest path length (diameter) & the average path length of a network.

%Usage: [ls,avpath]=pathlength(A), where A is an adjacency matrix.

%This version counts the steps taken for a node to "return to itself".

%prealloc B & stuff to make faster!

N=length(A);

i=1;

B=sparse([],[],[],N,N,N^2);

L=0;

B=B+A^i;

M(i)=nnz(B); %-nnz(diag(B)); %to account for self-connections & ignore

while M(i)>L %fill-in increases

   L=M(i);

   i=i+1;

   B=B+A^i;

   M(i)=nnz(B); %-nnz(diag(B));

end

ls=i-1; %longestshortest

avpath=sum((1:ls).*[M(1) M(2:ls)-M(1:ls-1)])/N^2; %change denom to N(N-1) if diag used