-:    0:Source:ts.c
        -:    0:Graph:ts.gcno
        -:    0:Data:ts.gcda
        -:    0:Runs:1
        -:    0:Programs:1
        -:    1:#include <alloca.h>
        -:    2:#include <stdio.h>
        -:    3:#include <math.h>
        -:    4:#include <float.h>
        -:    5:#include <stdlib.h>
        -:    6:
        -:    7:typedef struct {
        -:    8:  double x;
        -:    9:  double y;
        -:   10:} point;
        -:   11:
100181170:   12:double sqr(double x)
        -:   13:{
100181170:   14:  return x*x;
        -:   15:}
        -:   16:
 50090585:   17:double dist(point cities[], int i, int j) {
100181170:   18:  return sqrt(sqr(cities[i].x-cities[j].x)+
 50090585:   19:	      sqr(cities[i].y-cities[j].y));
        -:   20:}
        -:   21:
        1:   22:void tsp(point cities[], int tour[], int ncities)
        -:   23:{
        -:   24:  int i,j;
        1:   25:  char *visited = alloca(ncities);
        -:   26:  int ThisPt, ClosePt=0;
        -:   27:  double CloseDist;
        -:   28:  int endtour=0;
        -:   29:  
    10001:   30:  for (i=0; i<ncities; i++)
    10000:   31:    visited[i]=0;
        1:   32:  ThisPt = ncities-1;
        1:   33:  visited[ncities-1] = 1;
        1:   34:  tour[endtour++] = ncities-1;
        -:   35:  
    10001:   36:  for (i=1; i<ncities; i++) {
        -:   37:    CloseDist = DBL_MAX;
 99980001:   38:    for (j=0; j<ncities-1; j++) {
 99980001:   39:      if (!visited[j]) {
 49995000:   40:	if (dist(cities, ThisPt, j) < CloseDist) {
    85586:   41:	  CloseDist = dist(cities, ThisPt, j);
        -:   42:	  ClosePt = j;
        -:   43:	}
        -:   44:      }
        -:   45:    }
     9999:   46:    tour[endtour++] = ClosePt;
     9999:   47:    visited[ClosePt] = 1;
        -:   48:    ThisPt = ClosePt;
        -:   49:  }
        1:   50:}
        -:   51:
        1:   52:int main(int argc, char *argv[])
        -:   53:{
        -:   54:  int i, ncities;
        -:   55:  point *cities;
        -:   56:  int *tour;
        -:   57:  FILE *psfile;
        -:   58:  double sumdist = 0.0;
        -:   59:
        1:   60:  if (argc!=2) {
    #####:   61:    fprintf(stderr, "usage: %s <ncities>", argv[0]);
    #####:   62:    exit(1);
        -:   63:  }
        1:   64:  ncities = atoi(argv[1]);
        1:   65:  cities = alloca(ncities*sizeof(point));
        1:   66:  tour = alloca(ncities*sizeof(int));
    10001:   67:  for (i=0; i<ncities; i++) {
    10000:   68:    cities[i].x = ((double)(random()))/(double)(1U<<31);
    10000:   69:    cities[i].y = ((double)(random()))/(double)(1U<<31);
        -:   70:  }
        1:   71:  tsp(cities,tour,ncities);
        1:   72:  psfile = fopen("tsp.eps","w");
        1:   73:  fprintf(psfile, "%%!PS-Adobe-2.0 EPSF-1.2\n%%%%BoundingBox: 0 0 300 300\n");
        1:   74:  fprintf(psfile, "1 setlinejoin\n0 setlinewidth\n");
        2:   75:  fprintf(psfile, "%f %f moveto\n",
        2:   76:	  300.0*cities[tour[0]].x, 300.0*cities[tour[0]].y);
        1:   77:  printf("%d\n", tour[0]);
    10000:   78:  for (i=1; i<ncities; i++) {
     9999:   79:    printf("%d\n", tour[i]);
    19998:   80:    fprintf(psfile, "%f %f lineto\n",
    19998:   81:	    300.0*cities[tour[i]].x, 300.0*cities[tour[i]].y);
     9999:   82:    sumdist += dist(cities, tour[i-1], tour[i]);
        -:   83:  }
        1:   84:  fprintf(psfile,"stroke\n");
        1:   85:  printf("sumdist = %f\n", sumdist);
        1:   86:  exit(0);
        -:   87:}