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[l] != null) {
 222           result.append("\n" + ids[l++] + "\t");
 223         } else {
 224           result.append("\n" + (l++) + "\t");
 225         }
 226         for (int j : i) {
 227           if (j == INFINITY) {
 228             result.append("INF\t");
 229           } else {
 230             result.append(j + "\t");
 231           }
 232         }
 233       }
 234
 235       return result.toString();
 236     }
 237
 238   public static Graph sampleGraph() {
 239
 240     Graph graph = new Graph(11, 10);
 241
 242     int[][] Distances = new int[11][11];
 243
 244     /* Nuernberg - Leipzig */
 245     Distances[0][1] = 269;
 246     /* Nuernberg - Dresden */
 247     Distances[0][2] = 313;
 248     /* Nuernberg - Berlin */
 249     Distances[0][3] = 441;
 250     /* Nuernberg - Hamburg */
 251     Distances[0][4] = 609;
 252     /* Nuernberg - Bremen */
 253     Distances[0][5] = 582;
 254     /* Nuernberg - Hannover */
 255     Distances[0][6] = 465;
 256     /* Nuernberg - Koeln */
 257     Distances[0][7] = 410;
 258     /* Nuernberg - Frankfurt */
 259     Distances[0][8] = 225;
 260     /* Nuernberg - Stuttgart */
 261     Distances[0][9] = 208;
 262     /* Nuernberg - Muenchen */
 263     Distances[0][10] = 166;
 264
 265     /* Leipzig - Dresden */
 266     Distances[1][2] = 116;
 267     /* Leipzig - Berlin */
 268     Distances[1][3] = 195;
 269     /* Leipzig - Hamburg */
 270     Distances[1][4] = 396;
 271     /* Leipzig - Bremen */
 272     Distances[1][5] = 369;
 273     /* Leipzig - Hannover */
 274     Distances[1][6] = 264;
 275     /* Leipzig - Koeln */
 276     Distances[1][7] = 498;
 277     /* Leipzig - Frankfurt */
 278     Distances[1][8] = 391;
 279     /* Leipzig - Stuttgart */
 280     Distances[1][9] = 478;
 281     /* Leipzig - Muenchen */
 282     Distances[1][10] = 430;
 283
 284     /* Dresden - Berlin */
 285     Distances[2][3] = 194;
 286     /* Dresden - Hamburg */
 287     Distances[2][4] = 477;
 288     /* Dresden - Bremen */
 289     Distances[2][5] = 473;
 290     /* Dresden - Hannover */
 291     Distances[2][6] = 367;
 292     /* Dresden - Koeln */
 293     Distances[2][7] = 573;
 294     /* Dresden - Frankfurt */
 295     Distances[2][8] = 463;
 296     /* Dresden - Stuttgart */
 297     Distances[2][9] = 510;
 298     /* Dresden - Muenchen */
 299     Distances[2][10] = 465;
 300
 301     /* Berlin - Hamburg */
 302     Distances[3][4] = 288;
 303     /* Berlin - Bremen */
 304     Distances[3][5] = 392;
 305     /* Berlin - Hannover */
 306     Distances[3][6] = 286;
 307     /* Berlin - Koeln */
 308     Distances[3][7] = 575;
 309     /* Berlin - Frankfurt */
 310     Distances[3][8] = 547;
 311     /* Berlin - Stuttgart */
 312     Distances[3][9] = 633;
 313     /* Berlin - Muenchen */
 314     Distances[3][10] = 585;
 315
 316     /* Hamburg - Bremen */
 317     Distances[4][5] = 122;
 318     /* Hamburg - Hannover */
 319     Distances[4][6] = 157;
 320     /* Hamburg - Koeln */
 321     Distances[4][7] = 426;
 322     /* Hamburg - Frankfurt */
 323     Distances[4][8] = 493;
 324     /* Hamburg - Stuttgart */
 325     Distances[4][9] = 655;
 326     /* Hamburg - Muenchen */
 327     Distances[4][10] = 775;
 328
 329     /* Bremen - Hannover */
 330     Distances[5][6] = 131;
 331     /* Bremen - Koeln */
 332     Distances[5][7] = 315;
 333     /* Bremen - Frankfurt */
 334     Distances[5][8] = 441;
 335     /* Bremen - Stuttgart */
 336     Distances[5][9] = 629;
 337     /* Bremen - Muenchen */
 338     Distances[5][10] = 749;
 339
 340     /* Hannover - Koeln */
 341     Distances[6][7] = 295;
 342     /* Hannover - Frankfurt */
 343     Distances[6][8] = 349;
 344     /* Hannover - Stuttgart */
 345     Distances[6][9] = 512;
 346     /* Hannover - Muenchen */
 347     Distances[6][10] = 632;
 348
 349     /* Koeln - Frankfurt */
 350     Distances[7][8] = 194;
 351     /* Koeln - Stuttgart */
 352     Distances[7][9] = 369;
 353     /* Koeln - Muenchen */
 354     Distances[7][10] = 576;
 355
 356     /* Frankfurt - Stuttgart */
 357     Distances[8][9] = 209;
 358     /* Frankfurt - Muenchen */
 359     Distances[8][10] = 393;
 360
 361     /* Stuttgart - Muenchen */
 362     Distances[9][10] = 220;
 363
 364     graph.setDistance(Distances);
 365
 366     String[] ids = {"NBG", "Leipzip", "Dresden", "Berlin", "Hamburg",
 367                     "Bremen", "HAN", "Koeln", "FFM", "STR",
 368                     "MUC"};
 369     graph.ids = ids;
 370
 371     graph.mirrorDistances();
 372     graph.computeNearestNeighbours();
 373     graph.computeChoiceInformation();
 374
 375     return graph;
 376   }
 377
 378   public static void main (String[] args) {
 379     Graph graph = Graph.sampleGraph();
 380     System.out.println(graph);
 381     graph.printNearestNeighbours();
 382   }
 383
 384 }