protoas/Graph.java

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