/* nag_mip_tsp_simann (h03bbc) Example Program.
 *
 * Copyright 2020 Numerical Algorithms Group.
 *
 * Mark 27.1, 2020.
 */

#include <nag.h>
#include <stdio.h>
#include <string.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("%" NAG_IFMT " %*[^\n]", &nc);
  /* Get the length of the state array for random number generation */
  lstate = -1;
  nag_rand_init_repeat(genid, subid, seed, lseed, state, &lstate, &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_rand_init_repeat (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(" %" NAG_IFMT " %*[^\n]", &n_i);
    col_f = MIN(icol + 9, nc);
    nrows = col_f - 1;
    for (i = 1; i <= nrows; i++) {
      /* Skip row number */
      scanf("%" NAG_IFMT "", &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("%" NAG_IFMT " %19s%*[^\n] ", &n_i, cities[i]);
  }

  /* Initialize the random number generator to a repeatable sequence */
  nag_rand_init_repeat(genid, subid, seed, lseed, state, &lstate, &fail);
  if (fail.code != NE_NOERROR) {
    printf("Error from nag_rand_init_repeat (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       : %12" NAG_IFMT "\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;
}