VRPH  1.0
src/VRPTSPLib.cpp
Go to the documentation of this file.
00001 
00002 //                                                        //
00003 // This file is part of the VRPH software package for     //
00004 // generating solutions to vehicle routing problems.      //
00005 // VRPH was developed by Chris Groer (cgroer@gmail.com).  //
00006 //                                                        //
00007 // (c) Copyright 2010 Chris Groer.                        //
00008 // All Rights Reserved.  VRPH is licensed under the       //
00009 // Common Public License.  See LICENSE file for details.  //
00010 //                                                        //
00012 
00013 #include "VRPH.h"
00014 
00015 // Lists the various TSPLIB strings that are supported
00016 const char *SupportedTSPLIBStrings[]={
00017     "NAME","TYPE","BEST_KNOWN","DIMENSION",
00018     // 4
00019     "CAPACITY","DISTANCE","EDGE_WEIGHT_FORMAT","EDGE_WEIGHT_TYPE",
00020     // 8
00021     "NODE_COORD_TYPE","EOF","NODE_COORD_SECTION","DEPOT_SECTION",
00022     // 12
00023     "DEMAND_SECTION","EDGE_WEIGHT_SECTION","SERVICE_TIME","cxd",
00024     // 16
00025     "NUM_DAYS","SVC_TIME_SECTION","TIME_WINDOW_SECTION","COMMENT",
00026     // 20
00027     "DISPLAY_DATA_SECTION","TWOD_DISPLAY","DISPLAY_DATA_TYPE","NO_DISPLAY",
00028     // 24
00029     "COORD_DISPLAY"};
00030 
00031 
00032 // The lengths of the different supported TSPLIB strings
00033 const int SL[]={4,4,10,9,
00034                 8,8,18,16,
00035                 14,3,18,13,
00036                 13,14,12,8,
00037                 8,16,19,7,
00038                 20,12,17,10,
00039                 13};
00040 
00041 // Simply the number of supported strings
00042 const int NumSupportedTSPLIBStrings = 25;
00043 
00044 // Lists the various TSPLIB strings that are NOT supported
00045 const char *UnsupportedTSPLIBStrings[]=    {
00046     "HCP","ATSP","SOP","TOUR","ATT","XRAY1","XRAY2","SPECIAL",
00047     "LOWER_ROW",
00048     "LOWER_DIAG_ROW","UPPER_COL","LOWER_COL","UPPER_DIAG_COL",
00049     "LOWER_DIAG_COL","EDGE_LIST","ADJ_LIST","NO_COORDS",
00050     "EDGE_DATA_SECTION",
00051     "TOUR_SECTION"
00052 };
00053 // The number of unsupported TSPLIB strings
00054 const int NumUnsupportedTSPLIBStrings = 20;
00055 
00056 int VRPGetDimension(char *filename)
00057 {
00063 
00064     FILE *infile;
00065     char str1[VRPH_STRING_SIZE];
00066     int i,n;
00067 
00068     n=-1;
00069     for(i=0;i<VRPH_STRING_SIZE;i++)
00070         str1[i]=0;
00071 
00072     infile=fopen(filename,"r");
00073     if(infile==NULL)
00074     {
00075         fprintf(stderr,"Unable to open %s for reading\n",filename);
00076         exit(-1);
00077 
00078     }
00079 
00080     fscanf(infile,"%s",str1);
00081 
00082     while(strncmp(str1,"DIMENSION:",10)!=0 && strncmp(str1,"DIMENSION",9)!=0)
00083     {
00084         fscanf(infile,"%s\n",str1);
00085         if(feof(infile))
00086         {    
00087             fprintf(stderr, "The keyword DIMENSION was not found in the TSPLIB file %s\nExiting...\n",filename);
00088             exit(-1);
00089         }
00090 
00091     }
00092     // We found the keyword DIMENSION-get n now - watch out for an annoying possibility involving the colon!
00093     fscanf(infile,"%s",str1);
00094     if(strncmp(str1,":",1)==0)
00095         fscanf(infile,"%d\n",&n);
00096     else
00097         n=atoi((const char *)str1);
00098 
00099     //Check for EOF
00100     rewind(infile);
00101 
00102     // Now make sure we have the string EOF as the very last line
00103 
00104     fscanf(infile,"%s\n",str1);
00105     while(strncmp(str1,"EOF",3)!=0)
00106     {
00107         fscanf(infile,"%s\n",str1);        
00108 
00109         if(feof(infile) && strncmp(str1,"EOF",3)!=0)
00110         {    
00111             fprintf(stderr, "The keyword EOF was not found in the TSPLIB file %s\n",
00112                 filename);
00113             exit(-1);
00114         }
00115 
00116     }
00117 
00118     fclose(infile);
00119 
00120     // We return the # of non-VRPH_DEPOT nodes
00121     return n-1;
00122 
00123 }
00124 
00125 
00126 int VRPGetNumDays(char *filename)
00127 {
00133 
00134     FILE *infile;
00135     char str1[VRPH_STRING_SIZE];
00136     int i,n;
00137 
00138     n=-1;
00139     for(i=0;i<VRPH_STRING_SIZE;i++)
00140         str1[i]=0;
00141 
00142     infile=fopen(filename,"r");
00143     if(infile==NULL)
00144     {
00145         fprintf(stderr,"Unable to open %s for reading\n",filename);
00146         exit(-1);
00147 
00148     }
00149 
00150     fscanf(infile,"%s",str1);
00151 
00152     while(strncmp(str1,"NUM_DAYS",8)!=0 && strncmp(str1,"NUM_DAYS:",9)!=0)
00153     {
00154         fscanf(infile,"%s\n",str1);
00155         if(feof(infile))
00156         {    
00157             // Assume a 1-day problem
00158             fclose(infile);
00159             return 1;
00160         }
00161 
00162     }
00163     // We found the keyword NUM_DAYS - get the value and return
00164     fscanf(infile,"%d\n",&n);
00165     fclose(infile);
00166     return n;
00167 
00168 
00169 
00170 }
00171 
00172 int VRPCheckTSPLIBString(char *s)
00173 {
00179 
00180 
00181     int i;
00182 #if TSPLIB_DEBUG
00183     fprintf(stderr,"Checking string %s\n",s);
00184 #endif
00185 
00186     for(i=0;i<NumSupportedTSPLIBStrings;i++)
00187     {
00188         if(strncmp((const char *)s, SupportedTSPLIBStrings[i],SL[i])==0)
00189             return i+1;
00190     }
00191 
00192 #if TSPLIB_DEBUG
00193     fprintf(stderr,"Didn't find string %s in supported list\n",s);
00194 #endif
00195 
00196     // Didn't find a supported string - check for other known 
00197     // unsupported strings
00198 
00199 
00200     for(i=0;i<NumUnsupportedTSPLIBStrings;i++)
00201     {
00202         if(strcmp((const char *)s, UnsupportedTSPLIBStrings[i])==0)
00203             return -(i+1);
00204     }
00205 
00206     // Unknown string encountered
00207     fprintf(stderr,"Unknown string %s encountered\n", s);
00208     report_error("%s: Error related to TSPLIB string\n");
00209     return -1;
00210 }