% apspdemo.m
# some benchmarking with Floyd Warshall
clear all

# make a random undirected graph
n = 100; # graph order
adj = rand(n,n) > 0.98;
adj = (adj ~= adj'); # symmetric, with zero diagonal
assert (all (adj(:) == adj'(:)))

# initialize distance matrices
dist1 = inf (n,n);
dist1 (1:(n+1):n^2) = 0;
dist1 (adj) = 1;
dist2 = dist3 = dist1;

# naive method
tic
for k = 1:n
  for i = 1:n
    for j = 1:n
      dist1(i,j) = min (dist1(i,j), dist1(i,k) + dist1(k,j));
    end
  end
end
time1_naive = toc

# vectorized method
tic
for k = 1:n
  for i = 1:n
    dist2(i,:) = min (dist2(i,:), dist2(i,k) + dist2(k,:));
  end
end
time2_vectorized = toc

# broadcast method
tic
for k = 1:n
  dist3 = min (dist3, dist3(:,k) + dist3(k,:));
end
time3_broadcast = toc

# check that all three distance matrices are the same
assert (all (dist1(:) == dist2(:)))
assert (all (dist1(:) == dist3(:)))
assert (all (dist2(:) == dist3(:)))

clear i j k
whos

