protoas/NearestNeighbour.java

   1 package protoas;
   2
   3 class NearestNeighbour {
   4
   5   protected Graph graph;
   6   protected int[][] NearestNeighbour;
   7
   8   NearestNeighbour(Graph graph) {
   9     this.graph = graph;
  10     this.NearestNeighbour =
  11       new int[graph.getNumOfCities()][graph.getNearestNeighboursDepth()];
  12
  13     for (int i = 0; i < graph.getNumOfCities(); i++) {
  14       for (int j = 0; j < graph.getNearestNeighboursDepth(); j++) {
  15         setNearestNeighbour(i, j, -1);
  16       }
  17     }
  18   }
  19
  20   public void computeNearestNeighbours() {
  21     for (int City = 0; City < graph.getNumOfCities(); City++) {
  22       for (int Neighbour = 0; Neighbour < graph.getNumOfCities(); Neighbour++) {
  23
  24         if (City == Neighbour) {
  25           continue;
  26         } else {
  27
  28           for (int d = 0; d < graph.getNearestNeighboursDepth(); d++) {
  29
  30             /* if there is no entry yet, then assign */
  31             if (getNearestNeighbour(City,d) == -1) {
  32               setNearestNeighbour(City,d, Neighbour);
  33               break;
  34             }
  35             /* if distance from city to neighbour is smaller
  36              * than distance from city to neighbour from list */
  37             if (graph.getDistance(City,Neighbour) <
  38                 graph.getDistance(City, getNearestNeighbour(City,d))) {
  39
  40               /* copy element n-1 to n; right shift so to say; until elem d is reached */
  41               for (int c = graph.getNearestNeighboursDepth() - 1; c > d; c--) {
  42                 setNearestNeighbour(City,c, getNearestNeighbour(City,c-1));
  43               }
  44               setNearestNeighbour(City,d, Neighbour);
  45               break;
  46
  47                 }
  48
  49           }
  50         }
  51       }
  52     }
  53   }
  54
  55   public int[][] getNearestNeighbour() {
  56     return this.NearestNeighbour;
  57   }
  58
  59   public int getNearestNeighbour(int x, int y) {
  60     return this.NearestNeighbour[x][y];
  61   }
  62
  63   public void setNearestNeighbour(int[][] NearestNeighbour) {
  64     this.NearestNeighbour = NearestNeighbour;
  65   }
  66
  67   public void setNearestNeighbour(int x, int y, int NearestNeighbour) {
  68     this.NearestNeighbour[x][y] = NearestNeighbour;
  69   }
  70
  71 }