/* nag_mip_tsp_simann (h03bbc) Example Program.
 *
 * Copyright 2014 Numerical Algorithms Group.
 *
 * Mark 25, 2014.
 */

#include <nag.h>
#include <stdio.h>
#include <string.h>
#include <nag_stdlib.h>
#include <nagg05.h>
#include <nagh03.h>

int main(void)
{
  /* Scalars */
  Integer     exit_status = 0;
  Integer     subid = 53, lseed = 4, lstate;
  Integer     i, j, l, nc, n_i, icol, col_s, col_f, nrows, tmode;
  double      bound, targc, cost;
  /* Arrays */
  Integer     seed[] = { 304950,889934,209094,23423990 };
  double      alg_stats[6];
  Integer     *state = 0, *path = 0;
  double      *dm = 0;
  char        **cities = 0;
  /* Nag Types */
  Nag_BaseRNG genid = Nag_WichmannHill_I;
  NagError    fail;

  INIT_FAIL(fail);

  printf("nag_mip_tsp_simann (h03bbc) Example Program Results\n\n");

  /* Read number of cities from data file */
  scanf(" %*[^\n]"); /* Skip heading */
  scanf("%ld %*[^\n]", &nc);
  /* Get the length of the state array for random number generation */
  lstate = -1;
  nag_rand_init_repeatable(genid, subid, seed, lseed, state, &lstate, &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_rand_init_repeatable (g05kfc).\n%s\n",
           fail.message);
    exit_status = 1;
    goto END;
  }

  /* Allocate arrays using nc and lstate*/
  if (!(state = NAG_ALLOC(lstate, Integer)) ||
      !(path  = NAG_ALLOC(nc, Integer)) ||
      !(dm    = NAG_ALLOC(nc*nc, double)) ||
      !(cities = NAG_ALLOC(nc, char *)))
    {
      printf("Allocation failure\n");
      exit_status = 2;
      goto END;
    }

  /* Read distance matrix 10 columns at a time */
  /* Define DM for reading distance matrix from file */
#define DM(I, J) dm[(J-1)*nc + I - 1]
  for (icol = 2; icol <= nc; icol=icol+10) {
    /* Skip a line */
    scanf(" %ld %*[^\n]", &n_i);
    col_f = MIN(icol+9,nc);
    nrows = col_f - 1;
    for (i = 1; i <= nrows; i++) {
      /* Skip row number */
      scanf("%ld",&n_i); 
      col_s = MAX(i+1,icol);
      for (j = col_s; j <= col_f; j++) {
        scanf("%lf",&DM(i,j)); 
      }
      scanf("%*[^\n] ");
    }
  }

  /* Read city names */
  for (i = 0; i < nc; i++) {
    if (!(cities[i] = NAG_ALLOC(20, char)))
      {
        printf("Allocation failure\n");
        exit_status = 3;
        goto END;
      }
    scanf("%ld %19s%*[^\n] ", &n_i, cities[i]);
  }

  /* Initialise the random number generator to a repeatable sequence */
  nag_rand_init_repeatable(genid, subid, seed, lseed, state, &lstate, &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_rand_init_repeatable (g05kfc).\n%s\n", 
           fail.message);
    exit_status = 4;
    goto END;
  }

  /* Calculate a lower bound internally and try to find lowest cost path. */
  bound = -1.0;
  targc = -1.0;

  /* Find low cost return path through all cities. */
  nag_mip_tsp_simann(nc,dm,bound,targc,path,&cost,&tmode,alg_stats,state,&fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_mip_tsp_simann (h03bbc).\n%s\n", 
           fail.message);
    exit_status = 5;
    goto END;
  }

  printf("Initial search end cost: %12.2f\n", alg_stats[2]);
  printf("Search best cost       : %12.2f\n", alg_stats[3]);
  printf("Initial temperature    : %12.2f\n", alg_stats[4]);
  printf("Lower bound            : %12.2f\n", alg_stats[5]);
  printf("Termination mode       : %12ld\n\n", tmode);
  printf("Final cost             : %12.2f\n\n", cost);
  printf("Final path:\n");
  printf(" %s --> %s\n", cities[path[0]-1], cities[path[1]-1]);
  l = strlen(cities[path[0]-1]);
  for (i = 2; i <= nc-1; i++) {
    printf(" ");
    for (j = 0; j < l; j++) printf(" ");
    printf(" --> %s\n", cities[path[i]-1]);
  }
  printf(" ");
  for (j = 0; j < l; j++) printf(" ");
  printf(" --> %s\n", cities[path[0]-1]);

 END:
  NAG_FREE(dm);
  NAG_FREE(state);
  NAG_FREE(path);
  for (i = 0; i < nc; i++) {
    NAG_FREE(cities[i]);
  }
  NAG_FREE(cities);

  return exit_status;
}