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 = 5.0;
   8   public final double ROH = 0.2;
   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 int nearestNeighbourHeuristic(int city, boolean[] visited, int remaining) {
  85
  86     int nextmin = INFINITY;
  87     int nextcity = 0;
  88
  89     for (int i = 0; i < getNumOfCities(); i++) {
  90         if ((i != city) && (!visited[i]) && (getDistance(i,city) < nextmin)) {
  91           nextmin = getDistance(i,city);
  92           nextcity = i;
  93         }
  94     }
  95
  96     visited[nextcity] = true;
  97
  98     if (remaining == 1)
  99       return nextmin;
 100     else
 101       return nextmin + nearestNeighbourHeuristic(nextcity, visited, remaining - 1);
 102   }
 103
 104   public int nearestNeighbourHeuristicRandomStart() {
 105     boolean[] visited = new boolean[getNumOfCities()];
 106     for (int i = 0; i < getNumOfCities(); i++)
 107       visited[i] = false;
 108     return nearestNeighbourHeuristic(
 109         (int)(Math.random() * getNumOfCities()),
 110         visited, getNumOfCities());
 111   }
 112
 113   public Boolean hasCoordinates() {
 114     return coordinate != null;
 115   }
 116
 117   public Boolean hasIds() {
 118     return ids != null;
 119   }
 120
 121   public int getNumOfCities() {
 122     return this.NumOfCities;
 123   }
 124
 125   public int getNearestNeighboursDepth() {
 126     return this.NearestNeighboursDepth;
 127   }
 128
 129   public int getDistance(int x, int y) {
 130     return this.distance.getDistance(x, y);
 131   }
 132
 133   public Coordinate getCoordinate() {
 134     return this.coordinate;
 135   }
 136
 137   public double getPheromone(int x, int y) {
 138     return this.pheromone.getPheromone(x, y);
 139   }
 140
 141   public int getNearestNeighbour(int x, int y) {
 142     return this.nearestneighbour.getNearestNeighbour(x, y);
 143   }
 144
 145   public double getChoiceInformation(int x, int y) {
 146     return this.choiceinformation.getChoiceInformation(x, y);
 147   }
 148
 149   public double getALPHA() {
 150     return this.ALPHA;
 151   }
 152
 153   public double getBETA() {
 154     return this.BETA;
 155   }
 156
 157   public double getROH() {
 158     return this.ROH;
 159   }
 160
 161   public int getINFINITY() {
 162     return this.INFINITY;
 163   }
 164
 165   public void setNumOfCities(int NumOfCities) {
 166     this.NumOfCities = NumOfCities;
 167   }
 168
 169   public void setNearestNeighboursDepth(int NearestNeighboursDepth) {
 170     this.NearestNeighboursDepth = NearestNeighboursDepth;
 171   }
 172
 173   public String[] getIds() {
 174     return this.ids;
 175   }
 176
 177   public String getIds(int index) {
 178     if (this.ids != null) {
 179       return this.ids[index];
 180     } else {
 181       return null;
 182     }
 183   }
 184
 185   public void setIds(String[] ids) {
 186     this.ids = ids;
 187   }
 188
 189   public void setIds(int index, String ids) {
 190     this.ids[index] = ids;
 191   }
 192
 193   protected void setDistance(int x, int y, int Distance) {
 194     this.distance.setDistance(x,y, Distance);
 195   }
 196
 197   protected void setDistance(int[][] Distance) {
 198     this.distance.setDistance(Distance);
 199   }
 200
 201   protected void mirrorDistances() {
 202     for (int i = 0; i < NumOfCities; i++) {
 203       for (int j = 0; j < NumOfCities; j++) {
 204         if (distance.getDistance(i,j) != getINFINITY()) {
 205           distance.setDistance(j,i, distance.getDistance(i,j));
 206         } else {
 207           distance.setDistance(i,j, distance.getDistance(j,i));
 208         }
 209       }
 210     }
 211   }
 212
 213   protected void printNearestNeighbours() {
 214     for (int c = 0; c < getNumOfCities(); c++) {
 215       if (getIds(c) != null) {
 216         System.out.println("Nearest neighbours of: " + getIds(c));
 217       } else {
 218         System.out.println("Nearest neighbours of: " + c);
 219       }
 220       for (int n = 0; n < getNearestNeighboursDepth(); n++) {
 221         if (nearestneighbour.getNearestNeighbour(c,n) != -1) {
 222           if ( getIds( nearestneighbour.getNearestNeighbour(c,n) ) != null ) {
 223             System.out.print(
 224               getIds( nearestneighbour.getNearestNeighbour(c,n) ) + "\t");
 225           } else {
 226             System.out.print(nearestneighbour.getNearestNeighbour(c,n) + "\t");
 227           }
 228         } else {
 229           System.out.print("none" + "\t");
 230         }
 231       }
 232       System.out.println();
 233     }
 234   }
 235
 236   @Override
 237     public String toString() {
 238       StringBuilder result = new StringBuilder();
 239
 240       if (getIds() != null) {
 241         for (String id : getIds())
 242           result.append("\t" + id);
 243       } else {
 244         for (int i = 0; i < NumOfCities; i++)
 245           result.append("\t" + i);
 246       }
 247
 248       int l = 0;
 249       for (int i[] : distance.getDistance()) {
 250         if (ids != null) {
 251           if (ids[l] != null) {
 252             result.append("\n" + ids[l++] + "\t");
 253           } else {
 254             result.append("\n" + (l++) + "\t");
 255           }
 256         } else {
 257             result.append("\n" + (l++) + "\t");
 258         }
 259
 260         for (int j : i) {
 261           if (j == INFINITY) {
 262             result.append("INF\t");
 263           } else {
 264             result.append(j + "\t");
 265           }
 266         }
 267       }
 268
 269       return result.toString();
 270     }
 271
 272   public static Graph sampleGraph() {
 273
 274     Graph graph = new Graph(11, 10);
 275
 276     int[][] Distances = new int[11][11];
 277
 278     /* Nuernberg - Leipzig */
 279     Distances[0][1] = 269;
 280     /* Nuernberg - Dresden */
 281     Distances[0][2] = 313;
 282     /* Nuernberg - Berlin */
 283     Distances[0][3] = 441;
 284     /* Nuernberg - Hamburg */
 285     Distances[0][4] = 609;
 286     /* Nuernberg - Bremen */
 287     Distances[0][5] = 582;
 288     /* Nuernberg - Hannover */
 289     Distances[0][6] = 465;
 290     /* Nuernberg - Koeln */
 291     Distances[0][7] = 410;
 292     /* Nuernberg - Frankfurt */
 293     Distances[0][8] = 225;
 294     /* Nuernberg - Stuttgart */
 295     Distances[0][9] = 208;
 296     /* Nuernberg - Muenchen */
 297     Distances[0][10] = 166;
 298
 299     /* Leipzig - Dresden */
 300     Distances[1][2] = 116;
 301     /* Leipzig - Berlin */
 302     Distances[1][3] = 195;
 303     /* Leipzig - Hamburg */
 304     Distances[1][4] = 396;
 305     /* Leipzig - Bremen */
 306     Distances[1][5] = 369;
 307     /* Leipzig - Hannover */
 308     Distances[1][6] = 264;
 309     /* Leipzig - Koeln */
 310     Distances[1][7] = 498;
 311     /* Leipzig - Frankfurt */
 312     Distances[1][8] = 391;
 313     /* Leipzig - Stuttgart */
 314     Distances[1][9] = 478;
 315     /* Leipzig - Muenchen */
 316     Distances[1][10] = 430;
 317
 318     /* Dresden - Berlin */
 319     Distances[2][3] = 194;
 320     /* Dresden - Hamburg */
 321     Distances[2][4] = 477;
 322     /* Dresden - Bremen */
 323     Distances[2][5] = 473;
 324     /* Dresden - Hannover */
 325     Distances[2][6] = 367;
 326     /* Dresden - Koeln */
 327     Distances[2][7] = 573;
 328     /* Dresden - Frankfurt */
 329     Distances[2][8] = 463;
 330     /* Dresden - Stuttgart */
 331     Distances[2][9] = 510;
 332     /* Dresden - Muenchen */
 333     Distances[2][10] = 465;
 334
 335     /* Berlin - Hamburg */
 336     Distances[3][4] = 288;
 337     /* Berlin - Bremen */
 338     Distances[3][5] = 392;
 339     /* Berlin - Hannover */
 340     Distances[3][6] = 286;
 341     /* Berlin - Koeln */
 342     Distances[3][7] = 575;
 343     /* Berlin - Frankfurt */
 344     Distances[3][8] = 547;
 345     /* Berlin - Stuttgart */
 346     Distances[3][9] = 633;
 347     /* Berlin - Muenchen */
 348     Distances[3][10] = 585;
 349
 350     /* Hamburg - Bremen */
 351     Distances[4][5] = 122;
 352     /* Hamburg - Hannover */
 353     Distances[4][6] = 157;
 354     /* Hamburg - Koeln */
 355     Distances[4][7] = 426;
 356     /* Hamburg - Frankfurt */
 357     Distances[4][8] = 493;
 358     /* Hamburg - Stuttgart */
 359     Distances[4][9] = 655;
 360     /* Hamburg - Muenchen */
 361     Distances[4][10] = 775;
 362
 363     /* Bremen - Hannover */
 364     Distances[5][6] = 131;
 365     /* Bremen - Koeln */
 366     Distances[5][7] = 315;
 367     /* Bremen - Frankfurt */
 368     Distances[5][8] = 441;
 369     /* Bremen - Stuttgart */
 370     Distances[5][9] = 629;
 371     /* Bremen - Muenchen */
 372     Distances[5][10] = 749;
 373
 374     /* Hannover - Koeln */
 375     Distances[6][7] = 295;
 376     /* Hannover - Frankfurt */
 377     Distances[6][8] = 349;
 378     /* Hannover - Stuttgart */
 379     Distances[6][9] = 512;
 380     /* Hannover - Muenchen */
 381     Distances[6][10] = 632;
 382
 383     /* Koeln - Frankfurt */
 384     Distances[7][8] = 194;
 385     /* Koeln - Stuttgart */
 386     Distances[7][9] = 369;
 387     /* Koeln - Muenchen */
 388     Distances[7][10] = 576;
 389
 390     /* Frankfurt - Stuttgart */
 391     Distances[8][9] = 209;
 392     /* Frankfurt - Muenchen */
 393     Distances[8][10] = 393;
 394
 395     /* Stuttgart - Muenchen */
 396     Distances[9][10] = 220;
 397
 398     graph.setDistance(Distances);
 399
 400     String[] ids = {"NBG", "Leipzip", "Dresden", "Berlin", "Hamburg",
 401                     "Bremen", "HAN", "Koeln", "FFM", "STR",
 402                     "MUC"};
 403     graph.ids = ids;
 404
 405     graph.mirrorDistances();
 406     graph.computeNearestNeighbours();
 407     graph.computeChoiceInformation();
 408
 409     return graph;
 410   }
 411
 412   public static void main (String[] args) {
 413     try {
 414       Graph graph;
 415       if (args.length == 1)
 416         graph = new Graph(args[0]);
 417       else
 418         graph = Graph.sampleGraph();
 419       System.out.println(graph);
 420       graph.printNearestNeighbours();
 421     } catch (Exception e) {
 422       System.out.println(e.toString() + "(" + e.getClass() + "): " + e);
 423       System.exit(1);
 424     }
 425   }
 426
 427 }