function tsp_nearest_test ( )

%*****************************************************************************80
%
%% tsp_nearest_test() tests tsp_nearest().
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    06 June 2026
%
%  Author:
%
%    John Burkardt
%
  addpath ( '../tsp_nearest' );
  addpath ( '../tsp_display' );

  timestamp ( );
  fprintf ( 1, '\n' );
  fprintf ( 1, 'tsp_nearest_test():\n' );
  fprintf ( 1, '  MATLAB/Octave version %s\n', version ( ) );
  fprintf ( 1, '  Test tsp_nearest(), which seeks a shortest round trip\n' );
  fprintf ( 1, '  for the traveling salesperson problem, by starting at\n' );
  fprintf ( 1, '  an arbitrary city, and always moving next to the nearest\n' );
  fprintf ( 1, '  unvisited city.\n' );
%
%  Define the XY coordinates of the cities.
%
  x = [ ...
    6734, 1453; ...
    2233,   10; ...
    5530, 1424; ...
     401,  841; ...
    3082, 1644; ...
    7608, 4458; ...
    7573, 3716; ...
    7265, 1268; ...
    6898, 1885; ...
    1112, 2049; ...
    5468, 2606; ...
    5989, 2873; ...
    4706, 2674; ...
    4612, 2035; ...
    6347, 2683; ...
    6107,  669; ...
    7611, 5184; ...
    7462, 3590; ...
    7732, 4723; ...
    5900, 3561; ...
    4483, 3369; ...
    6101, 1110; ...
    5199, 2182; ...
    1633, 2809; ...
    4307, 2322; ...
     675, 1006; ...
    7555, 4819; ...
    7541, 3981; ...
    3177,  756; ...
    7352, 4506; ...
    7545, 2801; ...
    3245, 3305; ...
    6426, 3173; ...
    4608, 1198; ...
      23, 2216; ...
    7248, 3779; ...
    7762, 4595; ...
    7392, 2244; ...
    3484, 2829; ...
    6271, 2135; ...
    4985,  140; ...
    1916, 1569; ...
    7280, 4899; ...
    7509, 3239; ...
      10, 2676; ...
    6807, 2993; ...
    5185, 3258; ...
    3023, 1942 ];

  n = size ( x, 1 );
%
%  Find the best nearest neighbor round trip.
%
  [ order, cost ] = tsp_nearest ( x );
%
%  Report.
%
  fprintf ( 1, '\n' );
  fprintf ( 1, '  The best itinerary found:\n' );
  fprintf ( 1, '\n' );
  fprintf ( 1, '  Step  From  To        Distance\n' );
  fprintf ( 1, '\n' );
  for from = 1 : n
    i1 = order(from);
    to = mod ( from, n ) + 1;
    i2 = order(to);
    d = norm ( x(i1,:) - x(i2,:) );
    fprintf ( 1, '  %4d    %2d  %2d  %14.6g\n', from, i1, i2, d );
  end
  fprintf ( 1, '  ----    --  --  --------------\n' );
  fprintf ( 1, '  cost:           %14.6g\n', cost );
%
%  Display final path.
%
  x2 = zeros ( n + 1, 2 );

  for i2 = 1 : n + 1
    if ( i2 <= n )
      i = order(i2);
    else
      i = order(1);
    end
    x2(i2,1:2) = x(i,1:2);
  end
%
%  Send the data to the plotter.
%
  prefix = 'tsp_nearest_test';
  tsp_display ( prefix, n + 1, x2 );
%
%  Terminate.
%
  fprintf ( 1, '\n' );
  fprintf ( 1, 'tsp_nearest_test():\n' );
  fprintf ( 1, '  Normal end of execution.\n' );
  fprintf ( 1, '\n' );
  timestamp ( );

  rmpath ( '../tsp_display' );
  rmpath ( '../tsp_nearest' );

  return
end
function timestamp ( )

%*****************************************************************************80
%
%% timestamp() prints the current YMDHMS date as a timestamp.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    14 February 2003
%
%  Author:
%
%    John Burkardt
%
  t = now;
  c = datevec ( t );
  s = datestr ( c, 0 );
  fprintf ( 1, '%s\n', s );

  return
end

