Graph.java

   1 import java.io.IOException;
   2
   3 class Graph {
   4
   5   public final int INFINITY = Integer.MAX_VALUE;
   6   public final double ALPHA = 1.0;
   7   public final double BETA = 2.0;
   8   public final double ROH = 0.5;
   9
  10   protected int NumOfCities;
  11   protected int NearestNeighboursDepth;
  12
  13   public String[] ids = null;
  14
  15   // NxN; Distance Matrix
  16   protected Distance distance;
  17   // NxN; Pheromone Matrix
  18   protected Pheromone pheromone;
  19   // NxNN; Nearest Neighbours List of depth NN
  20   protected NearestNeighbour nearestneighbour;
  21   // NxN; combined pheromone and heuristic information
  22   protected ChoiceInformation choiceinformation;
  23
  24   protected Coordinate coordinate = null;
  25
  26   Graph(String filename) throws IOException {
  27     TSPLibReader tsplibreader = new TSPLibReader(filename);
  28     this.coordinate = new Coordinate(this, tsplibreader);
  29
  30     if (NumOfCities <= 30)
  31       this.NearestNeighboursDepth = NumOfCities - 1;
  32     else if (NumOfCities > 30 && NumOfCities < 80)
  33       this.NearestNeighboursDepth = NumOfCities/2;
  34     else
  35       this.NearestNeighboursDepth = 40;
  36
  37     this.distance = new Distance(this, coordinate.computeDistances());
  38     this.pheromone = new Pheromone(this);
  39     this.nearestneighbour = new NearestNeighbour(this);
  40     this.choiceinformation = new ChoiceInformation(this);
  41
  42     computeNearestNeighbours();
  43     computeChoiceInformation();
  44   }
  45
  46   Graph(int NumOfCities) {
  47     if (NumOfCities <= 30)
  48       this.NearestNeighboursDepth = NumOfCities - 1;
  49     else if (NumOfCities > 30 && NumOfCities < 80)
  50       this.NearestNeighboursDepth = NumOfCities/2;
  51     else
  52       this.NearestNeighboursDepth = 40;
  53
  54     this.NumOfCities = NumOfCities;
  55
  56     this.distance = new Distance(this);
  57     this.pheromone = new Pheromone(this);
  58     this.nearestneighbour = new NearestNeighbour(this);
  59     this.choiceinformation = new ChoiceInformation(this);
  60   }
  61
  62   Graph(int NumOfCities, int NearestNeighboursDepth) {
  63     this.NumOfCities = NumOfCities;
  64     this.NearestNeighboursDepth = NearestNeighboursDepth;
  65
  66     this.distance = new Distance(this);
  67     this.pheromone = new Pheromone(this);
  68     this.nearestneighbour = new NearestNeighbour(this);
  69     this.choiceinformation = new ChoiceInformation(this);
  70   }
  71
  72   public void pheromoneUpdate(Ant[] ants) {
  73     pheromone.pheromoneUpdate(ants);
  74   }
  75
  76   public void computeNearestNeighbours() {
  77     this.nearestneighbour.computeNearestNeighbours();
  78   }
  79
  80   public void computeChoiceInformation() {
  81     this.choiceinformation.computeChoiceInformation();
  82   }
  83
  84   public Boolean hasCoordinates() {
  85     return coordinate != null;
  86   }
  87
  88   public Boolean hasIds() {
  89     return ids != null;
  90   }
  91
  92   public int getNumOfCities() {
  93     return this.NumOfCities;
  94   }
  95
  96   public int getNearestNeighboursDepth() {
  97     return this.NearestNeighboursDepth;
  98   }
  99
 100   public int getDistance(int x, int y) {
 101     return this.distance.getDistance(x, y);
 102   }
 103
 104   public Coordinate getCoordinate() {
 105     return this.coordinate;
 106   }
 107
 108   public double getPheromone(int x, int y) {
 109     return this.pheromone.getPheromone(x, y);
 110   }
 111
 112   public int getNearestNeighbour(int x, int y) {
 113     return this.nearestneighbour.getNearestNeighbour(x, y);
 114   }
 115
 116   public double getChoiceInformation(int x, int y) {
 117     return this.choiceinformation.getChoiceInformation(x, y);
 118   }
 119
 120   public double getALPHA() {
 121     return this.ALPHA;
 122   }
 123
 124   public double getBETA() {
 125     return this.BETA;
 126   }
 127
 128   public double getROH() {
 129     return this.ROH;
 130   }
 131
 132   public int getINFINITY() {
 133     return this.INFINITY;
 134   }
 135
 136   public void setNumOfCities(int NumOfCities) {
 137     this.NumOfCities = NumOfCities;
 138   }
 139
 140   public void setNearestNeighboursDepth(int NearestNeighboursDepth) {
 141     this.NearestNeighboursDepth = NearestNeighboursDepth;
 142   }
 143
 144   public String[] getIds() {
 145     return this.ids;
 146   }
 147
 148   public String getIds(int index) {
 149     if (this.ids != null) {
 150       return this.ids[index];
 151     } else {
 152       return null;
 153     }
 154   }
 155
 156   public void setIds(String[] ids) {
 157     this.ids = ids;
 158   }
 159
 160   public void setIds(int index, String ids) {
 161     this.ids[index] = ids;
 162   }
 163
 164   protected void setDistance(int x, int y, int Distance) {
 165     this.distance.setDistance(x,y, Distance);
 166   }
 167
 168   protected void setDistance(int[][] Distance) {
 169     this.distance.setDistance(Distance);
 170   }
 171
 172   protected void mirrorDistances() {
 173     for (int i = 0; i < NumOfCities; i++) {
 174       for (int j = 0; j < NumOfCities; j++) {
 175         if (distance.getDistance(i,j) != INFINITY) {
 176           distance.setDistance(j,i, distance.getDistance(i,j));
 177         } else {
 178           distance.setDistance(i,j, distance.getDistance(j,i));
 179         }
 180       }
 181     }
 182   }
 183
 184   protected void printNearestNeighbours() {
 185     for (int c = 0; c < getNumOfCities(); c++) {
 186       if (getIds(c) != null) {
 187         System.out.println("Nearest neighbours of: " + getIds(c));
 188       } else {
 189         System.out.println("Nearest neighbours of: " + c);
 190       }
 191       for (int n = 0; n < getNearestNeighboursDepth(); n++) {
 192         if (nearestneighbour.getNearestNeighbour(c,n) != -1) {
 193           if ( getIds( nearestneighbour.getNearestNeighbour(c,n) ) != null ) {
 194             System.out.print(
 195               getIds( nearestneighbour.getNearestNeighbour(c,n) ) + "\t");
 196           } else {
 197             System.out.print(nearestneighbour.getNearestNeighbour(c,n) + "\t");
 198           }
 199         } else {
 200           System.out.print("none" + "\t");
 201         }
 202       }
 203       System.out.println();
 204     }
 205   }
 206
 207   @Override
 208     public String toString() {
 209       StringBuilder result = new StringBuilder();
 210
 211       if (getIds() != null) {
 212         for (String id : getIds())
 213           result.append("\t" + id);
 214       } else {
 215         for (int i = 0; i < NumOfCities; i++)
 216           result.append("\t" + i);
 217       }
 218
 219       int l = 0;
 220       for (int i[] : distance.getDistance()) {
 221         if (ids != null) {
 222           if (ids[l] != null) {
 223             result.append("\n" + ids[l++] + "\t");
 224           } else {
 225             result.append("\n" + (l++) + "\t");
 226           }
 227         } else {
 228             result.append("\n" + (l++) + "\t");
 229         }
 230
 231         for (int j : i) {
 232           if (j == INFINITY) {
 233             result.append("INF\t");
 234           } else {
 235             result.append(j + "\t");
 236           }
 237         }
 238       }
 239
 240       return result.toString();
 241     }
 242
 243   public static Graph sampleGraph() {
 244
 245     Graph graph = new Graph(11, 10);
 246
 247     int[][] Distances = new int[11][11];
 248
 249     /* Nuernberg - Leipzig */
 250     Distances[0][1] = 269;
 251     /* Nuernberg - Dresden */
 252     Distances[0][2] = 313;
 253     /* Nuernberg - Berlin */
 254     Distances[0][3] = 441;
 255     /* Nuernberg - Hamburg */
 256     Distances[0][4] = 609;
 257     /* Nuernberg - Bremen */
 258     Distances[0][5] = 582;
 259     /* Nuernberg - Hannover */
 260     Distances[0][6] = 465;
 261     /* Nuernberg - Koeln */
 262     Distances[0][7] = 410;
 263     /* Nuernberg - Frankfurt */
 264     Distances[0][8] = 225;
 265     /* Nuernberg - Stuttgart */
 266     Distances[0][9] = 208;
 267     /* Nuernberg - Muenchen */
 268     Distances[0][10] = 166;
 269
 270     /* Leipzig - Dresden */
 271     Distances[1][2] = 116;
 272     /* Leipzig - Berlin */
 273     Distances[1][3] = 195;
 274     /* Leipzig - Hamburg */
 275     Distances[1][4] = 396;
 276     /* Leipzig - Bremen */
 277     Distances[1][5] = 369;
 278     /* Leipzig - Hannover */
 279     Distances[1][6] = 264;
 280     /* Leipzig - Koeln */
 281     Distances[1][7] = 498;
 282     /* Leipzig - Frankfurt */
 283     Distances[1][8] = 391;
 284     /* Leipzig - Stuttgart */
 285     Distances[1][9] = 478;
 286     /* Leipzig - Muenchen */
 287     Distances[1][10] = 430;
 288
 289     /* Dresden - Berlin */
 290     Distances[2][3] = 194;
 291     /* Dresden - Hamburg */
 292     Distances[2][4] = 477;
 293     /* Dresden - Bremen */
 294     Distances[2][5] = 473;
 295     /* Dresden - Hannover */
 296     Distances[2][6] = 367;
 297     /* Dresden - Koeln */
 298     Distances[2][7] = 573;
 299     /* Dresden - Frankfurt */
 300     Distances[2][8] = 463;
 301     /* Dresden - Stuttgart */
 302     Distances[2][9] = 510;
 303     /* Dresden - Muenchen */
 304     Distances[2][10] = 465;
 305
 306     /* Berlin - Hamburg */
 307     Distances[3][4] = 288;
 308     /* Berlin - Bremen */
 309     Distances[3][5] = 392;
 310     /* Berlin - Hannover */
 311     Distances[3][6] = 286;
 312     /* Berlin - Koeln */
 313     Distances[3][7] = 575;
 314     /* Berlin - Frankfurt */
 315     Distances[3][8] = 547;
 316     /* Berlin - Stuttgart */
 317     Distances[3][9] = 633;
 318     /* Berlin - Muenchen */
 319     Distances[3][10] = 585;
 320
 321     /* Hamburg - Bremen */
 322     Distances[4][5] = 122;
 323     /* Hamburg - Hannover */
 324     Distances[4][6] = 157;
 325     /* Hamburg - Koeln */
 326     Distances[4][7] = 426;
 327     /* Hamburg - Frankfurt */
 328     Distances[4][8] = 493;
 329     /* Hamburg - Stuttgart */
 330     Distances[4][9] = 655;
 331     /* Hamburg - Muenchen */
 332     Distances[4][10] = 775;
 333
 334     /* Bremen - Hannover */
 335     Distances[5][6] = 131;
 336     /* Bremen - Koeln */
 337     Distances[5][7] = 315;
 338     /* Bremen - Frankfurt */
 339     Distances[5][8] = 441;
 340     /* Bremen - Stuttgart */
 341     Distances[5][9] = 629;
 342     /* Bremen - Muenchen */
 343     Distances[5][10] = 749;
 344
 345     /* Hannover - Koeln */
 346     Distances[6][7] = 295;
 347     /* Hannover - Frankfurt */
 348     Distances[6][8] = 349;
 349     /* Hannover - Stuttgart */
 350     Distances[6][9] = 512;
 351     /* Hannover - Muenchen */
 352     Distances[6][10] = 632;
 353
 354     /* Koeln - Frankfurt */
 355     Distances[7][8] = 194;
 356     /* Koeln - Stuttgart */
 357     Distances[7][9] = 369;
 358     /* Koeln - Muenchen */
 359     Distances[7][10] = 576;
 360
 361     /* Frankfurt - Stuttgart */
 362     Distances[8][9] = 209;
 363     /* Frankfurt - Muenchen */
 364     Distances[8][10] = 393;
 365
 366     /* Stuttgart - Muenchen */
 367     Distances[9][10] = 220;
 368
 369     graph.setDistance(Distances);
 370
 371     String[] ids = {"NBG", "Leipzip", "Dresden", "Berlin", "Hamburg",
 372                     "Bremen", "HAN", "Koeln", "FFM", "STR",
 373                     "MUC"};
 374     graph.ids = ids;
 375
 376     graph.mirrorDistances();
 377     graph.computeNearestNeighbours();
 378     graph.computeChoiceInformation();
 379
 380     return graph;
 381   }
 382
 383   public static void main (String[] args) {
 384     try {
 385       Graph graph;
 386       if (args.length == 1)
 387         graph = new Graph(args[0]);
 388       else
 389         graph = Graph.sampleGraph();
 390       System.out.println(graph);
 391       graph.printNearestNeighbours();
 392     } catch (Exception e) {
 393       System.out.println(e.toString() + "(" + e.getClass() + "): " + e);
 394       System.exit(1);
 395     }
 396   }
 397
 398 }