Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Tree_tsp.java

   1
   2 //import java.util.Random;
   3
   4 /**
   5  * A class that represents a node in a binary tree.  Each node represents
   6  * a city in the TSP benchmark.
   7  **/
   8 final class Tree_tsp
   9 {
  10   /**
  11    * The number of nodes (cities) in this subtree
  12    **/
  13   private int sz;
  14   /**
  15    * The coordinates that this node represents
  16    **/
  17   private float x,y;
  18   /**
  19    * Left child of the tree
  20    **/
  21   private Tree_tsp  left;
  22   /**
  23    * Right child of tree
  24    **/
  25   private Tree_tsp  right;
  26   /**
  27    * The next pointer in a linked list of nodes in the subtree.  The list
  28    * contains the order of the cities to visit.
  29    **/
  30   private Tree_tsp  next;
  31   /**
  32    * The previous pointer in a linked list of nodes in the subtree. The list
  33    * contains the order of the cities to visit.
  34    **/
  35   private Tree_tsp  prev;
  36
  37   // used by the random number generator
  38   //private static final float  M_E2; //  = 7.3890560989306502274;
  39   //private static final float  M_E3; //  = 20.08553692318766774179;
  40   //private static final float  M_E6; //  = 403.42879349273512264299;
  41   //private static final float  M_E12; // = 162754.79141900392083592475;
  42
  43   /**
  44    * Construct a Tree node (a city) with the specified size
  45    * @param size the number of nodes in the (sub)tree
  46    * @param x the x coordinate of the city
  47    * @param y the y coordinate of the city
  48    * @param left the left subtree
  49    * @param right the right subtree
  50    **/
  51   Tree_tsp(int size, float x, float y, Tree_tsp l, Tree_tsp r)
  52   {
  53     /*M_E2  = 7.3890560989306502274f;
  54     M_E3  = 20.08553692318766774179f;
  55     M_E6  = 403.42879349273512264299f;
  56     M_E12 = 162754.79141900392083592475f;*/
  57
  58     sz = size;
  59     this.x = x;
  60     this.y = y;
  61     left = l;
  62     right = r;
  63     next = null;
  64     prev = null;
  65   }
  66
  67   /**
  68    * Find Euclidean distance between this node and the specified node.
  69    * @param b the specified node
  70    * @return the Euclidean distance between two tree nodes.
  71    **/
  72   float distance(Tree_tsp b)
  73   {
  74     return (Math.sqrtf((float)((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y))));
  75   }
  76
  77   /**
  78    * Create a list of tree nodes.  Requires root to be the tail of the list.
  79    * Only fills in next field, not prev.
  80    * @return the linked list of nodes
  81    **/
  82   Tree_tsp makeList()
  83   {
  84     Tree_tsp myleft, myright;
  85     Tree_tsp tleft,tright;
  86     Tree_tsp retval = this;
  87
  88     // head of left list
  89     if (left != null)
  90       myleft = left.makeList();
  91     else
  92       myleft = null;
  93
  94     // head of right list
  95     if (right != null)
  96       myright = right.makeList();
  97     else
  98       myright = null;
  99
 100     if (myright != null) {
 101       retval = myright;
 102       right.next = this;
 103     }
 104
 105     if (myleft != null) {
 106       retval = myleft;
 107       if (myright != null)
 108         left.next = myright;
 109       else
 110         left.next = this;
 111     }
 112     next = null;
 113
 114     return retval;
 115   }
 116
 117   /**
 118    * Reverse the linked list.  Assumes that there is a dummy "prev"
 119    * node at the beginning.
 120    **/
 121   void reverse()
 122   {
 123     Tree_tsp prev = this.prev;
 124     prev.next = null;
 125     this.prev = null;
 126     Tree_tsp back = this;
 127     Tree_tsp tmp = this;
 128     // reverse the list for the other nodes
 129     Tree_tsp next;
 130     for (Tree_tsp t = this.next; t != null; back = t, t = next) {
 131       next = t.next;
 132       t.next = back;
 133       back.prev = t;
 134     }
 135     // reverse the list for this node
 136     tmp.next = prev;
 137     prev.prev = tmp;
 138   }
 139
 140   /**
 141    * Use closest-point heuristic from Cormen, Leiserson, and Rivest.
 142    * @return a
 143    **/
 144   Tree_tsp conquer()
 145   {
 146     // create the list of nodes
 147     Tree_tsp t = makeList();
 148
 149     // Create initial cycle
 150     Tree_tsp cycle = t;
 151     t = t.next;
 152     cycle.next = cycle;
 153     cycle.prev = cycle;
 154
 155     // Loop over remaining points
 156     Tree_tsp donext;
 157     for (; t != null; t = donext) {
 158       donext = t.next; /* value won't be around later */
 159       Tree_tsp min = cycle;
 160       float mindist = t.distance(cycle);
 161       for (Tree_tsp tmp = cycle.next; tmp != cycle; tmp=tmp.next) {
 162         float test = tmp.distance(t);
 163         if (test < mindist) {
 164           mindist = test;
 165           min = tmp;
 166         } /* if */
 167       } /* for tmp... */
 168
 169       Tree_tsp next = min.next;
 170       Tree_tsp prev = min.prev;
 171
 172       float mintonext = min.distance(next);
 173       float mintoprev = min.distance(prev);
 174       float ttonext = t.distance(next);
 175       float ttoprev = t.distance(prev);
 176
 177       if ((float)(ttoprev - mintoprev) < (float)(ttonext - mintonext)) {
 178         /* insert between min and prev */
 179         prev.next = t;
 180         t.next = min;
 181         t.prev = prev;
 182         min.prev = t;
 183       } else {
 184         next.prev = t;
 185         t.next = next;
 186         min.next = t;
 187         t.prev = min;
 188       }
 189     } /* for t... */
 190
 191     return cycle;
 192   }
 193
 194   /**
 195    * Merge two cycles as per Karp.
 196    * @param a a subtree with one cycle
 197    * @param b a subtree with the other cycle
 198    **/
 199   Tree_tsp merge(Tree_tsp a, Tree_tsp b)
 200   {
 201     // Compute location for first cycle
 202     Tree_tsp   min = a;
 203     float mindist = distance(a);
 204     Tree_tsp   tmp = a;
 205     for (a = a.next; a != tmp; a = a.next) {
 206       float test = distance(a);
 207       if (test < mindist) {
 208         mindist = test;
 209         min = a;
 210       }
 211     }
 212
 213     Tree_tsp next = min.next;
 214     Tree_tsp prev = min.prev;
 215     float mintonext = min.distance(next);
 216     float mintoprev = min.distance(prev);
 217     float ttonext   = distance(next);
 218     float ttoprev   = distance(prev);
 219
 220     Tree_tsp p1, n1;
 221     float tton1, ttop1;
 222     if ((ttoprev - mintoprev) < (ttonext - mintonext)) {
 223       // would insert between min and prev
 224       p1 = prev;
 225       n1 = min;
 226       tton1 = mindist;
 227       ttop1 = ttoprev;
 228     } else {
 229       // would insert between min and next
 230       p1 = min;
 231       n1 = next;
 232       ttop1 = mindist;
 233       tton1 = ttonext;
 234     }
 235
 236     // Compute location for second cycle
 237     min = b;
 238     mindist = distance(b);
 239     tmp = b;
 240     for (b = b.next; b != tmp; b = b.next) {
 241       float test = distance(b);
 242       if (test < mindist) {
 243         mindist = test;
 244         min = b;
 245       }
 246     }
 247
 248     next = min.next;
 249     prev = min.prev;
 250     mintonext = min.distance(next);
 251     mintoprev = min.distance(prev);
 252     ttonext = this.distance(next);
 253     ttoprev = this.distance(prev);
 254
 255     Tree_tsp p2, n2;
 256     float tton2, ttop2;
 257     if ((ttoprev - mintoprev) < (ttonext - mintonext)) {
 258       // would insert between min and prev
 259       p2 = prev;
 260       n2 = min;
 261       tton2 = mindist;
 262       ttop2 = ttoprev;
 263     } else {
 264       // would insert between min andn ext
 265       p2 = min;
 266       n2 = next;
 267       ttop2 = mindist;
 268       tton2 = ttonext;
 269     }
 270
 271     // Now we have 4 choices to complete:
 272     // 1:t,p1 t,p2 n1,n2
 273     // 2:t,p1 t,n2 n1,p2
 274     // 3:t,n1 t,p2 p1,n2
 275     // 4:t,n1 t,n2 p1,p2
 276     float n1ton2 = n1.distance(n2);
 277     float n1top2 = n1.distance(p2);
 278     float p1ton2 = p1.distance(n2);
 279     float p1top2 = p1.distance(p2);
 280
 281     mindist = (float)(ttop1 + ttop2 + n1ton2);
 282     int choice = 1;
 283
 284     float test = (float)(ttop1 + tton2 + n1top2);
 285     if (test < mindist) {
 286       choice = 2;
 287       mindist = test;
 288     }
 289
 290     test = tton1 + ttop2 + p1ton2;
 291     if (test < mindist) {
 292       choice = 3;
 293       mindist = test;
 294     }
 295
 296     test = tton1 + tton2 + p1top2;
 297     if (test < mindist)
 298       choice = 4;
 299
 300     if (choice == 1) {
 301     //case 1:
 302       // 1:p1,this this,p2 n2,n1 -- reverse 2!
 303       n2.reverse();
 304       p1.next = this;
 305       this.prev = p1;
 306       this.next = p2;
 307       p2.prev = this;
 308       n2.next = n1;
 309       n1.prev = n2;
 310       //break;
 311     } else if(choice == 2) {
 312     //case 2:
 313       // 2:p1,this this,n2 p2,n1 -- OK
 314       p1.next = this;
 315       this.prev = p1;
 316       this.next = n2;
 317       n2.prev = this;
 318       p2.next = n1;
 319       n1.prev = p2;
 320       //break;
 321     } else if(choice == 3) {
 322     //case 3:
 323       // 3:p2,this this,n1 p1,n2 -- OK
 324       p2.next = this;
 325       this.prev = p2;
 326       this.next = n1;
 327       n1.prev = this;
 328       p1.next = n2;
 329       n2.prev = p1;
 330       //break;
 331     } else if(choice == 4) {
 332     //case 4:
 333       // 4:n1,this this,n2 p2,p1 -- reverse 1!
 334       n1.reverse();
 335       n1.next = this;
 336       this.prev = n1;
 337       this.next = n2;
 338       n2.prev = this;
 339       p2.next = p1;
 340       p1.prev = p2;
 341       //break;
 342     }
 343     return this;
 344   }
 345
 346   /**
 347    * Compute TSP for the tree t. Use conquer for problems <= sz
 348    * @param sz the cutoff point for using conquer vs. merge
 349    **/
 350   Tree_tsp tsp(int sz)
 351   {
 352     if (this.sz <= sz) return conquer();
 353
 354     Tree_tsp leftval  = left.tsp(sz);
 355     Tree_tsp rightval = right.tsp(sz);
 356
 357     return merge(leftval, rightval);
 358   }
 359
 360   /**
 361    * Print the list of cities to visit from the current node.  The
 362    * list is the result of computing the TSP problem.
 363    * The list for the root node (city) should contain every other node
 364    * (city).
 365    **/
 366   /*void printVisitOrder()
 367   {
 368     System.out.println("x = " + x + " y = " + y);
 369     for (Tree_tsp tmp = next; tmp != this; tmp = tmp.next) {
 370       System.out.println("x = " + tmp.x + " y = " + tmp.y);
 371     }
 372   }*/
 373
 374   //
 375   // static methods
 376   //
 377
 378   /**
 379    * Return an estimate of median of n values distributed in [min,max)
 380    * @param min the minimum value
 381    * @param max the maximum value
 382    * @param n
 383    * @return an estimate of median of n values distributed in [min,max)
 384    **/
 385   private static float median(float min, float max, int n)
 386   {
 387     float M_E2  = 7.3890560989306502274f;
 388     float M_E3  = 20.08553692318766774179f;
 389     float M_E6  = 403.42879349273512264299f;
 390     float M_E12 = 162754.79141900392083592475f;
 391
 392     // get random value in [0.0, 1.0)
 393     float t = (new Random()).nextFloat();
 394
 395     float retval;
 396     if (t > 0.5) {
 397       retval = /*java.lang.*/(float)(Math.log(1.0-(2.0*(M_E12-1)*(t-0.5)/M_E12))/12.0f);
 398     } else {
 399       retval = (float)(-/*java.lang.*/Math.log(1.0-(2.0*(M_E12-1)*t/M_E12))/12.0f);
 400     }
 401     // We now have something distributed on (-1.0,1.0)
 402     retval = (float)((retval+1.0f) * (max-min)/2.0f);
 403     retval = retval + min;
 404     return retval;
 405   }
 406
 407   /**
 408    * Get float uniformly distributed over [min,max)
 409    * @return float uniformily distributed over [min,max)
 410    **/
 411   private static float uniform(float min, float max)
 412   {
 413     // get random value between [0.0,1.0)
 414     float retval = (new Random()).nextFloat();
 415     retval = retval * (max-min);
 416     return retval + min;
 417   }
 418
 419   /**
 420    * Builds a 2D tree of n nodes in specified range with dir as primary
 421    * axis (false for x, true for y)
 422    *
 423    * @param n the size of the subtree to create
 424    * @param dir the primary axis
 425    * @param min_x the minimum x coordinate
 426    * @param max_x the maximum x coordinate
 427    * @param min_y the minimum y coordinate
 428    * @param max_y the maximum y coordinate
 429    * @return a reference to the root of the subtree
 430    **/
 431   public static Tree_tsp buildTree(int n, boolean dir, float min_x,
 432       float max_x, float min_y, float max_y)
 433   {
 434     if (n==0) return null;
 435
 436     Tree_tsp left, right;
 437     float x, y;
 438     if (dir) {
 439       dir = !dir;
 440       float med = median(min_x,max_x,n);
 441       left = buildTree(n/2, dir, min_x, med, min_y, max_y);
 442       right = buildTree(n/2, dir, med, max_x, min_y, max_y);
 443       x = med;
 444       y = uniform(min_y, max_y);
 445     } else {
 446       dir = !dir;
 447       float med = median(min_y,max_y,n);
 448       left = buildTree(n/2, dir, min_x, max_x, min_y, med);
 449       right = buildTree(n/2, dir, min_x, max_x, med, max_y);
 450       y = med;
 451       x = uniform(min_x, max_x);
 452     }
 453     return new Tree_tsp(n, x, y, left, right);
 454   }
 455
 456 }