Graph.java

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