% PATHEXCT: Determines the shortest (and optionally longest) paths among a small set 
%           of points by brute force, by determining the path length for all possible 
%           permutations.  A starting point must be specified, and an optional end point 
%           may be specified; if they are equal, the resulting path is a Hamiltonian circuit.  
%           Interpoint distances are given by a square distance matrix (having zeros on 
%           the diagonal), which need be neither symmetric nor complete.  Incomplete links 
%           can be specified by arbitrarily large values.
%
%           The maximum number of points feasibly examined by brute force is 8-10.
%
%     Usage: [minpath,minlen,maxpath,maxlen] = pathexct(dist,sp,{ep})
%
%           dist =    [n x n] distance matrix.
%           sp =      index of the starting point.
%           ep =      optional index of the end point.
%           -------------------------------------------------------------------------------
%           minpath = [n x 1] vector of indices of points in the sequence connected; if the 
%                       starting point is also the end point, its value is not repeated.
%           minlen =  path length of the shortest path (including the final link for a 
%                       Hamiltonian circuit).
%           maxpath = comparable path of maximum length.
%           maxlen =  path length of the longest path.
%

% RE Strauss, 7/6/98

function [minpath,minlen,maxpath,maxlen] = pathexct(dist,sp,ep)
  if (nargin < 3) ep = []; end;

  [n,m] = size(dist);

  if (isempty(ep))
    ep = 0;
  end;

  m = n-1;                                % Number of values to be permuted
  if (ep & ep~=sp)
    m = m-1;
  end;
  nperm = prod(2:m);                      % Number of possible permutations

  minlen = 1/eps;
  maxlen = eps;

  perm = 1:m;
  minpath = perm;
  maxpath = perm;

  for it = 1:nperm
    p = perm;                               % Current permuation

    i = (p >= sp);                            % Adjust indices to allow for start pt
    p(i) = p(i)+1;

    if (ep>0 & ep~=sp)                        % Adjust to allow for end pt
      i = (p >= ep);
      p(i) = p(i)+1;
      p = [sp p ep];                          % Put start & end pts at beginning and end
    else                                      %   of list
      p = [sp p];
    end;

    len = 0;  
    for i = 1:length(p)-1                     % Get path length
      len = len + dist(p(i),p(i+1));
    end;

    if (len < minlen)
      minlen = len;
      minpath = p;
    end;

    if (len > maxlen)
      maxlen = len;
      maxpath = p;
    end;

    perm = permnext(perm);                  % Next permutation
  end;

  return;

