matrix_reader.java

用于求解TSP(Traveling salesman problem

/**
 * Description: reads the problem data in TSPLIB format
 *
   The following description of the file format is extracted from the TSPLIB
   documentation (by K. Helsgaun, LKH 1.3, July 2002).


   EDGE-WEIGHT_FORMAT : <string>
   Describes the format of the edge weights if they ar given explicitely. The values
   are
   FULL_MATRIX          Weights are given by a full matrix
   UPPER_ROW            Upper triangular matrix (row-wise without diagonal entries)
   LOWER_ROW            Lower triangular matrix (row-wise without diagonal entries)
   UPPER_DIAG_ROW       Upper triangular matrix (row-wise including diagonal entries)
   LOWER_DIAG_ROW       Lower triangular matrix (row-wise including diagonal entries)
   UPPER_COL            Upper triangular matrix (column-wise without diagonal entries)
   LOWER_COL            Lower triangular matrix (column-wise without diagonal entries)
   UPPER_DIAG_COL       Upper triangular matrix (column-wise including diagonal entries)
   LOWER_DIAG_COL       Lower triangular matrix (colum-wise including diagonal entries)

 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    Apr 6, 2005     [e-mail]
 *
 * @ Reference:
 *  [1] Program's name: acotsp
 *  Ant Colony Optimization algorithms (AS, ACS, EAS, RAS, MMAS, BWAS) for the
 *  symmetric TSP, Copyright (C) 2004  Thomas Stuetzle
 *  Email: stuetzle no@spam informatik.tu-darmstadt.de
 *  [2] TSPLIB, Gerhard Reinelt, Gerhard.Reinelt{at}informatik.uni-heidelberg.de
 */

package implement.TSP.infoIO;

import Global.methods.*;

public class Matrix_Reader {


  public static void readTRIContent(int[][] dataMatrix, boolean isLowTRI, boolean hasDiagonal, String[] lines, int startIndex, int endIndex) throws Exception {
    int ri = 0, rj = 0;
    int bias = 0;
    int nodeNumber = dataMatrix.length;
    if (!hasDiagonal) {
      bias=1;
    }
    if (isLowTRI) {
      ri += bias;
    } else {
      rj += bias;
    }

    for (int i=startIndex; i<endIndex; i++) {
      String[] lineInfos = GlobalString.tokenize(lines[i], " \t");
      for (int j=0; j<lineInfos.length; j++) {
        dataMatrix[ri][rj] = new Double(lineInfos[j]).intValue();
        if (ri!=rj) {
          dataMatrix[rj][ri] = dataMatrix[ri][rj];
        }
        rj ++;
        if (isLowTRI) {
          if (rj>ri-bias) {
            ri ++;
            rj = 0;
          }
        } else {
          if (rj >= nodeNumber) {
            ri++;
            rj = ri + bias;
          }
        }
      }
    }
  }

  public static void readFullMatrix(int[][] dataMatrix, String[] lines, int startIndex, int endIndex) throws Exception {
    int ri = 0, rj = 0;
    for (int i=startIndex; i<endIndex; i++) {
      String[] lineInfos = GlobalString.tokenize(lines[i], " \t");
      for (int j=0; j<lineInfos.length; j++) {
        dataMatrix[ri][rj] = new Double(lineInfos[j]).intValue();
        rj ++;
        if (rj>=dataMatrix[ri].length) {
          rj = 0;
          ri ++;
        }
      }
    }
  }
}