function graph_dist_pairing_greedy_test ( )

%*****************************************************************************80
%
%% graph_dist_pairing_greedy_test() tests graph_dist_pairing_greedy().
%
%  Discussion:
%
%    Random data is used in setting up the problem.
%
%  Licensing:
%
%    This code is distributed under the MIT license. 
%
%  Modified:
%
%    06 November 2024
%
%  Author:
%
%    John Burkardt
%
  nnode = 15;
  nnodeh = 7;
%
%  IDO just tells us if this is the first or later trials.
%
  ido = 1;
%
%  Set the maximum number of iterations.
%
  maxit = 10;
%
%  Set the range of the X and Y coordinates.
%
  xhi = 10.0;
  xlo = 0.0;
  yhi = 5.0;
  ylo = 3.0;
%
%  Set the relative tolerance for the stepwise distance decrease.
%
  tol = 0.05;
%
%  Say hello.
%
  fprintf ( 1, '\n' );
  fprintf ( 1, 'graph_dist_pairing_greedy_test():\n' );
  fprintf ( 1, '  graph_dist_pairing_greedy() tries to minimize the total\n' );
  fprintf ( 1, '  distance in a pairing of black and red nodes.\n' );
  fprintf ( 1, '\n' );
  fprintf ( 1, '  Try to find a pairing of two sets of nodes\n' );
  fprintf ( 1, '  with a low discrepancy.\n' );
  fprintf ( 1, '\n' );
  fprintf ( 1, '  Relative tolerance for step decrease = %g\n', tol );
  fprintf ( 1, '  Maximum number of steps = %d\n', maxit );
  fprintf ( 1, '  X range is %g to %g\n', xlo, xhi );
  fprintf ( 1, '  Y range is %g to %g\n', ylo, yhi );
%
%  Make an arbitrary pairing of the nodes.
%
  for indx = 1 : nnode
    nodeb(indx) = indx;
    noder(indx) = indx;
  end
%
%  Make up a random set of X, Y coordinates for the nodes.
%
  xb = xlo + ( xhi - xlo ) * rand ( nnode, 1 );
  xr = xlo + ( xhi - xlo ) * rand ( nnode, 1 );
  yb = ylo + ( yhi - ylo ) * rand ( nnode, 1 );
  yr = ylo + ( yhi - ylo ) * rand ( nnode, 1 );
%
%  We will jump back here if we restart with a permuted NODER.
%
  for ido = 1 : 2
 
    fprintf ( 1, '\n' );
    fprintf ( 1, 'Initial black node coordinates:\n' );
    fprintf ( 1, '\n' );
    fprintf ( 1, '    I   Black   X             Y\n' );
    fprintf ( 1, '\n' );
 
    for indx = 1 : nnode
      fprintf ( 1, '%8d  %8d  %g  %g\n', indx, nodeb(indx), xb(indx), yb(indx) );
    end
 
    fprintf ( 1, '\n' );
    fprintf ( 1, 'Initial red node coordinates:\n' );
    fprintf ( 1, '\n' );
    fprintf ( 1, '    I    Red    X             Y\n' );
    fprintf ( 1, '\n' );
 
    for indx = 1 : nnode
      fprintf ( 1, '%8d  %8d  %g  %g\n', indx, noder(indx), xr(indx), yr(indx) );
    end
 
    fprintf ( 1, '\n' );
    fprintf ( 1, 'Initial pairing of nodes:\n' );
    fprintf ( 1, '\n' );
    fprintf ( 1, '    I   Black  Red    Distance\n' );
    fprintf ( 1, '\n' );
 
    for indx = 1 : nnode
      nodeb1 = nodeb(indx);
      noder1 = noder(indx);
      dist = sqrt ( ( xb(nodeb1) - xr(noder1) )^2 + ...
                    ( yb(nodeb1) - yr(noder1) )^2 );

      fprintf ( 1, '  %d  %d  %d  %g\n', indx, nodeb1, noder1, dist );
    end
 
    total = 0.0;
    for indx = 1 : nnode
      nodeb1 = nodeb(indx);
      noder1 = noder(indx);
      total = total + sqrt ( ( xb(nodeb1) - xr(noder1) )^2 ...
                           + ( yb(nodeb1) - yr(noder1) )^2 );
    end
 
    fprintf ( 1, '\n' );
    fprintf ( 1, 'Total discrepancy of initial pairing = %g\n', total );
%
%  Seek a better pairing.
%
    noder = graph_dist_pairing_greedy ( maxit, nodeb, noder, nnode, ...
      tol, xb, xr, yb, yr );
 
    fprintf ( 1, '\n' );
    fprintf ( 1, 'Final black node coordinates:\n' );
    fprintf ( 1, '\n' );
    fprintf ( 1, '    I   Black   X             Y\n' );
    fprintf ( 1, '\n' );
 
    for indx = 1 : nnode
      fprintf ( 1, '%8d  %8d  %g  %g\n', indx, nodeb(indx), xb(indx), yb(indx) );
    end
 
    fprintf ( 1, '\n' );
    fprintf ( 1, 'Final red node coordinates:\n' );
    fprintf ( 1, '\n' );
    fprintf ( 1, '    I    Red    X             Y\n' );
    fprintf ( 1, '\n' );
 
    for indx = 1 : nnode
      fprintf ( 1, '%8d  %8d  %g  %g\n', indx, noder(indx), xr(indx), yr(indx) );
    end
 
    fprintf ( 1, '\n' );
    fprintf ( 1, 'Final pairing of nodes:\n' );
    fprintf ( 1, '\n' );
    fprintf ( 1, '    I   Black  Red    Distance\n' );
    fprintf ( 1, '\n' );
 
    for indx = 1 : nnode

      nodeb1 = nodeb(indx);
      noder1 = noder(indx);

      dist = sqrt ( ( xb(nodeb1) - xr(noder1) )^2 ...
                  + ( yb(nodeb1) - yr(noder1) )^2 );

      fprintf ( 1, '  %d  %d  %d  %g\n', indx, nodeb1, noder1, dist );

    end
 
    total = 0.0;
    for indx = 1 : nnode
      nodeb1 = nodeb(indx);
      noder1 = noder(indx);
      dist = sqrt ( ( xb(nodeb1) - xr(noder1) )^2 ...
                  + ( yb(nodeb1) - yr(noder1) )^2 );

      total = total + dist;
 
    end
 
    fprintf ( 1, '\n' );
    fprintf ( 1, '  Total discrepancy of final pairing = %g\n', total );
%
%  On the second try, reverse the ordering of the red nodes.
%  Any random permutation would be worth trying.
%
    if ( ido == 1 )
 
      noder = noder(nnode:-1:1);
 
      fprintf ( 1, '\n' );
      fprintf ( 1, '  Reversing NODER!\n' );
 
    end

  end
 
  return
end

