/*
        HEADER:         CUG000.03;
        TITLE:          TwoOpt;
        DATE:           Mar 89;
        DESCRIPTION:    2-Opt Tour Improvement Algorithm;
        VERSION:        2.0;
        FILENAME:       2OPT.C;
        SEE-ALSO:       TSP.C, NN.C, POPT.C, HYBRID.C, 3OPT.C, FN.C,
                        BOOLEAN.H, NODELIST.H, TSP.H,
                        BLDMTX.C, PRTMTX.C, TIME.C;
        AUTHORS:        Kevin E. Knauss;
*/

#include <nodelist.h>

long TwoOpt (NumberOfVirteces, Path)
   unsigned NumberOfVirteces;
   NODE *Path;
{
   unsigned ArcCost();
   long CircuitCost;
   unsigned count, index, pindex, sindex, k;
   unsigned D2, D4;
   NODE *First, *Last, *Kth, *Save, *Reverse;

   count = 1;
   First = Path;
   do {
      Last = First->prior;
      Kth = First->next;
      do {
         D2 = ArcCost (First->position, Kth->next->position)  /* 2-Opt */
            + ArcCost (Kth->position, Last->position);
         D4 = ArcCost (First->position, Last->position)
            + ArcCost (Kth->position, Kth->next->position);
         if (D2 < D4) {
            for ( Reverse = First; Reverse != Kth; Reverse = Save) {
               Save = Reverse->next;
               Reverse->next = Reverse->prior;
               Reverse->prior = Save;
            }
            First->next = Kth->next;
            Kth->next->prior = First;
            Kth->next = Kth->prior;
            Kth->prior = Last;
            Last->next = Kth;
            count = 0;
            First = Last->next;
            Kth = First->next;
         } else
            Kth = Kth->next;
      } while ((Kth != Last->prior->prior) && (count != 0));
      if (count != 0)
         First = First->next;
      count++;
   } while (count < NumberOfVirteces);
   Last = First->prior;
   CircuitCost = ArcCost (Last->position, First->position);
   for ( Kth = First; Kth != Last; Kth = Kth->next)
      CircuitCost += ArcCost (Kth->position, Kth->next->position);
   return (CircuitCost);
} /* TwoOpt */