realproblemiohandler.java

用于求解TSP(Traveling salesman problem

    int index = StringSearch.getStringLoc(lines, "TOUR_SECTION");
    if (index==-1) return;
    int endIndex1 = StringSearch.getStringLoc(lines, "-1");
    int endIndex2 = StringSearch.getStringLoc(lines, "EOF");
    int endIndex = lines.length;
    if (endIndex1==-1&&endIndex2==-1) {
      endIndex = lines.length;
    } else if (endIndex1==-1&&endIndex2!=-1) {
      endIndex = endIndex2;
    } else if (endIndex1!=-1&&endIndex2==-1) {
      endIndex = endIndex1;
    } else {
      endIndex = Math.min(endIndex1, endIndex2);
    }

    int tspN = -1;
    String lineContent = getSubString(lines, "DIMENSION");
    if (lineContent != null) {
      tspN = new Integer(lineContent).intValue();
    }

    int dataLines = endIndex-index-1;
    int[] tourPath;
    if (tspN==-1) {
      tourPath = new int[0];
      for (int i=index+1; i<endIndex; i++) {
        String[] lineAti = GlobalString.tokenize(lines[i], " \t");
        int[] contentAtLineI = new int[lineAti.length];
        for (int j=0; j<contentAtLineI.length; j++) {
          contentAtLineI[j] = (new Integer(lineAti[j])).intValue();
        }
        int[] currentContents = new int[tourPath.length+contentAtLineI.length];
        System.arraycopy(tourPath, 0, currentContents, 0, tourPath.length);
        System.arraycopy(contentAtLineI, 0, currentContents, tourPath.length, contentAtLineI.length);
        tourPath = currentContents;
      }
    } else {
      tourPath = new int[tspN];
      int inCount = 0;
      if (tspN != dataLines) {
        for (int i = index + 1; i < endIndex; i++) {
          String[] lineAti = GlobalString.tokenize(lines[i], " \t");
          for (int j = 0; j < lineAti.length; j++) {
            tourPath[inCount] = (new Integer(lineAti[j])).intValue();
            inCount++;
          }
        }
      }
      else {
        for (int i = index + 1; i < endIndex; i++) {
          tourPath[i - index - 1] = (new Integer(lines[i])).intValue();
        }
      }
    }
    state.getSearchState().initLocation(tourPath);
  }

  public AbsProblemData readProblem(String content) throws Exception {
    String[] lines = GlobalString.getMeaningfulLines(content);
    String lineContent = "";

    lineContent = getSubString(lines, "EDGE_WEIGHT_TYPE");
    if (lineContent!=null) {
      Abs_TSPData tspData = null;
      if (!lineContent.equalsIgnoreCase("EXPLICIT")) {
        tspData = readEUCContent(lines);
      } else {
        tspData = readExplicitContent(lines);
      }
      return new RealProblemData(tspData.getDistanceMatrix());
    }
    throw new Exception("Not a TSP TYPE in TSPLIB format!!");
  }

  private static DIR_TSPData readExplicitContent(String[] lines) throws Exception {
    String lineContent = "";

    int index = StringSearch.getStringLoc(lines, "EDGE_WEIGHT_SECTION");
    if (index==-1) {
      throw new Exception("Errors ocurred in finding EDGE_WEIGHT_SECTION from tsp file!");
    }

    int tspN = -1;
    lineContent = getSubString(lines, "DIMENSION");
    if (lineContent!=null) {
      tspN = new Integer(lineContent).intValue();
    } else {
      return null;
    }

    DIR_TSPData tspData = new DIR_TSPData(tspN);
    readGeneralContent(tspData, lines);

    lineContent = getSubString(lines, "EDGE_WEIGHT_TYPE");
    if (lineContent!=null) {
      if (!tspData.setEDGE_WEIGHT_TYPE(lineContent)) {
        throw new Exception("Unkown EDGE_WEIGHT_TYPE: "+ lineContent);
      }
    }

    int endIndex = getEndIndex(lines);
    lineContent = getSubString(lines, "EDGE_WEIGHT_FORMAT");
    if (lineContent!=null) {
      if (!tspData.setDataBlock(lineContent, lines, index+1, endIndex)) {
        throw new Exception("Unkown EDGE_WEIGHT_FORMAT: "+ lineContent);
      }
    }
    return tspData;
  }

  private static int getEndIndex(String[] lines) {
    int endIndex1 = StringSearch.getStringLoc(lines, "-1");
    int endIndex2 = StringSearch.getStringLoc(lines, "EOF");
    int endIndex = lines.length;
    if (endIndex1==-1&&endIndex2==-1) {
      endIndex = lines.length;
    } else if (endIndex1==-1&&endIndex2!=-1) {
      endIndex = endIndex2;
    } else if (endIndex1!=-1&&endIndex2==-1) {
      endIndex = endIndex1;
    } else {
      endIndex = Math.min(endIndex1, endIndex2);
    }
    return endIndex;
  }

  private static void readGeneralContent(Abs_TSPData tspData, String[] lines) throws Exception {
    String lineContent = "";

    lineContent = getSubString(lines, "TYPE");
    if (lineContent!=null) {
      tspData.setKey(lineContent);
    }

    lineContent = getSubString(lines, "NAME");
    if (lineContent!=null) {
      tspData.name = lineContent;
    }

    lineContent = getSubString(lines, "COMMENT");
    if (lineContent!=null) {
      tspData.description = lineContent;
    }
  }

  private static EUC_TSPData readEUCContent(String[] lines) throws Exception {
    EUC_TSPData tspData = new EUC_TSPData();
    readGeneralContent(tspData, lines);

    String lineContent = "";

    int index = StringSearch.getStringLoc(lines, "NODE_COORD_SECTION");
    if (index==-1) {
      throw new Exception("Errors ocurred in finding NODE_COORD_SECTION from tsp file!");
    }
    lineContent = getSubString(lines, "EDGE_WEIGHT_TYPE");
    if (lineContent!=null) {
      if (!tspData.setEDGE_WEIGHT_TYPE(lineContent)) {
        throw new Exception("Unkown EDGE_WEIGHT_TYPE: "+ lineContent);
      }
    }

    int tspN = -1;
    lineContent = getSubString(lines, "DIMENSION");
    if (lineContent!=null) {
      tspN = new Integer(lineContent).intValue();
    }

    int endIndex = getEndIndex(lines);
    if (tspN!=endIndex-index-1) {
      throw new Exception("Invalid dimension: "+tspN+"(specified)!="+(endIndex-index-1)+"(readable lines)");
    }

    double[][] tspCOORDData = new double[tspN][2];
    for (int i=index+1; i<endIndex; i++) {
      String[] lineInfos = GlobalString.tokenize(lines[i], " \t");
      tspCOORDData[i-index-1][0] = Double.parseDouble(lineInfos[1]);
      tspCOORDData[i-index-1][1] = Double.parseDouble(lineInfos[2]);
    }
    tspData.tspCOORDData = tspCOORDData;
    return tspData;
  }

  private static String getSubString(String[] lines, String headStr) {
    return GlobalString.getFirstStringWithHead(lines, headStr, ":");
  }
}