home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / functions.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-14  |  5.7 KB  |  222 lines
  1. #include <math.h>
  2. #include <limits.h>
  3. #include <stdio.h>
  4. #include "TwoDView.h"
  5. #include "tspheaders.h"
  6. #include "prototypes.h"
  7. /********************************************************************/
  8. /* This file contains a number of miscellaneous functions used in all
  9.    of the TSP algorithms.
  10. */
  11. /********************************************************************/
  12.  
  13.  
  14.  
  15. /********************************************************************/
  16. /* Function: kfrom
  17.    given i and j, figure out what the k coordinate is.
  18. */
  19. /********************************************************************/
  20. int kfrom(int l, int m, int n)
  21. { 
  22. int i,j,k;
  23.  
  24. if (l < m) {
  25.   i = l;
  26.   j = m;
  27. }
  28. else {
  29.   i = m;
  30.   j = l;
  31. }
  32.  
  33. k = i*n - i*(i+1)/2+j-i-1;
  34. return(k);
  35. }     
  36.  
  37. /********************************************************************/
  38. /* Function: ClosestCities
  39.    given a list of cities, figure out which two are closest, and
  40.    return the distance between them.  
  41.    From and To will contain the indices of the cities.
  42.    The function returns the distance between them.
  43. */
  44. /********************************************************************/
  45. float ClosestCities(float *Distance, int *From, int *To, int NumberOfCities) {
  46. int i,j,k;
  47. float MinDistance;
  48.  
  49. MinDistance = INT_MAX;
  50. for(i=0;i<NumberOfCities;i++) {
  51.   for(j=(i+1);j<NumberOfCities;j++) {
  52.     k = kfrom(i,j,NumberOfCities);
  53.     if (Distance[k] < MinDistance) {
  54. #ifdef DEBUGMYDIR
  55.       printf("k is %d i is %d j is %d \n",k,i,j);
  56.       printf("changing mindistance from %f to %f \n",MinDistance,Distance[k]);
  57. #endif
  58.       MinDistance = Distance[k];
  59.       *From = i;
  60.       *To = j;
  61.     }
  62.   }
  63. }
  64.  
  65. return(MinDistance);
  66. }
  67.  
  68. /********************************************************************/
  69. /* Function: FarthestCities
  70.    given a list of cities, figure out which two are farthest, and
  71.    return the distance between them.
  72.    From and To will contain the indices of the cities.
  73.    The function returns the distance between them.
  74. */
  75. /********************************************************************/
  76. float FarthestCities(float *Distance, int *From, int *To, int NumberOfCities) {
  77. int i,j,k;
  78. float BigDistance;
  79.  
  80. BigDistance = 0;
  81. for(i=0;i<NumberOfCities;i++) {
  82.   for(j=(i+1);j<NumberOfCities;j++) {
  83.     k = kfrom(i,j,NumberOfCities);
  84.     if (Distance[k] > BigDistance) {
  85.  #ifdef DEBUGMYDIR
  86.       printf("k is %d i is %d j is %d \n",k,i,j);
  87.       printf("changing bigdistance from %f to %f \n",BigDistance,Distance[k]);
  88.  #endif
  89.       BigDistance = Distance[k];
  90.       *From = i;
  91.       *To = j;
  92.     }
  93.   }
  94. }
  95.  
  96. return(BigDistance);
  97. }
  98.  
  99.  
  100. /********************************************************************/
  101. /* Function: ValidTour
  102.    given a tour and 2 edges to exchange, figure out if the tour is
  103.    valid if the two edges are exchanged.
  104. */
  105. /********************************************************************/
  106. int ValidTour(int *Tour, int Edge1, int Edge2, int Reverse, 
  107.               int NumberOfCities) {
  108.  
  109. int i,To1,BeginningCity,CurrentCity,GoingThroughTour,IsATour,
  110.     StillLooking,AtEdge,NextEdge,NumberOfCitiesVisited;
  111.  
  112. int *TestingTour;
  113.  
  114. /* allocate space for TestingTour */
  115. TestingTour = (int *)malloc(2*NumberOfCities*sizeof(int));
  116. if (TestingTour == (int *) 0)
  117.   printf("Malloc for TestingTour failed. \n");
  118.  for (i=0;i<2*NumberOfCities;i+=2) {
  119.    TestingTour[i] = Tour[i];
  120.    TestingTour[i+1] = Tour[i+1];
  121.  }
  122.  
  123. /* exchange the edges in the tour. */
  124. /* if Reverse == 1, then make To From and From To. */
  125. if (Reverse) {
  126.   To1 = TestingTour[2*Edge1+1];
  127.   TestingTour[2*Edge1+1] = TestingTour[2*Edge2+1];
  128.   TestingTour[2*Edge2+1] = To1;
  129. }
  130. else {
  131. /* if Reverse == 0, then take the second edge as is. */
  132.   To1 = TestingTour[2*Edge1+1];
  133.   TestingTour[2*Edge1+1] = TestingTour[2*Edge2];
  134.   TestingTour[2*Edge2] = To1;
  135. }
  136.  
  137. GoingThroughTour = 1;
  138. IsATour = 0;
  139. BeginningCity = TestingTour[0];
  140. CurrentCity = TestingTour[1];
  141. NumberOfCitiesVisited = 0;
  142. AtEdge = 0;
  143.  
  144. while (GoingThroughTour) {
  145.   /* set NextEdge to be the next edge after AtEdge in the tour. */
  146.   if (AtEdge >= (NumberOfCities-1)) {
  147.     NextEdge = 0;
  148.   }
  149.   else {
  150.     NextEdge = AtEdge + 1;
  151.   }
  152.  
  153.   StillLooking = 1;
  154.   while ((StillLooking) && (GoingThroughTour)) {
  155.     
  156.     /* look to see if the To of NextEdge is the city we want. */
  157.     if (TestingTour[2*NextEdge] == CurrentCity) {
  158.       NumberOfCitiesVisited+=1;
  159.       if (CurrentCity == BeginningCity) {
  160.         if (NumberOfCitiesVisited == NumberOfCities) {
  161.           /* then we have found a valid tour. */
  162.           IsATour = 1;
  163.           GoingThroughTour = 0;
  164.         }
  165.         else {
  166.           /* otherwise, this tour has subtours. */
  167.           GoingThroughTour = 0;
  168.         }
  169.       }
  170.       CurrentCity = TestingTour[2*NextEdge+1];
  171.       AtEdge = NextEdge;
  172.       StillLooking = 0;
  173.     }
  174.     else {
  175.       /* look to see if the From of NextEdge is the city we want. */
  176.       if (TestingTour[2*NextEdge+1] == CurrentCity) {
  177.         NumberOfCitiesVisited+=1;
  178.         if (CurrentCity == BeginningCity) {
  179.           if (NumberOfCitiesVisited == NumberOfCities) {
  180.             /* then we have found a valid tour. */
  181.             IsATour = 1;
  182.             GoingThroughTour = 0;
  183.           }
  184.           else {
  185.             /* otherwise, this tour has subtours. */
  186.             GoingThroughTour = 0;
  187.           }
  188.         }
  189.             
  190.         CurrentCity = TestingTour[2*NextEdge];
  191.         AtEdge = NextEdge;
  192.         StillLooking = 0;
  193.       }
  194.     }
  195.  
  196.     /* get ready to look at the next edge. */
  197.     if (AtEdge >= (NumberOfCities-1)) {
  198.       if (NextEdge == (AtEdge-1)) {
  199.         StillLooking = 0;
  200.         GoingThroughTour = 0;
  201.       }
  202.       else {
  203.         NextEdge+=1;
  204.       }
  205.     }
  206.     else {
  207.       if (NextEdge >= (NumberOfCities - 1)) {
  208.         NextEdge = 0;
  209.       }
  210.       else {
  211.         NextEdge+=1;
  212.       }
  213.     }
  214.   }
  215. }
  216. free(TestingTour);
  217. return(IsATour);
  218. }
  219.   
  220.   
  221.   
  222.