
#include <stdlib.h>
#ifdef MYDIR
#else
#include "TwoDView.h"
#include "TwoDTSP.h"
#include <appkit/graphics.h>
#endif
#include <math.h>
#include <limits.h>
#include <stdio.h>
#include "tspheaders.h"
#include "prototypes.h"
extern   setUpScaling(TwoDView *);
extern   setUpDrawing(TwoDView *);
/************************************************************************/
/* This function implements a (2-Opt) Tour Optimization Algorithm for the
   Travelling Salesperson Algorithm.  It provides an approximate optimal
   value rather than the optimal value. 

   Reference: Salkin & Mathur, Foundations Of Integer Programming, 1989
              North-Holland, p 690-93.
*/
/************************************************************************/
/* Parameters:   TwoDView *self: Ye Old Drawing Object

                    float *Data: Pointer to the list of points.
                                 Used to draw intermediate graph.

                float *Distance: Pointer to area that contains the
                                 Distances Between Each Pair of Cities

                      int *Tour: Pointer to area that will contain the
                                 indices of the n arcs that are selected 
                                 to be a part of the tour

             int NumberOfCities: Number of cities in the problem
*/
/************************************************************************/
/************************************************************************/
#ifdef MYDIR
float TourOptimization(float *Distance,int *Tour,float OptimalValue, 
                       int NumberOfCities) {
#else
float TourOptimization(TwoDView *self,float *data,float *Distance,int *Tour,
                       float OptimalValue, int NumberOfCities) {
#endif

int i,CurrentEdge,CurrentFrom,CurrentTo,NumberOfExchanges,
    NextEdge,NextFrom,NextTo,Exchanges,ExchangeEdge1,ExchangeEdge2,
    NewFrom1,NewFrom2,NewTo1,NewTo2;
float OnTourDistance1,OnTourDistance2,NotOnTourDistance1,NotOnTourDistance2,
      BestExchange,Gain,NewOptimalValue;
char msg[256];

#ifndef MYDIR /* code to set up drawing enviromment */
        self->displayFlag = DISP_PTS_ONLY;
        [self display];

	[self lockFocus];
  	setUpScaling(self);
  	NXSetColor([self->highColorWell color]);
  	setUpDrawing(self);
  	PSsetinstance(YES);
        PSnewinstance();
        for (i=0;i<2*(NumberOfCities);i+=2) {
	     int x,y;
	     x = Tour[i];
	     y = Tour[i+1];
	     [self drawEdge:X(x):Y(x):X(y):Y(y)];
	}
        NXPing();    
#endif

 NewOptimalValue = OptimalValue;
	
 Exchanges = 1;
 NumberOfExchanges = 0;

 /* while at least 1 edge exchange has ocurred, we must look and see if
    this change might make others possible. */
 while (Exchanges) {
   Exchanges = 0;
   BestExchange = 0;
   CurrentEdge = 0;

   /* for all edges on the tour, and look at all possible edge
      exchanges. */
   while (CurrentEdge < NumberOfCities) {

 #ifdef DEBUGMYDIR
     printf("comparing edge %d with all other edges \n",CurrentEdge);
 #else
     sprintf(msg,"comparing edge %d with all other edges \n",CurrentEdge);
     STATUS(msg);
 #endif

     CurrentFrom = Tour[2*CurrentEdge];
     CurrentTo = Tour[2*CurrentEdge+1];
     OnTourDistance1 = Distance[kfrom(CurrentFrom,CurrentTo,NumberOfCities)];
     NextEdge = CurrentEdge + 1;

     /* look at all edges on the tour that we might be able to make an
        exchange with CurrentEdge. */
     while (NextEdge < NumberOfCities) {
       NextFrom = Tour[2*NextEdge];
       NextTo = Tour[2*NextEdge+1];

       /* we can't look at edges that involve CurrentFrom or CurrentTo.*/
       if ((NextFrom != CurrentFrom) & 
          (NextFrom != CurrentTo)) {
         if ((NextTo != CurrentFrom) &
             (NextTo != CurrentTo)) {

           /* Get distance between NextFrom and NextTo. */
           OnTourDistance2 = Distance[kfrom(NextFrom,NextTo,NumberOfCities)];

           /* first look at exchanging CurrentFrom to CurrentTo and
              NextFrom to NextTo with CurrentFrom to NextFrom and
              CurrentTo to NextTo. */
           NotOnTourDistance1 = 
             Distance[kfrom(CurrentFrom,NextFrom,NumberOfCities)];
           NotOnTourDistance2 = 
             Distance[kfrom(CurrentTo,NextTo,NumberOfCities)];

           Gain = (NotOnTourDistance1 + NotOnTourDistance2) -
                  (OnTourDistance1 + OnTourDistance2);

           /* If there is a negative gain, this is a candidate for the 
              best exchange in this iteration. */
           if (Gain < BestExchange) {
            if (ValidTour(Tour,CurrentEdge,NextEdge,0,NumberOfCities)) {
 #ifdef DEBUGMYDIR
               printf("Changing BestExchange from %f to %f \n",BestExchange,Gain);
 #endif
               BestExchange = Gain;
               ExchangeEdge1 = CurrentEdge;
               ExchangeEdge2 = NextEdge;
 #ifdef DEBUGMYDIR
               printf("Changing NewFrom1 from %d to %d \n",NewFrom1,CurrentFrom);
               printf("Changing NewTo1 from %d to %d \n",NewTo1,NextFrom);
               printf("Changing NewFrom2 from %d to %d \n",NewFrom2,CurrentTo);
               printf("Changing NewTo2 from %d to %d \n",NewTo2,NextTo);
 #endif
               NewFrom1 = CurrentFrom;
               NewTo1 = NextFrom;
               NewFrom2 = CurrentTo;
               NewTo2 = NextTo;
             }
           }  

           /* next look at exchanging CurrentFrom to CurrentTo and
              NextFrom to NextTo with CurrentFrom to NextTo and
              CurrentTo to NextFrom. */
           NotOnTourDistance1 = 
             Distance[kfrom(CurrentFrom,NextTo,NumberOfCities)];
           NotOnTourDistance2 = 
             Distance[kfrom(CurrentTo,NextFrom,NumberOfCities)];

           Gain = (NotOnTourDistance1 + NotOnTourDistance2) -
                  (OnTourDistance1 + OnTourDistance2);

           /* If there is a negative gain, this is a candidate for the 
              best exchange in this iteration. */
           if (Gain < BestExchange) {
            if (ValidTour(Tour,CurrentEdge,NextEdge,1,NumberOfCities)) {
 #ifdef DEBUGMYDIR
               printf("Changing BestExchange from %f to %f \n",BestExchange,Gain);
 #endif
               BestExchange = Gain;
               ExchangeEdge1 = CurrentEdge;
               ExchangeEdge2 = NextEdge;
 #ifdef DEBUGMYDIR
               printf("Changing NewFrom1 from %d to %d \n",NewFrom1,CurrentFrom);
               printf("Changing NewTo1 from %d to %d \n",NewTo1,NextTo);
               printf("Changing NewFrom2 from %d to %d \n",NewFrom2,CurrentTo);
               printf("Changing NewTo2 from %d to %d \n",NewTo2,NextFrom);
 #endif
               NewFrom1 = CurrentFrom;
               NewTo1 = NextTo;
               NewFrom2 = CurrentTo;
               NewTo2 = NextFrom;
             }
           }  
         }
       }

       /* get ready to look at the next edge on the tour. */
       NextEdge+=1;

       /* perhaps we have looked at all exchanges for this edge...*/
       if (NextEdge == NumberOfCities) {
 #ifdef DEBUGMYDIR
         printf("done looking at edge %d \n",CurrentEdge);
 #else
         sprintf(msg,"done looking at edge %d \n",CurrentEdge);
         STATUS(msg);
 #endif
       }
     }
  
     /* Now look at the next city on the tour. */
     CurrentEdge+=1;
   }
   
   /* we've looked at all possible exchanges.  now, if BestExchange is 
      greater than 0, we have a valid exchange that will lead to a 
      better tour. */
   if (BestExchange < 0) {
 #ifdef DEBUGMYDIR
     printf("Found an exchange \n");
     printf("ExchangeEdge1 %d ExchangeEdge2 %d \n",ExchangeEdge1,ExchangeEdge2);
 #else
     sprintf(msg,"exchanging edges %d and %d \n",
                  ExchangeEdge1,ExchangeEdge2);
     STATUS(msg);
 #endif
     Tour[2*ExchangeEdge1] = NewFrom1;
     Tour[2*ExchangeEdge1+1] = NewTo1;
     Tour[2*ExchangeEdge2] = NewFrom2;
     Tour[2*ExchangeEdge2+1] = NewTo2;
     NewOptimalValue+= BestExchange;
     Exchanges = 1;
     NumberOfExchanges+=1;
     BestExchange = 0;
 #ifndef MYDIR
     /* draw the intermediate tour */
     PSnewinstance();
     for (i=0;i<2*(NumberOfCities);i+=2) {
       int x,y;
       x = Tour[i];
       y = Tour[i+1];
       [self drawEdge:X(x):Y(x):X(y):Y(y)];
     }
     sprintf(msg,"number of exchanges: %d \n",NumberOfExchanges);
     STATUS(msg);
     NXPing();
     [self->optimalValueField setFloatValue: NewOptimalValue at: 0];
     usleep(self->drawTime);
#endif
   }
           
 #ifdef DEBUGMYDIR
     /* print out current subtour */
     printf("number of exchanges: %d \n",NumberOfExchanges);
     for (i=0;i<2*(NumberOfCities);i+=2) {
       printf("i %d from city %d to city %d \n",i,Tour[i],Tour[i+1]);
     }
 #endif
    
}
#ifndef MYDIR
	PSsetinstance(NO);
	[self unlockFocus];
        self->displayFlag = DISP_PTS_RESULTS;
        [self display];
#endif

/* return the optimal value */
return(NewOptimalValue);
}
