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     return this.ids[index];
 150   }
 151
 152   public void setIds(String[] ids) {
 153     this.ids = ids;
 154   }
 155
 156   public void setIds(int index, String ids) {
 157     this.ids[index] = ids;
 158   }
 159
 160   protected void setDistance(int[][] Distance) {
 161     this.distance.setDistance(Distance);
 162   }
 163
 164   protected void mirrorDistances() {
 165     for (int i = 0; i < NumOfCities; i++) {
 166       for (int j = 0; j < NumOfCities; j++) {
 167         if (distance.getDistance(i,j) != INFINITY) {
 168           distance.setDistance(j,i, distance.getDistance(i,j));
 169         } else {
 170           distance.setDistance(i,j, distance.getDistance(j,i));
 171         }
 172       }
 173     }
 174   }
 175
 176   protected void printNearestNeighbours() {
 177
 178     for (int c = 0; c < NumOfCities; c++) {
 179       if (getIds(c) != null) {
 180         System.out.println("Nearest neighbours of: " + getIds(c));
 181       } else {
 182         System.out.println("Nearest neighbours of: " + c);
 183       }
 184       for (int n = 0; n < NearestNeighboursDepth; n++) {
 185         if (nearestneighbour.getNearestNeighbour(c,n) != -1) {
 186           if ( getIds( nearestneighbour.getNearestNeighbour(c,n) ) != null ) {
 187             System.out.print(
 188               getIds( nearestneighbour.getNearestNeighbour(c,n) ) + "\t");
 189           } else {
 190             System.out.print(nearestneighbour.getNearestNeighbour(c,n) + "\t");
 191           }
 192         } else {
 193           System.out.print(nearestneighbour.getNearestNeighbour(c,n) + "\t");
 194         }
 195       }
 196       System.out.println();
 197     }
 198   }
 199
 200   @Override
 201     public String toString() {
 202       StringBuilder result = new StringBuilder();
 203
 204       if (getIds() != null) {
 205         for (String id : getIds())
 206           result.append("\t" + id);
 207       } else {
 208         for (int i = 0; i < NumOfCities; i++)
 209           result.append("\t" + i);
 210       }
 211
 212       int l = 0;
 213       for (int i[] : distance.getDistance()) {
 214         if (ids[l] != null) {
 215           result.append("\n" + ids[l++] + "\t");
 216         } else {
 217           result.append("\n" + (l++) + "\t");
 218         }
 219         for (int j : i) {
 220           if (j == INFINITY) {
 221             result.append("INF\t");
 222           } else {
 223             result.append(j + "\t");
 224           }
 225         }
 226       }
 227
 228       return result.toString();
 229     }
 230
 231   public static Graph sampleGraph() {
 232
 233     Graph graph = new Graph(11, 10);
 234
 235     int[][] Distances = new int[11][11];
 236
 237     /* Nuernberg - Leipzig */
 238     Distances[0][1] = 269;
 239     /* Nuernberg - Dresden */
 240     Distances[0][2] = 313;
 241     /* Nuernberg - Berlin */
 242     Distances[0][3] = 441;
 243     /* Nuernberg - Hamburg */
 244     Distances[0][4] = 609;
 245     /* Nuernberg - Bremen */
 246     Distances[0][5] = 582;
 247     /* Nuernberg - Hannover */
 248     Distances[0][6] = 465;
 249     /* Nuernberg - Koeln */
 250     Distances[0][7] = 410;
 251     /* Nuernberg - Frankfurt */
 252     Distances[0][8] = 225;
 253     /* Nuernberg - Stuttgart */
 254     Distances[0][9] = 208;
 255     /* Nuernberg - Muenchen */
 256     Distances[0][10] = 166;
 257
 258     /* Leipzig - Dresden */
 259     Distances[1][2] = 116;
 260     /* Leipzig - Berlin */
 261     Distances[1][3] = 195;
 262     /* Leipzig - Hamburg */
 263     Distances[1][4] = 396;
 264     /* Leipzig - Bremen */
 265     Distances[1][5] = 369;
 266     /* Leipzig - Hannover */
 267     Distances[1][6] = 264;
 268     /* Leipzig - Koeln */
 269     Distances[1][7] = 498;
 270     /* Leipzig - Frankfurt */
 271     Distances[1][8] = 391;
 272     /* Leipzig - Stuttgart */
 273     Distances[1][9] = 478;
 274     /* Leipzig - Muenchen */
 275     Distances[1][10] = 430;
 276
 277     /* Dresden - Berlin */
 278     Distances[2][3] = 194;
 279     /* Dresden - Hamburg */
 280     Distances[2][4] = 477;
 281     /* Dresden - Bremen */
 282     Distances[2][5] = 473;
 283     /* Dresden - Hannover */
 284     Distances[2][6] = 367;
 285     /* Dresden - Koeln */
 286     Distances[2][7] = 573;
 287     /* Dresden - Frankfurt */
 288     Distances[2][8] = 463;
 289     /* Dresden - Stuttgart */
 290     Distances[2][9] = 510;
 291     /* Dresden - Muenchen */
 292     Distances[2][10] = 465;
 293
 294     /* Berlin - Hamburg */
 295     Distances[3][4] = 288;
 296     /* Berlin - Bremen */
 297     Distances[3][5] = 392;
 298     /* Berlin - Hannover */
 299     Distances[3][6] = 286;
 300     /* Berlin - Koeln */
 301     Distances[3][7] = 575;
 302     /* Berlin - Frankfurt */
 303     Distances[3][8] = 547;
 304     /* Berlin - Stuttgart */
 305     Distances[3][9] = 633;
 306     /* Berlin - Muenchen */
 307     Distances[3][10] = 585;
 308
 309     /* Hamburg - Bremen */
 310     Distances[4][5] = 122;
 311     /* Hamburg - Hannover */
 312     Distances[4][6] = 157;
 313     /* Hamburg - Koeln */
 314     Distances[4][7] = 426;
 315     /* Hamburg - Frankfurt */
 316     Distances[4][8] = 493;
 317     /* Hamburg - Stuttgart */
 318     Distances[4][9] = 655;
 319     /* Hamburg - Muenchen */
 320     Distances[4][10] = 775;
 321
 322     /* Bremen - Hannover */
 323     Distances[5][6] = 131;
 324     /* Bremen - Koeln */
 325     Distances[5][7] = 315;
 326     /* Bremen - Frankfurt */
 327     Distances[5][8] = 441;
 328     /* Bremen - Stuttgart */
 329     Distances[5][9] = 629;
 330     /* Bremen - Muenchen */
 331     Distances[5][10] = 749;
 332
 333     /* Hannover - Koeln */
 334     Distances[6][7] = 295;
 335     /* Hannover - Frankfurt */
 336     Distances[6][8] = 349;
 337     /* Hannover - Stuttgart */
 338     Distances[6][9] = 512;
 339     /* Hannover - Muenchen */
 340     Distances[6][10] = 632;
 341
 342     /* Koeln - Frankfurt */
 343     Distances[7][8] = 194;
 344     /* Koeln - Stuttgart */
 345     Distances[7][9] = 369;
 346     /* Koeln - Muenchen */
 347     Distances[7][10] = 576;
 348
 349     /* Frankfurt - Stuttgart */
 350     Distances[8][9] = 209;
 351     /* Frankfurt - Muenchen */
 352     Distances[8][10] = 393;
 353
 354     /* Stuttgart - Muenchen */
 355     Distances[9][10] = 220;
 356
 357     graph.setDistance(Distances);
 358
 359     String[] ids = {"NBG", "Leipzip", "Dresden", "Berlin", "Hamburg",
 360                     "Bremen", "HAN", "Koeln", "FFM", "STR",
 361                     "MUC"};
 362     graph.ids = ids;
 363
 364     graph.mirrorDistances();
 365     graph.computeNearestNeighbours();
 366     graph.computeChoiceInformation();
 367
 368     return graph;
 369   }
 370
 371   public static void main (String[] args) {
 372     Graph graph = Graph.sampleGraph();
 373     System.out.println(graph);
 374     graph.printNearestNeighbours();
 375   }
 376
 377 }