NearestNeighbour.java

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