allpair_dijkstra.m

best routing protocol

function [dist, nexthop] = allpair_dijkstra(neighbor_dist, dests, ...
					    use_cache, cache_fn)
if nargin<1
  error('wrong usage')
end
neighbor_dist = double(neighbor_dist);
[x y] = size(neighbor_dist);
if x~=y
  error('neighbor_dist is not a square matrix');
end

n = length(neighbor_dist);
if nargin<2
  dests = 1:n;
end
if nargin<3
  use_cache = 1;
end

if nargin<4
  cache_fn = 'dijkstra-cache.mat';
end

debug = 1;
saved_dist = neighbor_dist;
saved_dests = dests;
if use_cache
  try
    clear dests;
    clear neighbor_dist;
    load(cache_fn);
    if neighbor_dist==saved_dist
      if issame(saved_dests, dests)
	if debug
	  fprintf('loaded from cached result\n');
	end
	return
      elseif issame(dests, 1:n)
	dist = dist(:,saved_dests);
	nexthop = nexthop(:, saved_dests);
	if debug
	  fprintf('loaded from partial cached result\n');
	end
	return
      end
    end
  catch
    %do nothing
    fprintf('%s\n',lasterr);
  end
  if debug
    fprintf('cache %s is no good\n', cache_fn);
  end
else
  if debug
    fprintf('skip cache\n');
  end
end

neighbor_dist = saved_dist;
dests = saved_dests;
clear dist nexthop saved_dests;

% fill Inf with 0 and convert to sparse matrix
if issparse(neighbor_dist)
  if debug
    fprintf('already a sparse matrix\n');
  end
  S = neighbor_dist;
else
  if debug
    fprintf('coverting to a sparse matrix\n');
  end
  S = neighbor_dist;
  tmp = find(S==Inf);
  S(find(S==Inf))=zeros(length(tmp),1);
  S = sparse(S);
  if debug
    fprintf('finished coverting to a sparse matrix\n');
  end
end
%dist = zeros(n,n);
start_t = clock;
old_t = clock;
old_i = 1;
count=1;
for i=dests
  new_t = clock;
  if etime(new_t,old_t) >10
    fprintf('dijkstra: progress %.1f%%. ETA %.1f secs\n', ...
    (count-1)*100/n,(etime(new_t,old_t))/(count-old_i)*(n-i+1));
    old_t = new_t;
    old_i = count;
  end
  
  [s_dist, s_pre,s_nexthop] = dijkstra(S,i);
  dist(:,count) = s_dist;
  %nexthop(i,:) = s_nexthop';
  nexthop(:,count) = s_pre;
  count = count+1;
end
if use_cache
  save(cache_fn, 'neighbor_dist', 'dist','nexthop', 'dests');
end
function b = issame(v1, v2)
if length(v1)~=length(v2)
  b = 0;
else
  b = prod(double(v1==v2));
end