tsp.java

A program to demonstrate the optimization process of ant colony optimization for the traveling salem

  public boolean isSymmetric ()
  { return this.sym; }

  public double  getDist     (int i, int j)
  { return this.dists[i][j]; }

  public void    setDist     (int i, int j, double dist)
  { this.dists[i][j] = this.dists[j][i] = dist; this.euclid = false; }

  public void    setDistAsym (int i, int j, double dist)
  { this.dists[i][j] = dist; this.sym = false;  this.euclid = false; }

  /*------------------------------------------------------------------*/

  public int[] getTour () { return this.tour; }

  public void  setTour (int[] tour)
  {                             /* --- set a (best) tour */
    if (this.tour == null)      /* create a tour if necessary */
      this.tour = new int[this.size];
    System.arraycopy(tour, 0, this.tour, 0, this.size);
  }  /* setTour() */            /* copy the given tour */

  /*------------------------------------------------------------------*/

  public String toString ()
  {                             /* --- create a string description */
    int          i, k;          /* loop variables */
    StringBuffer s;             /* created string description */

    s = new StringBuffer("TSP = {\n");
    s.append("  vertices = {"); /* there are always vertices */
    s.append("\n    (" +this.xs[0] +", " +this.ys[0] +")");
    for (i = 1; i < this.size; i++)
      s.append(",\n    (" +this.xs[i] +", " +this.ys[i] +")");
    s.append("\n  };\n");       /* list the vertices */
    if (!this.euclid) {         /* if the distances are not Euclidean */
      s.append("  distances = {");
      for (i = 0; i < this.size; i++) {
        if (i > 0) s.append(",");
        s.append("\n    { " +this.dists[i][0]);
        for (k = 1; k < this.size; k++)
          s.append(", " +this.dists[i][k]);
        s.append(" }");         /* list the pairwise distances */
      }                         /* (which are possibly asymmetric, */
      s.append("\n  };\n");     /* so that the full distance matrix */
    }                           /* may be needed) */
    if (this.tour != null) {    /* if a (best) tour is known */
      s.append("  tour = {\n    " +this.tour[0]);
      for (i = 1; i < this.size; i++)
        s.append(", " +this.tour[i]);
      s.append("\n  };\n");     /* list the vertices of the tour */
    }
    s.append("};\n");           /* terminate the description */
    return s.toString();        /* return the created string */
  }  /* toString() */

  /*------------------------------------------------------------------*/

  public TSP (Scanner s) throws IOException
  {                             /* --- read a traveling salesman p. */
    this();                     /* initialize the variables */
    int    i, k;                /* loop variables */
    double x, y;                /* buffers for coordinates */

    /* --- read vertices --- */
    s.getID("TSP");             /* check for keyword 'TSP' */
    s.getChar('=');             /* check for a '=' */
    s.getChar('{');             /* check for a '{' */
    s.getID("vertices");        /* check for keyword 'vertices' */
    s.getChar('=');             /* check for a '=' */
    s.getChar('{');             /* check for a '{' */
    if (s.nextToken() == '}')   /* if the list is empty, abort */
      throw new IOException("no vertices in TSP");
    s.pushBack();               /* push back already read token */
    do {                        /* vertex read loop */
      s.getChar('(');           /* check for a '(' */
      s.getNumber();            /* get the x-coordinate */
      x = Double.parseDouble(s.value);
      s.getChar(',');           /* check for a ',' */
      s.getNumber();            /* get the y-coordinate */
      y = Double.parseDouble(s.value);
      s.getChar(')');           /* check for a ')' */
      if (this.size >= this.xs.length)
        this.resize(-1);        /* resize the coord. vectors if nec. */
      this.xs[this.size  ] = x; /* store the coordinates */
      this.ys[this.size++] = y; /* of the new vertex */
    } while (s.nextToken() == ',');
    s.pushBack();               /* push back last token */
    s.getChar('}');             /* check for a '}' */
    s.getChar(';');             /* check for a ';' */
    if (this.size < this.xs.length)
      this.resize(this.size);   /* shrink coord. vectors if possible */

    /* --- read distances --- */
    if ((s.nextToken() != Scanner.T_ID)
    ||  !s.value.equals("distances")) {
      this.makeDists(true);     /* calculate distances if necessary */
      s.pushBack(); }           /* (symmetric, Euclidean distances) */
    else {                      /* if distances are given */
      s.getChar('=');           /* check for a '=' */
      s.getChar('{');           /* check for a '{' */
      this.dists = new double[this.size][this.size];
      for (i = 0; i < this.size; i++) {
        if (i > 0) s.getChar(',');
        s.getChar('{');         /* check for a '{' */
        for (k = 0; k < this.size; k++) {
          if (k > 0) s.getChar(',');
          s.getNumber();        /* check for a number */
          this.dists[i][k] = Double.parseDouble(s.value);
        }                       /* store the distance */
        s.getChar('}');         /* check for a '}' */
      }
      this.euclid = false;      /* distances were read */
      s.getChar('}');           /* check for a '}' */
      s.getChar(';');           /* check for a ';' */
      this.sym = true;          /* default: symmetric distances */
      for (i = this.size; (--i >= 0) && this.sym; ) {
        for (k = i; --k >= 0; )
          if (this.dists[i][k] != this.dists[k][i]) {
            this.sym = false; break; }
      }                         /* check for symmetric distances */
    }                           /* and set flag accordingly */

    /* --- read tour --- */
    if ((s.nextToken() != Scanner.T_ID)
    ||  !s.value.equals("tour"))
      s.pushBack();             /* check whether a tour is known */
    else {                      /* if there is a tour */
      s.getChar('=');           /* check for a '=' */
      s.getChar('{');           /* check for a '{' */
      for (i = 0; i < this.size; i++) {
        if (i > 0) s.getChar(',');
        s.getNumber();          /* check for a number */
        this.tour[i] = Integer.parseInt(s.value);
      }                         /* store the vertex index */
      s.getChar('}');           /* check for a '}' */
      s.getChar(';');           /* check for a ';' */
    }

    s.getChar('}');             /* check for a '}' */
    s.getChar(';');             /* check for a ';' */
  }  /* TSP() */

  /*------------------------------------------------------------------*/

  public TSP (String desc)    throws IOException
  { this(new Scanner(desc)); }

  public TSP (InputStream in) throws IOException
  { this(new Scanner(in)); }

  /*------------------------------------------------------------------*/

  public static void main (String args[])
  {                             /* --- main function for testing */
    int    size;                /* number of vertices */
    double scale = 1.0;         /* scaling factor */
    long   seed;                /* seed value for random numbers */
    TSP    tsp;                 /* created random TSP */

    if (args.length <= 0) {     /* if no file name is given */
      System.err.println("usage: TSP <vertcnt> [<scale>] [<seed>]");
      return;                   /* print a usage message */
    }                           /* and abort the program */
    seed = System.currentTimeMillis();
    size = Integer.parseInt(args[0]);
    if (args.length > 1) scale = Double.parseDouble(args[1]);
    if (args.length > 2) seed  = Integer.parseInt(args[2]);
    tsp = new TSP(size, new Random(seed));
    tsp.transform(scale,0,0);   /* create a TSP and scale it */
    System.out.print(tsp);      /* print the created TSP */
  }  /* main() */

}  /* class TSP */